算法找到两点远离彼此

StackOverflow https://stackoverflow.com/questions/477591

题

Im在寻找一种算法应用于一个赛车游戏Im。地图上/水平/轨道是随机产生的，所以我需要找到两位置，启动和目标，即使使用最多的地图。

  • 算法内工作的一个两维空间
  • 从每一点，人们只能横以下一点在四个方向；上下左右
  • 点只能是阻止或nonblocked，只有nonblocked点可以走

关于计算距离，它不应该是"鸟的道路"为缺乏一个更好的词。路径A和B之间应该更长的时间，如果有一堵墙(或其他阻挡地区)之间。

Im不确定在哪里开始，评论是非常受欢迎的和拟议的解决方案是优选的伪代码。

编辑： 正确的。之后的寻找过 gs的代码 我给它一次机会。而不是蟒蛇，我这段时间写C++。但是，即使在阅读了 Dijkstras算法, ， floodfill 和 Hosam Alys解决方案, 我未能发现任何关键的区别。我的代码仍然有效，但不一样快，你似乎得到你的运行。全源于 pastie.唯一有趣的线(我猜)是Dijkstra变本身在线78-118.

但是速度不是这里的主要问题.我真的很感激的帮助，如果有人将一种足以指出的差异算法。

  • 在Hosam Alys算法，唯一不同的是，他的扫描从边界，而不是每个节点?
  • 在Dijkstras你跟踪和复盖距离，但不是在floodfill，但这就是呢？
有帮助吗？

解决方案

假设的地图是长方形的，你可以循环过的所有边界点，并启动一个洪水填充，以找到最遥远点从起点：

bestSolution = { start: (0,0), end: (0,0), distance: 0 };
for each point p on the border
    flood-fill all points in the map to find the most distant point
    if newDistance > bestSolution.distance
        bestSolution = { p, distantP, newDistance }
    end if
end loop

我想这将是在 O(n^2).如果我没有记错的话，它的 (L+W) * 2 * (L*W) * 4, ，哪里 L 是的长度并且 W 是的宽的地图上， (L+W) * 2 代表若干边境点的周界， (L*W) 是的点数， 4 是的假设，即洪水填补将访问一点的一个最大的4倍(从所有方向)。由于 n 相当于数分，这相当于 (L + W) * 8 * n, ，这应该比 O(n2).(如果地图是正方形，以便将 O(16n1.5).)

更新： 为每评论，由于该地图是一个迷宫(于一个简单的障碍，因为我想最初)，可以作出同样的逻辑之上，但检查的所有各点的地图(相对要点的边界)。这应该可以的 O(4n2), ，这仍然是更好的比F-W及Dijkstra的。

注： 洪水灌 更适合这个问题，因为所有的顶点直接相连通，只有4个边界。一种广度的第一个穿越的地图上可以产生结果相对较快(在只是 O(n)).我假设每一点可以检查在洪水填写从其每4邻居，因此该系数在公式上。

更新2： 我感谢所有积极的反馈，我已经收到关于这种算法。特别感谢@乔治 他审查.

P.S.任何评论或修正的欢迎。

其他提示

后续行动的问题，关于弗洛伊德-Warshall或简单的算法 Hosam Aly:

我创建了一个测试程序，其中可以使用这两种方法。这些文件：

在所有试验的情况下弗洛伊德-Warshall是由一个伟大幅度较慢，可能这是因为数量非常有限的边缘，帮助这个算法来实现这一点。

这些是倍，每个时段是四和3的10个领域是一个障碍。

Size         Hosam Aly      Floyd-Warshall
(10x10)      0m0.002s       0m0.007s     
(20x20)      0m0.009s       0m0.307s
(40x40)      0m0.166s       0m22.052s
(80x80)      0m2.753s       -
(160x160)    0m48.028s      -

时Hosam Aly似乎是二次方程，因此我建议使用这种算法。也存储的消耗通过弗洛伊德-Warshall是n2, ，显然多于所需要的。如果您有任何想法为什么弗洛伊德-Warshall是如此缓慢，请留言或编辑这个员额。

PS:我没有写C或C++在很长一段时间，我希望我没有太多的错误。

