学习
实践
活动
工具
TVP
写文章

脱离迷宫的搜索算法

网页应用示例

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

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180722G1E3HL00?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

扫码关注腾讯云开发者

领取腾讯云代金券