基于图论求解多选择背包问题

• 作者: 李炯城 鲍江宏
• 来源期刊: 计算机工程与设计
• 学科: 工学
• 关键词: 多选择背包问题 图论 最短路径算法 动态规划 多阶段决策过程图
• 年，卷（期）: 2009,（13）
• 所属期刊栏目: 人工智能
• 页码范围: 3144-3147
• 页数: 4页
• 分类号: TP301.6
• 字数: 3618字
• 语种: 中文

摘要

多选择背包问题涉及的约束条件种类最多,在背包问题的各种变形中最为复杂.使用动态规划的思想,巧妙地把这个组合优化领域的问题转化成图论上求最短路径的问题.因为标准的Dijkstra算法只能找出两个节点间的一条最短路径,为了克服这个问题,对该算法进行了改进.对案例的测试表明,该算法能成功地算出多选择背包问题的全部最优解.首次把动态规划、图论算法共同应用到多选择背包问题,既能发挥动态规划的理论优势来大大减少计算量,又能充分利用图论的已有成果.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李炯城	广东省电信规划设计院有限公司信息系统研究院	18	61	6.0	6.0
2	鲍江宏	华南理工大学数学科学学院	12	74	5.0	8.0