1

问题：

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

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

（这是在过去的 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 的算法和二进制堆来找到最短路径。

但是这个算法对一半的测试用例不起作用，它输出的解大于正确的解。

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

4

3 回答 3

2

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

这实质上意味着您删除“未使用”的坐标。但这会花费你回旋的空间。举个例子：

4
1 1
3 3
3 2
1 2

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

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

现在，如果您执行压缩方案，那么您将删除 y=2 列，实际上将没有任何列，您可以在不访问农场 3 或 4 的情况下从农场 1 传递到农场 2。所以我看不到任何收益从此压缩，可是麻烦不少。

所以我使用了 Dijktra 的算法

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

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

我想我会为 Dijkstra 使用“绕道指标”：每一步让你更接近距离的成本为零，而每一步让你远离的成本都是一个。最后，您可以将绕行成本乘以 2（因为您走的每一步也是您必须朝着目标迈出的一步）并加上端点的曼哈顿距离（这是零绕行成本) 并且您回到原来的成本。这基本上是来自 A* 的想法，但具有 Disjkstra 的性能（和现有实现）。

于 2013-09-03T13:37:15.467 回答
1

如果你压缩这个

..2
...
3.4
...
1..

对此

.2
34
1.

然后你将路径的长度从 1 增加到 2，因为 34 构成了一个虚假的障碍。您可以将多个空行/列压缩为一个空行/列而不是一个空行/列。

于 2013-09-03T13:37:54.497 回答
1

我的想法是：点到点的距离何时i不是i + 1曼哈顿距离？在我看来，唯一的情况是当有一个完整的水平或垂直块（或两者）时，例如，

        (i+1)                  X    (i+1)           (i+1)
                              X
      XXX XXXX                 X                   XXXX
         X                      X                     X
       i                    i   X                  i  X

我还没有编写任何代码，但在计算到下一个点的路线时扫描任一块可能会很有用，如果存在块，则计算最小绕行。

于 2013-09-04T03:11:58.470 回答