36

我知道有许多算法可用于计算图形或网格中两点之间的最短路径，例如广度优先、全对（Floyd's）、Dijkstra's。

然而，正如我所注意到的，所有这些算法都会计算该图形或网格中的所有路径，而不仅仅是我们感兴趣的两点之间的路径。

我的问题是： 如果我有一个网格，即一个二维数组，并且我有兴趣计算两点之间的最短路径，比如 P1 和 P2，以及我在网格上移动的方式是否受到限制（例如仅对角线，或仅对角线和向上等），什么算法可以计算这个？

请注意，如果您有答案，我希望您发布算法的名称而不是算法本身（当然，如果您也发布算法就更好了）；例如，无论是 Dijkstra 的算法，还是 Floyd 的算法，或者其他什么。

请帮助我，我已经考虑了几个月了！

伙计们，我在 TOPCODER.COM 上的网格中找到了这个算法，你只能移动（对角线和向上），但我不明白这是什么算法，任何人都知道吗？

#include<iostream>
#include <cmath>

using namespace std;




inline int Calc(int x,int y)

{



if(abs(x)>=abs(y)) return abs(x);
int z=(abs(x)+abs(y))/2;
return z+abs(abs(x)-z);
 }

class SliverDistance
{


    public:
int minSteps(int x1,int y1, int x2, int y2)
{
    int ret=0;
    if(((x1+y1)&1)!=((x2+y2)&1))y1++,ret++;
    return ret+Calc(x2-x1,y2-y1);
}
};
4

8 回答 8

44

李氏算法：http ://en.wikipedia.org/wiki/Lee_algorithm

它本质上是一个BF搜索，这里有一个例子：http ://www.oop.rwth-aachen.de/documents/oop-2007/sss-oop-2007.pdf

为了有效地实施它，请在此处查看我的答案：Change FloodFill-Algorithm to get Voronoi Territory for two data points? - 当我说标记时，你用你来自+1的位置上的数字标记它。

例如，如果你有这个网格，其中 * = 障碍物，你可以上下左右移动，你从 S 开始，必须去 D，0 = 自由位置：

S 0 0 0
* * 0 *
* 0 0 *
0 0 * *
* 0 0 D

您将 S 放入队列中，然后“扩展”它：

S 1 0 0
* * 0 *
* 0 0 *
0 0 * *
* 0 0 D

然后展开它的所有邻居：

S 1 2 0
* * 0 *
* 0 0 *
0 0 * *
* 0 0 D

所有这些邻居的邻居：

S 1 2 3
* * 3 *
* 0 0 *
0 0 * *
* 0 0 D

依此类推，最后你会得到：

S 1 2 3
* * 3 *
* 5 4 *
7 6 * *
* 7 8 9

所以从 S 到 D 的距离是 9。运行时间是 O(NM)，其中 N = 行数，M = 列数。我认为这是在网格上实现的最简单的算法，并且在实践中也非常有效。它应该比经典的 dijkstra 更快，尽管如果你使用堆来实现它，dijkstra 可能会赢。

于 2010-02-22T15:12:06.737 回答
6

使用A 星 (A*)算法。

于 2010-02-22T14:36:26.290 回答
5

你可能被误导了。Dijkstra 算法存在不同的变体。计算从每个点到每个其他点的最短路径（如 Floyd 的）。

但是，典型的 Dijkstra 算法基于优先级队列，并且只计算您所需的最短路径。它在执行过程中确实构造了几条路径，但这些都是从 A 到可能位于最终解决方案路径上的其他一些节点的部分路径。

因此，您可以轻松地将网格解释为图形（然后可以相应地考虑对角线等限制）并运行 Dijkstra 搜索从 A 到 B 的最短路径。这实际上只是对您的问题进行建模的问题，而不是您需要一些花哨的算法。

于 2010-02-22T14:41:50.317 回答
2

