脫離迷宮的搜索演算法
6 人贊了文章
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
1.深度優先搜索演算法
DFS考慮所有相鄰路徑，並且徑直向目標移動。在這種方法中，該演算法沒有任何遠見，無法避免前方只有幾步遠的「L」形牆。
火柴人不斷向右上方移動，離目標越來越近。這個DFS演算法進入到了牆的拐角處，現在它需要繞著牆的走，這也導致了不必要的步驟。
一個更有效的方法是找到一個能迴避「L」形牆的整體路線，但是這個必須在第一步的時候就向右下方或者左上方移動。
因為這些移動不是接近目標的直接路徑，所以這些路徑不在深度優先演算法的考慮範圍之內。
2.廣度優先搜索演算法
不像DFS方法，BFS方法會找到圖上的所有路徑。
BFS方法會發現第一步中所有可能的相鄰路徑，然後發現第二步的，然後是第三步的，等等。
BFS方法會找到很多路徑，但是不能找到一個特定的路徑。
用BFS來找到一個特定的路徑需要探索很多不必要的路徑。因此，如果我們需要到達一個特定的地點，用BFS方法並不是理想的。
3.最佳優先搜索演算法
A*演算法是最佳優先演算法（best-first）的一種,不僅計算相鄰路徑的距離，也計算目標的距離。其結果便是一種經過深度導引的廣度優先搜索。
所以，現在，搜索路徑的廣度以目標距離為導引。
這個演算法最終的目的是離目標越來越近，但是也希望探索出許多的路徑，只要這些路徑和目標的大概方向一致。
注意，最佳優先搜索方法迴避了「L」形牆並且也避免了非目標方向。
當在迷宮中應用A*演算法時，小人兒通常會朝著目標向右下方移動，但是也會向右上方或者左下方移動來迴避障礙物。
How
A*演算法這種最佳優先演算法, 是Dijkstra的演算法加上對距離的計算。
讓我們先來定義迷宮的一些特徵，例如高度，寬度和點。（譯者註：在這裡表述成點而不是方塊兒，因為在實際操作中可以是三角形或者其它形狀，所以統一表述成點。）高度，寬度和點：#define HEIGHT 25#define WIDTH 25enum struct direction {L,R,U,D};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<WIDTH && y>=0 && y<HEIGHT ) ? 1 : 0; } void print() { std::cout<<"{x: "<<x<<", y: "<<y<<"}
"; }; const bool operator==(const point& rhs) const { return ( x == rhs.x && y == rhs.y) ? 1 : 0; };};
高度和寬度都是數字。
{x, y}坐標代表點的位置，有時也用於表示移動的方向。這裡還有一些重要的細節。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));}
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); } }}
現在，點（point），歐式距離（euclideanDistance），隨機迷宮（randomMaze）都已經定義好了，現在對A*進行編程。
A*功能：std::vector<points> astar(int maze[HEIGHT][WIDTH],point s,point g) { //initialize sets// std::vector<point> paths[HEIGHT][WIDTH]; float dist[HEIGHT][WIDTH] = { 0 }; bool visited[HEIGHT][WIDTH] = { 0 }; for(int i=0; i<HEIGHT; i++) for(int j=0; j<WIDTH; 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]) ) { 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<HEIGHT; i++) for(int j=0; j<WIDTH; j++) if(!visited[i][j] && dist[i][j]!=INT_MAX && dist[i][j] < md) { cur = point(j,i), md = dist[i][j]; } } //return path from start to goal// paths[g.y][g.x].push_back(g); return paths[g.y][g.x]; }
現在 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.cpp2. 從命令行編譯，g++ main.cpp -std=c++11 -o Astar.exe3. 然後從命令行執行代碼，./Astar.exe編譯並執行源代碼後，程序將生成隨機迷宮，然後找到從開始到目標的路徑。
完整C++代碼：
https://github.com/DavidPynes/Tutorials/blob/master/Graphs/Graph_02/main.cpp用A*演算法走出迷宮：https://davidpynes.github.io/Tutorials/Graphs/Graph_02/翻譯：張朔審校：奔跑的笤帚把子原文：https://towardsdatascience.com/graphs-paths-a-getting-out-of-a-maze-a3d7c079a5c6關注集智AI學園公眾號
獲取更多更有趣的AI教程吧！搜索微信公眾號：swarmAI
集智AI學園QQ群：426390994學園網站：http://campus.swarma.org商務合作和投稿轉載｜[email protected]
推薦閱讀：
TAG:搜索演算法 | 深度學習DeepLearning | 人工智慧 |