面向多最优解组合优化问题的决策求解算法

针对具有固定物品总和、多最优解特征的组合优化问题,以固定总和实数子集问题和购买鸡翅问题为例,给出了这类多最优解组合优化问题的形式化表示。在分析枚举等经典算法基础上,提出了基于整数状态表示和实数状态表示的0-1决策递归搜索多最优解动态规划算法。针对该算法在最优解数量较大时,时间复杂度趋向O(mⁿ)的问题,提出了基于相同决策路径合并和基于0-x决策的两种改进算法。实验中两种改进算法的计算时间基本符合与O(nb+nm)的正比关系,表明对于这类多最优解组合优化问题具有良好的求解性能。

Decision solving algorithm for multiple optimal solution combinatorial optimization problem

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(mⁿ) 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.