如果您的移动足够受限（例如，您只能向右、向上或向对角线向上和向右移动），那么您可以利用其重叠子问题和次优子结构性质并使用动态规划。

于 2010-02-22T14:52:55.997 回答
1

我不明白的是，如果您想要A和B之间的最短路径，如果C和D指向B，您是否还需要查看A到C和A到D？您的最短路径很可能是 ACB 或 ADB。你只需要扔掉未连接的节点。在我的一个项目中，我选取了 A 点和 B 点，检查了哪些其他点是连接的，那些没有从整个图表中删除的点。然后我继续使用 Dijkstra 算法。

于 2010-02-22T14:53:40.253 回答
1

这是使用 BFS 从 (0,0) 到 (0,m-1) 的矩阵中最短路径的 python 实现。您可以更改它以适应可变点。

n,m,k1,k2=[int(i) for i in input().split()]
arr=[[int(j) for j in input().split()] for i in range(n)]
x=[[-1 for i in range(m)] for j in range(n)]
x[0][0]=0
vis={}
q=[(0,0)]
while len(q)!=0:
    curr=q[0]
    rem=q.pop(0)
    vis[curr]=True
    r=curr[0]
    c=curr[1]
    if r-1>=0 and arr[r-1][c]==0:
        if vis.get((r-1,c),-1)==-1 or vis[(r-1,c)]!=True:
            q.append((r-1,c))
            x[r-1][c]=x[r][c]+1
    if r+1<n and arr[r+1][c]==0:
        if vis.get((r+1,c),-1)==-1 or vis[(r+1,c)]!=True:
            q.append((r+1,c))
            x[r+1][c]=x[r][c]+1
    if c-1>=0 and arr[r][c-1]==0:
        if vis.get((r,c-1),-1)==-1 or vis[(r,c-1)]!=True:
            q.append((r,c-1))
            x[r][c-1]=x[r][c]+1
    if c+1<m and arr[r][c+1]==0:
        if vis.get((r,c+1),-1)==-1 or vis[(r,c+1)]!=True:
            q.append((r,c+1))
            x[r][c+1]=x[r][c]+1
    #for i in x:
        #print(i)
ans=x[0][m-1]
if ans==-1:
    print(-1)
else:
    print(ans)
  • 输入矩阵应由 0 和 1 组成。0 表示可能的移动。
  • n 是行数。
  • m 是列数。
  • arr 是给定的矩阵。
  • x 是距 (0,0) 的距离矩阵。
  • vis 是一个字典，如果节点被访问，则给出布尔值。
  • -1 的输出表明不可能有这样的路径。
于 2016-07-09T10:05:57.413 回答
0

您的网格形成了一个图表（或者至少可以被视为一个图表）。消除一些运动方向表明它是一个有向图。如果您根本无法从一个节点移动到另一个节点，那么这就是图中不存在的边。

将网格编码为图形形式后，只需在众所周知的图形算法（您显然已经知道）中进行选择，即可遍历它以获得所需的结果类型（例如最短路径）。

编辑：我查看了您发布的答案，但我不确定该代码应该是/做什么。举例来说，它有：if(y>=0) max(abs(x),y);. 这似乎（至少对我来说）没有多大意义——结果max只是被丢弃了。为了完成一些有用的事情，它需要被退回或分配或按该顺序执行。就目前而言，您所能希望的最好的结果是编译器将其识别为死代码，并且不会为它生成任何东西。

我的猜测是代码并没有真正按预期工作，如果它做了任何有用的事情，那更多的是偶然而不是设计。要确保你已经解决了这样的问题，以至于你真的确定它做了什么，甚至更难以猜测真正的意图是什么，这需要相当多的时间和精力。

于 2010-02-22T15:18:16.713 回答
-2

使用 A* 算法查找 2D 网格中两点之间的路径。 http://theory.stanford.edu/~amitp/GameProgramming/ImplementationNotes.html

于 2015-04-01T06:23:13.300 回答