求解随机时变背包问题的确定性算法

• 作 者: 贺毅朝 张新禄 高锁刚 宋超
• 机 构: 石家庄经济学院信息工程学院; 河北师范大学数学与信息科学学院; 电子科技大学信息与软件工程学院
• 出 处: 小型微型计算机系统
• 发表日期: 2004年期
• 关键词: 动态优化问题 随机时变背包问题 动态规划法 算法复杂度
• 基金项目: 国家自然科学基金项目(10971052)资助;石家庄经济学院预研项目(2012-05)资助

随机时变背包问题(RTVKP)是智能计算领域中的一个动态组合优化问题,具有重要的理论与应用价值.对于背包载重随机变化的RTVKP问题(记为RTVKP3),首先利用改进的动态规划法提出了一种适于求解具有较小物品价值和较大背包载重的RTVKP3的确定性算法(记为MDP-RTVKP),给出了MDP-RTVKP可成功求解RTVKP3的必要条件;然后,基于MDPRTVKP和DPforRTVKP的不同适用性提出了一种适于求解任意RTVKP3实例的有效方法 GenericDPfRTVKP,并通过对大规模RTVKP3实例的仿真计算验证了GenericDPfRTVKP的通用性与高效性.