问最大限度地降低城市间的旅行成本
EN

Stack Overflow用户

提问于 2016-05-05 02:59:46

回答 1查看 154关注 0票数 1

嗨，我有一个优化问题，我有n天的时间去k个城市旅行，我必须计划我的旅行，使我的旅行总成本最小化。

任意两个城市u和v之间的旅行费用取决于我决定旅行的那一天(所以u和v之间的旅行费用是一个函数f(u，v，n)，n是我旅行的那一天)，而我一天只能旅行一次。我也可以选择留在同一个城市。

有没有办法通过最短路径算法来解决这个问题？

发布于 2016-05-05 03:23:50

这是一个NP-完全问题(因为它是从哈密顿路径推导出来的)。这与标准的旅行商问题之间唯一的主要区别是边权重是动态的。这意味着您将面临O(V_V_E!)的一次性预处理成本。复杂性和整个周期可以在O(V^3)最坏情况时间内解决。

我能够在IEEE上发布的这篇paper中找到类似问题的一些细节，它描述了智能交通-TSP问题。

票数 0

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/37035870

复制

相似问题

问最大限度地降低城市间的旅行成本EN