用障碍物找到最短路径的算法

我有一个代表网格的点集合，我正在寻找一个能让我得到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 *搜索算法的绝佳场所， A *搜索算法是一种启发式搜索算法，即使在存在障碍物时也可以非常快速地找到点之间的最佳路径。 该想法是将网格转换为图形 ，其中网格中的每个单元格是节点，并且在任何两个相邻单元格之间存在不相互阻碍的边缘。 获得此图后，您要查找的答案是图中从起始节点到目标节点的最短路径。

为了使用A *，您需要一个启发式function，“猜测”从网格上的任何点到目标方块的距离。 一个好的启发式方法是使用两点之间的曼哈顿距离 。

如果您正在寻找一种更简单但仍然非常有效的算法来寻找最短路径，请考虑查看Dijkstra算法 ，该算法可以被认为是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 #include #include 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 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