algorithm - 旅行商修改

Question

我目前正在学习旅行商问题的优化算法，我想知道是否可以在不改变实际问题本身的情况下修改问题。如果这听起来很模糊，让我澄清一下:

据我所知，TSP 的决定 版本提出以下问题:

Given a list of vertices G and a cost c, is there a Hamiltonian path P such that the cost of P is at most c?

我理解这个问题的一般性和 NP 完整性。但是，我发现问题的修改版本更直观地思考:

Given a list of vertices G and a specific Hamiltonian path P, is there a different Hamiltonian path P* such that the cost of P* is less than P?

参数略有不同；第一个只给出总成本，而第二个给出构成该成本的整个顶点序列。我想知道的是，是否可以在不失一般性的情况下将第一个问题简化为第二个问题？显然，通过简单计算P的成本，可以将第二种降为第一种；但是，将第一个减少到第二个逃脱了我的掌握。非常感谢这方面的任何帮助。

Answer 1

减少将要求评估成本严格大于 c 的最短路径。

这个操作至少和原来的 TSP 一样难，因为 TSP 可以通过设置 c = 0 并询问返回的路径是否大于所需的 c 来减少它。

因此，归约本身就是 NP 难的。尽管如此，它可以通过重复应用原始 TSP(返回路径)来形成，逐渐增加 c 图中边长的最小差异，从比原始问题所需的 c 高一级开始。