科研之友
微信
新浪微博
Facebook
分享链接
摘要
针对多阶段决策过程求解旅行商问题中离散确定性决策模型单一的问题，提出一种基于最优插入子集的动态规划法。通过研究旅行商问题的插入算法，提出简单插入最优性猜想和同型插座猜想并应用不完全归纳法进行测试。依据同型插座猜想的推论，引入最优插入子集的概念，重新设计了不同于Held-Karp解法的新算法。实验结果表明，该算法在不同数据集上均能求得最优解，并达到已知的运行时间界限。
- 单位
针对多阶段决策过程求解旅行商问题中离散确定性决策模型单一的问题，提出一种基于最优插入子集的动态规划法。通过研究旅行商问题的插入算法，提出简单插入最优性猜想和同型插座猜想并应用不完全归纳法进行测试。依据同型插座猜想的推论，引入最优插入子集的概念，重新设计了不同于Held-Karp解法的新算法。实验结果表明，该算法在不同数据集上均能求得最优解，并达到已知的运行时间界限。
