网页应用示例
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
领取专属 10元无门槛券
私享最新 技术干货