如何最小化顶点不相交路径覆盖中路径的最大成本

Question

给定一个有向加权图G和n，其中n是用于覆盖图G中所有顶点的路径数。如何最小化最长路径的最大成本？(假设此图中始终存在解决方案(

Answer 1

对于 n = 1，这显然变成了一个旅行推销员问题 - 这是 NP 困难的。因此，我不会在您的情况下寻找确切的算法。

我的猜测是，对于小n来说，一个好的解决方案是使用旅行推销员问题的丰富算法之一(通常近似最优解非常好(，然后从找到的路径中删除(n-1(最重的边。这样你就以 n 条路径结束。

关于TSP的维基百科文章实际上列出了一些非常简单的算法技术，这些技术应该给你一个相当好的近似值。