首页 文章

如何计算网格中两点之间的最短路径

提问于
浏览 次
31

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

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

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

Please notice here that if you have an answer, I would like you to post the name of the algorithm rather than the algorithm itself (of course, even better if you also post the algorithm); for example, whether it is Dijkstra's algorithm, or Floyd's, or whatever.

请帮助我，我几个月来一直在考虑这个问题！

好吧我们在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);
}
};
algorithm shortest-path

8 回答

  • 4

    如果您的移动足够严格（例如，您只能向右或向上移动，或向上和向右移动），那么您可以利用其重叠的子问题和次优的子结构性质并使用dynamic programming .

    回复于
  • 6

    我不明白的是，如果你想要A和B之间的最短路径，如果C和D指向B，你还不需要看A到C和A到D吗？你的最短路径很可能是A-C-B或A-D-B . 你只需要抛弃未连接的节点 . 在我的一个项目中，我采用了A点和B点，检查了其他点的连接点，以及那些不是算法的点 .

    回复于
  • 39

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

    它's essentially a BF search, here'的一个例子：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可能会赢 .

    回复于
  • 0

    使用A Star (A*)算法 .

    回复于
  • 1

    你可能会被解雇 . Dijkstra算法存在不同的变体 . 一个计算从每个点到每个其他点的最短路径（如Floyd的） .

    但是，典型的Dijkstra算法基于优先级队列，仅计算所需的最短路径 . 它在执行期间确实构造了几条路径，但这些路径都是从A到可能在最终解决方案路径上的其他节点的部分路径 .

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

    回复于
  • 2

    这是使用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 's and 1' s . 0表示可能的移动 .

    • n是行数 .

    • m是列数 .

    • arr是给定的矩阵 .

    • x是距离（0,0）的距离矩阵 .

    • vis是一个字典，如果访问该节点则给出一个布尔值 .

    • 输出-1表示没有这样的路径可能 .

    回复于
  • -1

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

    一旦您将网格编码为图形形式，就可以在众所周知的图形算法（您显然已经意识到）中进行选择，以便根据您想要的结果类型（例如最短路径）进行遍历 .

    编辑：我've looked at the answer you posted, but I'我不知道该代码应该是什么/做什么 . 例如，它有： if(y>=0) max(abs(x),y); . 这似乎（至少对我而言）没有多大意义 - max 的结果被简单地扔掉了 . 要完成有用的事情，需要返回或分配该命令或其他内容 . 就目前而言，您可以期望的最好的是编译器将其视为死代码，并且不会为其生成任何内容 .

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

    回复于
  • 1

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

    回复于

相关问题