| 引用本文: | 胡振震,袁唯淋,罗俊仁,等.面向多最优解组合优化问题的决策求解算法.[J].国防科技大学学报,2022,44(3):31-40.[点击复制] |
| HU Zhenzhen,YUAN Weilin,LUO Junren,et al.Decision solving algorithm for multiple optimal solution combinatorial optimization problem[J].Journal of National University of Defense Technology,2022,44(3):31-40[点击复制] |
|
| |
|
|
| 本文已被：浏览 6254次 下载 3741次 |
| 面向多最优解组合优化问题的决策求解算法 |
| 胡振震,袁唯淋,罗俊仁,邹明我,陈璟 |
|
(国防科技大学 智能科学学院, 湖南 长沙 410073)
|
| 摘要: |
| 针对具有固定物品总和、多最优解特征的组合优化问题,以固定总和实数子集问题和购买鸡翅问题为例,给出了这类多最优解组合优化问题的形式化表示。在分析枚举等经典算法基础上,提出了基于整数状态表示和实数状态表示的0-1决策递归搜索多最优解动态规划算法。针对该算法在最优解数量较大时,时间复杂度趋向O(mn)的问题,提出了基于相同决策路径合并和基于0-x决策的两种改进算法。实验中两种改进算法的计算时间基本符合与O(nb+nm)的正比关系,表明对于这类多最优解组合优化问题具有良好的求解性能。 |
| 关键词: 组合优化 多最优解 动态规划 固定总和实数子集问题 |
| DOI：10.11887/j.cn.202203005 |
| 投稿日期：2021-06-03 |
| 基金项目:国家自然科学基金资助项目(61702528,61806212)；湖南省自然科学基金资助项目(2019JJ50724) |
|
| Decision solving algorithm for multiple optimal solution combinatorial optimization problem |
| HU Zhenzhen, YUAN Weilin, LUO Junren, ZOU Mingwo, CHEN Jing |
|
(College of Intelligence Science and Technology, National University of Defense Technology, Changsha 410073, China)
|
| Abstract: |
| Oriented to the combinatorial optimization problem with fixed sum of goods and multiple optimal solutions, the problem formulation was given by two examples:the fixed sum real number subset problem and buying wings problem. A integer state and a real number state multi-optimal solution dynamic programming algorithm based on 0-1 decision recursive search was put forward on the foundation of analysis of some classical methods like enumeration. In order to cope with the problem of time complexity tending to the extreme O(mn) when the number of optimal solutions is large for the proposed algorithms, two improved algorithms, the same decision path fusion algorithm and the 0-x decision based algorithm were proposed. The computation time of the improved algorithms is consistent with the proportional relation with O(nb+nm) on the whole in experiments, which indicates that these algorithms have good performance for this type of problem. |
| Keywords: combinatorial optimization multiple optimal solution dynamic programming fixed sum real number subset problem |
|
|
|
|
|
