脱离迷宫的搜索算法

网页应用示例

https://davidpynes.github.io/Tutorials/Graphs/Graph_02/

Why

1968年，人工智能研究员Nils Nilsson制作了一个机器人原型，它可以穿过一个有障碍物的房间。这种被称为A1的路径搜索算法是当时最著名的Dijkstra算法的更快版本。

紧接着，Betram Raphael提出了对A1算法的重大改进，并把修订后的算法称为A2。

后来Hart，Nilsson和Raphael证明了A2是最优的，于是，这个算法重新被命名为A*。

因为A*算法的性能和精确性，它被广泛使用于路径寻找中。A*是一种使用最佳优先搜索（best first search)方法的带有智慧决策的搜寻算法。

最佳优先搜索（Best first search）结合了深度优先搜索（depth first search，DFS）和广度优先搜索(breadth first search,BFS)的思想。

What

让我们举个例子说明一下， A*算法与DFS和BFS算法的优缺点。

在下图中，有一个火柴人表示起点，星星表示目的地。

1.深度优先搜索算法

DFS考虑所有相邻路径，并且径直向目标移动。在这种方法中，该算法没有任何远见，无法避免前方只有几步远的“L”形墙。

火柴人不断向右上方移动，离目标越来越近。这个DFS算法进入到了墙的拐角处，现在它需要绕着墙的走，这也导致了不必要的步骤。

一个更有效的方法是找到一个能回避“L”形墙的整体路线，但是这个必须在第一步的时候就向右下方或者左上方移动。

因为这些移动不是接近目标的直接路径，所以这些路径不在深度优先算法的考虑范围之内。

2.广度优先搜索算法

不像DFS方法，BFS方法会找到图上的所有路径。

BFS方法会发现第一步中所有可能的相邻路径，然后发现第二步的，然后是第三步的，等等。

BFS方法会找到很多路径，但是不能找到一个特定的路径。

用BFS来找到一个特定的路径需要探索很多不必要的路径。因此，如果我们需要到达一个特定的地点，用BFS方法并不是理想的。

3.最佳优先搜索算法

A*算法是最佳优先算法（best-first）的一种,不仅计算相邻路径的距离，也计算目标的距离。其结果便是一种经过深度导引的广度优先搜索。

所以，现在，搜索路径的广度以目标距离为导引。

这个算法最终的目的是离目标越来越近，但是也希望探索出许多的路径，只要这些路径和目标的大概方向一致。

注意，最佳优先搜索方法回避了“L”形墙并且也避免了非目标方向。

当在迷宫中应用A*算法时，小人儿通常会朝着目标向右下方移动，但是也会向右上方或者左下方移动来回避障碍物。

点击这里用A*算法走出迷宫

https://davidpynes.github.io/Tutorials/Graphs/Graph_02/

How

A*算法这种最佳优先算法, 是Dijkstra的算法加上对距离的计算。

让我们先来定义迷宫的一些特征，例如高度，宽度和点。（译者注：在这里表述成点而不是方块儿，因为在实际操作中可以是三角形或者其它形状，所以统一表述成点。）

高度，宽度和点：

#define HEIGHT 25

#define WIDTH 25

enum struct direction ;

