algorithm - 如何设计最佳旅行计划

Question

我正在开发一个旅行计划程序。每个城市都有一个名为 rateOfInterest 的属性。两个城市之间的每条道路都有时间成本。问题是，给定起始城市和我们想要花费的具体时间量，如何输出最有趣的路径(即城市的 rateOfInterest 的总和)。我正在考虑使用一些贪心算法，但是有没有可以保证最佳路径的算法？

编辑 正如@robotking 所说，我们允许多次访问地点，而且只有第一次访问才有趣。我们有50个城市，每个城市大约有5个相邻的城市。每条边上的成本函数是时间或距离。我们不必访问所有城市，只需使用给定的成本函数，我们需要返回具有最高 ROI 的最佳部分行程。我希望这能让问题更清楚!

Answer 1

这听起来很像加权方式的 TSP 实例，意味着有些顶点比其他顶点更可取......

现在您可以找到最佳路径，尝试所有可能的排列(使用回溯和一些修剪以使其更快)，具体取决于我们正在谈论的城市数量。看TSP问题是n!问题所以在 n > 10 之后你可以忘记它......

如果您的城市数量不是那么少，那么找到最佳路径将是不可行的，所以放弃这个想法...但是很可能有足够好的启发式算法来近似足够好的解决方案。

Steven Skiena 推荐“模拟退火”作为逼近此类难题的启发式算法。它非常像“爬山”方法，但更灵活或更宽容。我的意思是，在“爬山”中，您总是只接受改进解决方案的更改，而在“模拟退火”中，在某些情况下，您实际上接受了更改，即使它会使您的解决方案在本地变得更糟，希望在未来的道路上拿回你的钱...

无论哪种方式，用于近似 TSP 类问题的任何方法都适用于此。