algorithm - 最大限度地减少城市之间的旅行成本

Question

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

任意两个城市 u 和 v 之间的旅行费用取决于我决定旅行的日期(因此 u 和 v 之间的旅行费用是一个函数 f(u,v,n)，其中 n 是日期当我旅行时)而且我每天只能旅行一次。我也可以选择留在同一个城市。

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

Answer 1

这是一个 NP 完全问题(因为它从哈密顿路径归约)。此问题与标准旅行商问题之间的唯一主要区别是边权重是动态的。这意味着您面临 O(VVE!) 复杂度的一次性预处理成本，并且整个循环可以在 O(V^3) 最坏情况下解决。

我能够在此 paper 中找到类似问题的一些详细信息发表于 IEEE，描述了智能交通-TSP 问题。