数学建模社区-数学中国

标题: 贪心核加速动态规划算法精确求解适用范围 [打印本页]
作者: 杨利霞    时间: 2020-10-14 16:18
标题: 贪心核加速动态规划算法精确求解适用范围
贪心核加速动态规划算法精确求解适用范围

9 w9 x; j! Z  G/ Q7 E* {
7 c- k) I; X! O( k) W, B0 l
. I, J' v1 s1 d! a1 K8 l针对背包容量折扣系数在 0.8~0.9 时，贪心核加速动态规划算法（GCADP）无法求得逆向强相关折扣' \5 Y! `( W% Y/ A+ G, Q8 E9 N
｛0-1｝背包问题实例（IDKP）精确解的问题，为求得 D｛0-1｝KP 实例的精确解，在对 IDKP 实例参数进行分析的, O& t/ g* G3 [/ W9 n! f7 \6 w, d) ^  Y
基础上，给出 GCADP 算法能精确求解 D｛0-1｝KP 实例的限定条件：任意项集的价值系数满足价值最小项大于
/ J! X# E9 }0 O5 c: T价值次大项的 0.99 倍。将该条件应用到 4 类 D｛0-1｝KP 实例的参数设置中，生成新的大规模 D｛0-1｝KP 实 8 L! W* Q' `. \' f
例。对 4 类 D｛0-1｝KP 实例运用 GCADP 和动态规划（DP）进行计算，计算结果表明，新的 4 类 D｛0-1｝KP 实例: ~. S3 k0 Z# [3 x
均得到精确解，并且 GCADP 随着数据规模的变大，求解时长增长平缓。
/ Z2 z2 N/ B$ M7 Y3 T4 U  S9 T! t8 b) _4 h
; \5 O! p2 B& m( j9 c& N

贪心核加速动态规划算法精确求解适用范围.pdf

1.9 MB, 下载次数: 1, 下载积分: 体力 -2 点

售价: 2 点体力  [记录]  [购买]





欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5