最短路徑算法：

? A*算法擅長解決靜態(tài)路徑中最短距離問題，而又不同于Dijkstra算法和Floyd算法，該算法綜合了BFS和Dijkstra算法優(yōu)點：在進行啟發(fā)式搜索提高算法效率的同時，可以保證找到一條最優(yōu)路徑(基于評估函數(shù)，例如：曼哈頓距離、歐式距離)，Floyd算法更多地使用場景在于機器人路徑規(guī)劃、游戲規(guī)劃、衛(wèi)星路徑探尋等領域。

A*算法與最短路徑計算：

對于地理環(huán)境中的一個固定地面位置，它至少可以被標記為兩種狀態(tài)跟：可使用區(qū)、不可使用區(qū)(障礙區(qū))，同時可以把該固定位置視為九宮格里面的中心點。

可以確定該中心點的移動方向包含8個：上下左右，左上、右上、左下、右下，因此A*算法的尋路流程可以通過三個步驟完成。

1.從中心點開始，把它放入一個待計算的開放列表，開放列表可以理解成一個準備進行路徑分析的隊列。

2.尋找中心點周圍可達到的方格集，這些方格的狀態(tài)需要是可以使用的，將這些方格的來源都標記為中心點。

3.在開放列表中移除剛剛分析的中心點，將該中心點放入關閉列表中，關閉列表表示后續(xù)不再對該表進行可達路徑分析。

通過3步已經(jīng)完成了開放列表的獲取，但是如何從開放列表中選擇下一步的移動方格是A*算法思想中最核心的內容。A*算法利用公式f(n)=g(n)+h(n)篩選下一步移動方格，其中，g(n)代表從起初開始的方格移動當當前方格的移動距離；h(n)表示從即將移動到的方格到終點方格的距離，兩者相加得到f(n)即為當前預估的可能路徑，這種可能路徑中最小的值對應的方格即為當前可以從開放列表中選擇的下一步移動方格，選擇該方格之后再依次重復上述步驟，知道鄰近的方格中存在終點方格(或終點方格進入了開放列表)‘

上述步驟中g(n)和h(n)是獲取A*計算計算的關鍵值

1.g(n)的計算

g(n)定義的是起點方格到當前方格的距離，從方格不同位置移動多產生的距離，在實際應用中，每個方向的距離都有可能不同，g(n)則是從起點方格開始通過不斷的方位移動累計的距離和。

2.h(n)的計算

h(n)是對當前方格到目的地方格距離的估算，估算方法：

常見的距離計算公式有這么幾種：

1、曼哈頓距離：這個名字聽起來好高端，說白了，就是上面我們講的橫向格子數(shù)+縱向格子數(shù)；

2、歐式距離：這個名字聽起來也很高端，說白了，就是兩點間的直線距離sqrt((x1-x2)2?+ (y1-y2)2)

算法源碼：

Main.java:

