算法找到最短路径，障碍物

Question

我点的集合代表一格，我正在寻找一种算法，让我点A和B. 美中不足的是任意点之间的最短距离（不包括A和B）可能有阻碍路径的障碍，因此必须绕道。路径可能不会以对角线移动。

为别人寻找解决这类问题，我发现这些引用是非常有用的：

http://optlab-server.sce.carleton.ca/POAnimations2007/DijkstrasAlgo.html

http://en.literateprograms.org/Dijkstra%27s_algorithm_%28Java%29#chunk%20def:visit%20each%20vertex%20u,%20always%20visiting%20vertex%20with%20smallest%20minDistance%20first

Answer 1

这是一个很好的点使用A* search algorithm，启发式搜索算法，即使在存在障碍物的情况下也能快速找到点之间的最佳路径。我们的想法是网格转换成graph其中网格中的每个单元是一个节点，并且其中有未彼此阻碍任何两个相邻单元之间的边缘。一旦你有了这张图，你要找的答案就是图中从起始节点到目的节点的最短路径。

为了使用A *，你需要一个启发式功能“猜测”从发车到目的地方任何一点的距离。一个好的启发是这两个点之间使用the Manhattan distance。

如果你正在寻找一个更简单但仍然非常有效的寻找最短路径的算法，可以考虑查看Dijkstra's algorithm，它可以被认为是更简单的A *版本。它比A *慢一点，但仍然运行得非常快，并保证有最佳答案。

希望这会有所帮助！

Answer 2

这是可以使用广度优先搜索

/** 
    * computing distance of each cell from the starting cell 
    * avoiding obstacles, 0 represents obstacle 1 represents non obstacle 
    * we can take only one step x-1;x+1;y-1;y+1 
*/ 

#include<iostream> 
#include<queue> 
#include<stdio.h> 
using namespace std; 

class XY 
{ 
public : 
int x; 
int y; 
}; 

int main() 
{ 
int grid[8][8] = { 
    {1,1,1,1,1,1,1,1}, 
    {1,0,0,0,1,1,1,1}, 
    {1,1,0,0,1,1,1,1}, 
    {1,1,0,0,1,1,1,1}, 
    {1,1,1,2,0,1,0,0}, 
    {1,1,1,1,1,1,1,1}, 
    {1,1,1,1,1,1,1,1}, 
    {1,1,1,1,1,1,1,1} 
}; 


int rows = 8; 
int cols = 8; 

int distance[rows][cols]; 

for(int m = 0;m<rows;m++) 
{ 
    for(int n =0;n<cols;n++) 
    { 
     distance[m][n] = -1; 
    } 
} 

queue<XY> iterator; 


XY xy; 
xy.x = 0; 
xy.y = 0; 
distance[0][0] = 0; 
iterator.push(xy); 

while(!iterator.empty()) 
{ 
    xy = iterator.front(); 
    iterator.pop(); 
    //printf("popped %d+%d\n",xy.x ,xy.y); 
    for(int p = -1;p<2;p++) 
    { 
     for(int q = -1;q<2;q++) 
     { 
      if(p == q)continue; 
      int i = xy.x + p; 
      int j = xy.y + q; 

      if(i<0)i=0; 
      if(j<0)j=0; 
      if(i>rows-1)i=rows-1; 
      if(j>cols-1)j=cols-1; 

      if(i== xy.x && j == xy.y)continue; 

    //    printf("i,j = %d,%d\n",i,j); 

      if(distance[i][j] == -1) 
      { 
    //     printf("******\n"); 
       if(grid[i][j] != 0) 
       { 
    //     printf("assigned distance %d to %d+%d\n",distance[xy.x][xy.y] + 1,i,i); 
       distance[i][j] = distance[xy.x][xy.y] + 1; 
       XY xyn; 
       xyn.x = i; 
       xyn.y = j; 
       iterator.push(xyn); 
     //     printf("pushed %d+%d\n",xyn.x,xyn.y); 
       } 
      } 

     } 
    } 
} 

for(int x = 0;x<rows;x++) 
{ 
    for(int y =0;y<cols;y++) 
    { 
     printf("%d ",distance[x][y]); 
    } 
    printf("\n"); 
} 
return 0; 
}