我删除了我原来的职位推荐弗洛伊德-Warshall算法。:(

gs有没有一个现实的基准 你猜是什么，F-W是基本上低于Hosam Aly的"洪水填写"算法用于典型的地图大小！因此，即使F-W是一个很酷的算法和速度远远超过Dijkstra为密集的图表，我不能让你再用于运的问题，这涉及非常稀疏的图表中(每个顶点只有4边)。

为记录：

  • 一个高效率的执行情况 Dijkstra的算法 需要O(Elog V)时间为一个图与电子边和V折点。
  • Hosam Aly的"洪水填写"是一个 广度第一次搜索, ，这是O(V)。这可以被认为是一个特殊的情况下Dijkstra的算法在没有顶点可以有它的距离估计修订。
  • 的 弗洛伊德-Warshall算法 需要O(V^3)时间，是非常容易代码，并仍然是最为密集的图表中(这些图表，其顶点是通常连接到其他许多顶点).但它的 不正确的选择 对于运的任务，这涉及非常稀疏的图表。

这听起来像是你想要的是终点，由分 图径.一个相当好和容易计算的近似值，是随机挑选一个点时，发现最远点，然后找到的最远点，从那里。最后这两点应该是接近最大限度地隔开。

对于一个长方形的迷宫，这意味着两个洪水填补了应该得到你一个很好的对的开始和结束点。

莱蒙德赛德尔给出一个简单的方法使用矩阵乘以计算所有对距离矩阵在一个未加权,无向图(这正是你想要的)的第一部分的他的文件 在所有的-对-最短路径问题在未加权无向图 [pdf].

输入的是邻接矩阵和输出的所有对最短路径距离矩阵。运行时间是O(M(n)*日志(n))n点M(n)运行时间的矩阵乘算法。

该文件还给出的方法计算的实际路径(在相同的运行时间)，如果你需要这个了。

Seidel的算法是很酷，因为运行时间是独立的边的数量，但我们实际上不在乎这里是因为我们的图是稀疏。然而，这可能仍然是一个不错的选择(尽管略有不正^2运行时间)如果希望所有对距离矩阵，这也可能更易于执行和调试，比floodfill在一个迷宫。

这里是伪:

Let A be the nxn (0-1) adjacency matrix of an unweighted, undirected graph, G

All-Pairs-Distances(A)
    Z = A * A
    Let B be the nxn matrix s.t. b_ij = 1 iff i != j and (a_ij = 1 or z_ij > 0)
    if b_ij = 1 for all i != j return 2B - A //base case
    T = All-Pairs-Distances(B)
    X = T * A
    Let D be the nxn matrix s.t. d_ij = 2t_ij if x_ij >= t_ij * degree(j), otherwise d_ij = 2t_ij - 1
    return D

要获得对点的最大距离我们只是回argmax_ij(d_ij)

完成了一条巨蟒模型的dijkstra解决问题的办法。代码得有点长，所以我张贴在别的地方: http://refactormycode.com/codes/717-dijkstra-to-find-two-points-furthest-away-from-each-other

在我设置，它需要大约1.5秒运算法为一个节点。运行每一个节点需要几分钟。

不起作用，虽然，它总是显示左上和右下角作为最长的路径；58瓷砖。这当然是真实的，当你没有障碍。但即使增加几个随意放置的，该程序仍然认为，一个最长的。也许它仍然是真实的，很难测试没有更高级的形状。

但是，也许至少可以显示我的野心。

Ok，"Hosam的算法"是一个广泛第一搜索与一个预选的节点。Dijkstra的算法不应适用在这里，因为你的边缘，没有重量。

差异是至关重要的，因为如果对权重的边缘变化，需要保持一个很大的选择(替代路线)开放，并检查他们的每一步。这使得算法更加复杂。与的广度第一次搜索，你只是探索所有的边缘，一旦在一种方式，garantuees你找到最短路径的各个节点。即通过探索中的边缘了，你找到他们。

所以基本上的差异是Dijkstra有'原路返回'看看边缘它已经探讨了前以确保它是最短的路线，同时将广泛第一搜索总是知道这是最短的路线。

此外，在一个迷宫点在外边是不能保证部分的最长的路线。例如，如果你有一个迷宫的形状的一个巨大的螺旋式，但是外端回到中间，你可能有两点之一的核心螺旋和其他在结束的螺旋，无论是在中间！

因此，一个好办法是使用广泛第一搜索的每一点，但删除该起始点搜索后(你已经知道所有的路线，并从它)。复杂性的广度第一个是O(n)，其中n=|V|+|E|.我们这样做一旦每个节点V，使它成为O(n^2).

你的描述听起来对我像一个 迷宫的路由 问题。检查出来的 李算法.书籍有关的地方和路线问题的集成电路的设计可以帮助你- 长外套是"算法对超大规模的物理设计的自动化" 好，你可以找到 超大规模的物理设计自动化的Sait和优素福 有用的(和更便宜在谷歌的版本...)

如果你的对象(分)不动频繁，你可以执行这样的计算，在一个短得多O(n^3)时间。

所有你需要的是休息的空间变为大型网格和预算的间网格的距离。然后选择一点对占大多数遥远的电网是一个问题的简单的表中查找。在一般情况下你会需要对检查只有一小组的对象。

这个解决方案的工作如果距离的指标是连续的。因此，如果，例如有许多障碍，在该地图(如在迷宫)，这种方法可能会失败。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top