package com.simplemain.astar;public class Main {// 地圖元素static final char START = 'S'; // 起點static final char END = 'E'; // 終點static final char SPACE = '.'; // 空地static final char WALL = 'W'; // 墻static final char VISITED = '-'; // 被訪問過static final char ON_PATH = '@'; // 在結果路徑上// 地圖字符串static final String[] S_MAP = {". . . . . . . . . . . . . . . . . . . .", ". . . W W W W . . . . . . . . . . . . .",". . . . . . W . . . . . . . . . . . . .", ". . . . . . W . . . . . . . . . . . . .", ". . S . . . W . . . . . . . . . . . . .", ". . . . . . W . . . . . . . . . . . . .", ". . . . . . W . . . . . . . . . . . . .", ". . . . . . W . . . . . . . . . . . . .", ". . . W W W W . . . . . . . . . . . . .", ". . . . . . . . . . . . . . . . . E . ."};// 地圖static char[][] MAP = new char[S_MAP[0].replace(" ", "").length()][S_MAP.length];// 地圖最大尺寸static Point MAX_PNT = new Point(MAP.length, MAP[0].length);// 起點static Point START_PNT = null;// 終點static Point END_PNT = null;public static void main(String[] args){genMap();printMap();search();printMap();}/*** 用地圖字符串產生地圖數(shù)據(jù)*/static void genMap(){int idx = 0;for (String s : S_MAP){char[] cs = s.replace(" ", "").toCharArray();for (int i = 0; i < cs.length; i++){MAP[i][idx] = cs[i];switch (cs[i]){case START:START_PNT = new Point(i, idx);break;case END:END_PNT = new Point(i, idx);break;}}idx++;}}/*** 打印地圖*/static void printMap(){for (int j = 0; j < MAX_PNT.y; j++){for (int i = 0; i < MAX_PNT.x; i++){System.out.printf("%c ", MAP[i][j]);}System.out.printf("\n");}System.out.printf("\n");}/*** 搜索算法*/static void search(){final MinHeap heap = new MinHeap(); // 用最小堆來記錄擴展的點final int[][] directs = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; // 可以擴展的四個方向heap.add(new Data(START_PNT, 0, 0, null)); // 把起始點放入堆Data lastData = null; // 找到的最后一個點的數(shù)據(jù),用來反推路徑for (boolean finish = false; !finish && !heap.isEmpty(); ){final Data data = heap.getAndRemoveMin(); // 取出f值最小的點final Point point = data.point;if (MAP[point.x][point.y] == SPACE) // 將取出的點標識為已訪問點{MAP[point.x][point.y] = VISITED;}for (int[] d : directs) // 遍歷四個方向的點{final Point newPnt = new Point(point.x + d[0], point.y + d[1]);if (newPnt.x >= 0 && newPnt.x < MAX_PNT.x && newPnt.y >= 0 && newPnt.y < MAX_PNT.y){char e = MAP[newPnt.x][newPnt.y];if (e == END) // 如果是終點,則跳出循環(huán),不用再找{lastData = data;finish = true;break;}if (e != SPACE) // 如果不是空地,就不需要再擴展{continue;}final Data inQueueData = heap.find(newPnt);if (inQueueData != null) // 如果在堆里,則更新g值{if (inQueueData.g > data.g + 1){inQueueData.g = data.g + 1;inQueueData.parent = data;}}else // 如果不在堆里,則放入堆中{double h = h(newPnt);Data newData = new Data(newPnt, data.g + 1, h, data);heap.add(newData);}}}}// 反向找出路徑for (Data pathData = lastData; pathData != null; ) {Point pnt = pathData.point;if (MAP[pnt.x][pnt.y] == VISITED){MAP[pnt.x][pnt.y] = ON_PATH;}pathData = pathData.parent;}}/*** h函數(shù)*/static double h(Point pnt){ // return hBFS(pnt);return hEuclidianDistance(pnt); // return hPowEuclidianDistance(pnt); // return hManhattanDistance(pnt);}/*** 曼哈頓距離,小于等于實際值*/static double hManhattanDistance(Point pnt){return Math.abs(pnt.x - END_PNT.x) + Math.abs(pnt.y - END_PNT.y);}/*** 歐式距離,小于等于實際值*/static double hEuclidianDistance(Point pnt){return Math.sqrt(Math.pow(pnt.x - END_PNT.x, 2) + Math.pow(pnt.y - END_PNT.y, 2));}/*** 歐式距離平方,大于等于實際值*/static double hPowEuclidianDistance(Point pnt){return Math.pow(pnt.x - END_PNT.x, 2) + Math.pow(pnt.y - END_PNT.y, 2);}/*** BFS的h值,恒為0*/static double hBFS(Point pnt){return 0;}}

MinHeap.java:

package com.simplemain.astar;import java.util.ArrayList; import java.util.HashMap; import java.util.Map;public class MinHeap {private final ArrayList<Data> queue = new ArrayList<>();private int endPnt = 0;private final Map<String, Data> index = new HashMap<>();public Data getAndRemoveMin(){if (isEmpty()){return null;}Data head = queue.get(0);Data last = queue.get(endPnt - 1);queue.set(0, last);endPnt--;index.remove(getKey(head.point));topDown();return head;}public Data find(Point pnt){return index.get(getKey(pnt));}public void add(Data data){if (queue.size() > endPnt){queue.set(endPnt, data);}else{queue.add(data);}endPnt++;index.put(getKey(data.point), data);bottomUp();}public boolean isEmpty(){return endPnt <= 0;}private String getKey(Point pnt){return String.format("%d-%d", pnt.x, pnt.y);}private void topDown(){for (int cur = 0; cur < endPnt; ){int left = 2 * cur + 1;int right = 2 * cur + 2;Data dc = queue.get(cur);Data dl = left < endPnt ? queue.get(left) : null;Data dr = right < endPnt ? queue.get(right) : null;int next = -1;Data dn = dc;if (dl != null && dl.f() < dn.f()){next = left;dn = dl;}if (dr != null && dr.f() < dn.f()){next = right;dn = dr;}if (next >= 0 && next < endPnt){queue.set(next, dc);queue.set(cur, dn);cur = next;}else{break;}}}private void bottomUp(){for (int cur = endPnt - 1; cur >= 0; ){int parent = (cur - 1) / 2;if (parent < 0){break;}Data dc = queue.get(cur);Data dp = queue.get(parent);if (dc.f() < dp.f()){queue.set(parent, dc);queue.set(cur, dp);cur = parent;}else{break;}}} }

Point.java:

package com.simplemain.astar;public class Point {int x, y;Point(int x, int y){this.x = x;this.y = y;}public boolean equals(Object o){return o != null && o instanceof Point && ((Point)o).x == x && ((Point)o).y == y;} }

Data.java:

package com.simplemain.astar;public class Data {Point point;double g;double h;Data parent;public Data(Point p, double g, double h, Data parent){this.point = p;this.g = g;this.h = h;this.parent = parent;}double f(){return g + h;} }

gitHub代碼：https://github.com/simplemain/astar

代碼出自：https://blog.csdn.net/qq_41325698/article/details/81874529

總結

以上是生活随笔為你收集整理的A*算法启发式搜索的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。