struct point {

int x,y;

direction d;

point(int x_ = -1, int y_ = -1):x(x_),y(y_){};

point(int x_, int y_, direction d_):x(x_),y(y_),d(d_){};

bool inBounds() { return ( x>=0 && x=0 && y

void print() { std::cout

const bool operator==(const point& rhs) const { return ( x == rhs.x && y == rhs.y) ? 1 : 0; };

};

高度和宽度都是数字。

坐标代表点的位置，有时也用于表示移动的方向。这里还有一些重要的细节。inBounds()检查点是否在迷宫界限之内，print()用来显示点的位置，operator==重载了等号运算，用于检查两个的坐标是否相同。

现在定义探试程序，欧氏距离（距离公式）。 这个计算把算法从当下的点导向目标。

欧氏距离：

float euclideanDistance(point a, point b) {

return (pow( pow( a.x - b.x, 2.0) + pow( a.y - b.y, 2.0), 0.5));

}

现在完成了点（point）和欧式距离（euclideanDistanceare）的定义，接下来，让我们生成一个随机的迷宫。

生成随机迷宫：

void randomMaze(int maze[HEIGHT][WIDTH], point p) {

point rn[4] = {

point(p.x-2, p.y, direction::L),

point(p.x+2, p.y, direction::R),

point(p.x, p.y+2, direction::U),

point(p.x, p.y-2, direction::D)

};

std::random_shuffle(&rn[0], &rn[4]);

for(point cn : rn) {

if(cn.inBounds() && !maze[cn.y][cn.x]) {

if(cn.d == direction::L)

maze[cn.y][cn.x+1] = 1;

else if(cn.d == direction::R)

maze[cn.y][cn.x-1] = 1;

else if(cn.d == direction::U)

maze[cn.y-1][cn.x] = 1;

else if(cn.d == direction::D)

maze[cn.y+1][cn.x] = 1;

maze[cn.y][cn.x] = 1;

randomMaze(maze, cn);

}

}

}

这段代码很有趣，因为这段代码通过使用递归的堆栈生成随机迷宫。

程序中，首先根据输入的点创建一个与之相邻度数为2的点组成的数组（即以这个点为中心的正方形的四个顶点）。然后对着几个点随机排序，并进行迭代处理。如果这个点在迷宫范围之内，并且其本身代表了墙（即这个点的值为0）则将这个点设置为路径（即将其值设置为1），并将其对应方向的上的邻接点设置为墙。然后基于这个点，递归调用此方法。

输出结果：

注意，墙的值为0，路径的值为1。

现在，点（point），欧式距离（euclideanDistance），随机迷宫（randomMaze）都已经定义好了，现在对A*进行编程。

A*功能：

std::vector

astar(int maze[HEIGHT][WIDTH],point s,point g) {

//initialize sets//

std::vector

paths[HEIGHT][WIDTH];

float dist[HEIGHT][WIDTH] = { 0 };

bool visited[HEIGHT][WIDTH] = { 0 };

for(int i=0; i

for(int j=0; j

dist[i][j] = INT_MAX;

//initialize starting point//

point cur = s;

dist[cur.y][cur.x] = euclideanDistance(s,g);

//best-fit search algorithm//

while( !(cur == g) ) {

//update current point to being visited//

visited[cur.y][cur.x] = 1;

//neighbors of the current point//

point nb[4] = {

point(cur.x-1,cur.y,direction::L),

point(cur.x+1,cur.y,direction::R),

point(cur.x,cur.y-1,direction::U),

point(cur.x,cur.y+1,direction::D)

};

//calculate distances//

for(point cn : nb )

if( cn.inBounds() && maze[cn.y][cn.x] &&

(euclideanDistance(cn,g) + dist[cur.y][cur.x] + maze[cn.y][cn.x]

dist[cn.y][cn.x] = euclideanDistance(cn,g) + dist[cur.y][cur.x] + maze[cn.y][cn.x];

paths[cn.y][cn.x] = paths[cur.y][cur.x], paths[cn.y][cn.x].push_back(cur);

}

//select point of next iteration//

cur = point(-1,-1);

float md = INT_MAX;

for(int i=0; i

for(int j=0; j

if(!visited[i][j] && dist[i][j]!=INT_MAX && dist[i][j]

} //return path from start to goal//

paths[g.y][g.x].push_back(g);

return paths[g.y][g.x];

}

程序中首先初始化程序中首先初始化了距离（dist），访问（visited）和路径（paths）三个二维数组。

将目前所在点cur设置为起点s，并将cur点对应得距离（dist）设置为起点到终点的欧式距离（euclideanDistance）。

现在 A*开始走迷宫。‍♂️⭐️

在每次迭代的过程中，将cur点对应得 visited 数组的值设置为1，然后计算终点到 cur 点的相邻点的距离。这个距离等于，将 cur 点对应的 dist 值加上邻居点对应的 dist 的值然后再加上 cur 邻居点到终点的距离。如果计算出来的距离小于当前邻居点对应得的dist 数组的值，则将其值更新为新计算的值。

最后一步：选择下一步的移动。 选择邻居点中，可到达的、未访问过的且距离值（dist）最小的点。

算法完成：当点cur在目标点g时。

注意，A*是Dijkstra的算法+启发式算法。有关实现Dijkstra算法的更明确的步骤，可以查看以下网址。

https://towardsdatascience.com/graphs-paths-dijkstra-4d8b356ad6fa

现在可以将这些代码合并。

1.复制代码到文本编辑器中，保存为main.cpp

2. 从命令行编译，g++ main.cpp -std=c++11 -o Astar.exe

3. 然后从命令行执行代码，./Astar.exe

编译并执行源代码后，程序将生成随机迷宫，然后找到从开始到目标的路径。

完整C++代码：

https://github.com/DavidPynes/Tutorials/blob/master/Graphs/Graph_02/main.cpp

用A*算法走出迷宫：

https://davidpynes.github.io/Tutorials/Graphs/Graph_02/

翻译：张朔

审校：奔跑的笤帚把子

编辑：Yiri

原文：

https://towardsdatascience.com/graphs-paths-a-getting-out-of-a-maze-a3d7c079a5c6

关注集智AI学园公众号

获取更多更有趣的AI教程吧！

搜索微信公众号：swarmAI

学园网站：campus.swarma.org

商务合作和投稿转载｜swarma@swarma.org