使用分支定界算法修改 TSP

Question

我一直在努力使用分支定界来解决它，以找到下一个任务的最佳路径：

有一个城市列表，它们都是相互连接的，基本上是一个完整的图表，每个城市都有一个兴趣指数（城市'A'有8个兴趣点，城市'B'有9个）。旅行的预算有限，我们需要想出一条获得最大可能兴趣指数的路径。此外，路径必须在同一个城市开始和结束，因此如果我们从那里开始，我们需要从最后一个城市返回到城市“A”，例如。

没有必要走遍所有的城市，有时预算不允许。可以选择起始城市和结束城市，但问题是你需要回到起始城市。

不允许两次访问一个城市，唯一可以访问同一个城市的情况是返回起始城市。

此外，通过其他城市穿越城市 X 和 Y 可能更便宜，因此图表是非公制的。

有人问过这个任务涵盖的现实世界问题，它是旅游路径算法。我们需要用可用资金创建最感兴趣的路径。

还有哪些算法适合这种任务？

我试过贪心算法，有人尝试用分支定界法解决它

我希望在任何语言上都有一个有效的分支定界解决方案。

Answer 1

需要注意两点：

1. 最好的方案是每个城市都走一遍，只要旅游预算可以（你的问题没有明确说明旅游预算）

2. 度量旅行商算法给出了良好的结果和出色的性能（你没有指定你的性能要求！）只要对于任何两个顶点（ x 和 y ） X 和 Y 之间的直接边总是比 X 之间的旅行更便宜和 Y 通过第三个顶点。

所以算法是：

• 校验图为公制
• 如果不是公制，放弃！
• 使用度量算法解决旅行商问题
• 如果解决方案成本低于预算，解决
• 删除兴趣最小的城市，及其所有链接
• 重复直到找到解决方案。