algorithm - 以给定顺序访问一组点的最小成本路径恰好一次？

Question

问题:

我们在 2D 平面上给定了一组 N 个点，我们必须找到一条路径，该路径以 1-2-3....N 的顺序访问所有点并返回到 1，这样所花费的时间被最小化。我们可以向北、向东、向西或向南移动一步，这需要 1 个单位的时间。我们不能多次访问 N 个点中的任何一个，除了 1，我们不能访问超过两次。

N <= 100
每个点的x轴和y轴是<= 1000000

(This 是过去 USACO 竞赛中出现的完整问题陈述)

我的算法:

点的 x 轴和 y 轴可以非常大，但只有 <=100 个点，因此，我们更改点的 x 轴，以便当它们按 x 轴的升序排列时，点之间的差异相邻点的x轴为1。我们对所有点的y轴做同样的事情。

现在我们找到从点 1 到点 2、从点 2 到点 3、...以及从点 N 到点 1 的最短路径，除了源点和目标点之外，不访问任何给定点。我们不能使用直接的 bfs 来找到最短路径，因为从点 x,y 到点 x+1,y 的距离不是 1，而是 x+1 的原始值减去 x 的原始值。因此，我将 Dijktra 算法与二叉堆结合使用来寻找最短路径。

但是这个算法对 testcases 的一半不起作用，它输出的解比正确解大。

为什么这个算法是错误的？否则我们如何解决这个问题？

Answer 1

The x and y axis of the points can be very large but there are just <=100 points so, we change x-axis of the points so that when the are arranged in ascending order of their x axis the difference between the x axis of the adjacent points is 1. We do the same for all the y axis of the points.

这实际上意味着您删除了“未使用”的坐标。但这将花费您的机动空间。举个例子:

4
1 1
3 3
3 2
1 2

这里的最短路径需要 8 步。假设正 x 为东，正 y 为北，则最佳路径为 ennESwWS，大写字母表示到达下一个农场。

   /--2
   |  |
4--|--3
|  |
1--/

现在，如果你执行你的压缩方案，那么你将删除 y=2 列，实际上将没有任何列，你可以在不访问农场 3 或 4 的情况下从农场 1 传递到农场 2。所以我从这种压缩中看不到任何好处，但会带来很多麻烦。

So I used Dijktra's algorithm

在什么图表上？如果您只在农场使用 Dijkstra，就会遇到麻烦，因为您必须考虑非农场位置。据我所知，如果你也接受这些，事情应该会奏效。除了前面的压缩。

如果您想保留这个想法，您可以做的是将空行或空列的连续范围压缩成一个。这样，您的图表将保持相当小(最多 201 行和列)，但在农场周围有空间可以操纵的地方，您的图表将代表这一事实。

我想我会为 Dijkstra 使用“迂回指标”:使您更接近距离的每一步成本为零，而使您远离的每一步成本为一。最后，您可以将绕行成本乘以二(因为您每走一步也是您必须朝着目标迈出的一步)并加上终点的曼哈顿距离(这是零绕行成本) 并且您以原始成本返回。这基本上是 A* 的想法，但具有 Disjkstra 的性能(和现有实现)。