TSP变体的近似算法，固定的启动和结束的任何地方，但在每个顶点处的起点 +多次访问

Question

注意：由于这次旅行并没有在同一地点结束，而且只要我仍然访问所有人，每个点都可以访问一次以上，这并不是真正的TSP变体，而是我认为由于缺乏对问题的更好定义。

这个问题最初发布在Stackoverflow上，但有人告诉我这将是一个更好的地方。我得到了一个指针，这将问题从非属性转换为度量标准。

所以..

假设我要以n的兴趣点进行远足之旅。这些点都是通过远足径连接的。我有一张地图显示所有距离距离的步道，给了我一个定向的图形。

我的问题是如何近似一个从A点开始并访问所有兴趣点的巡回演出，同时在我开始的任何地方结束了巡回演出，我希望这次旅行尽可能短。

由于远足的性质，我认为可悲的是不是对称问题（或者我可以将我的不对称图转换为对称图形吗？），因为从高海拔到低海拔显然比另一方面更容易。

由于我访问每个点几次没有限制，只要我访问所有点，从A到D的最短路径是否经过B和C。这足以说三角不平等能力，因此我有一个度量问题？

我相信我的问题比TSP更容易，因此这些算法不符合此问题。我考虑过使用最小跨树，但是我很难将其应用于此问题，在这种情况下，应该是公制的不对称有向图？

我真正想要的是一些关于我如何提出近似算法的指示，该算法将在所有N点找到几乎最佳的旅行

Answer 1

我不知道如何解决您的问题或显示其NP硬度，但是您可以找到所有最短的路径以将图形转换为公制，只需替换$ e_ {a，b} $，从a→b和最短路径如果$ a之间没有边缘，则b $添加最短路径重量的新边缘，现在您可以为TSP运行一些近似值以找到问题的近似值，因为我知道最好 TSP的近似值当前为$ O（{ log n fover log { log n}}）$. 。基本的想法是使用karp-karp放松，并找到特殊的跨越树，然后使用诸如Christofides算法之类的方法。 （它具有一些新的定义，例如薄树，……比其他非对称情况的方法更难），您也可以使用已知的$ o（ log n）$近似值。另外，我想到了您的问题，可以用最小的周期盖近似近似，但是我无法获得良好的结果。如果我发现任何东西，我会更新此答案。