一.算法原理

A* 算法，就是解決在一個平面 grid地圖中尋找起點到終點的最短路徑問題的算法，類似于Dijkstra算法和BFS算法一樣，屬于廣度優(yōu)先搜索。實際上它還是一個啟發(fā)式搜索算法，什么叫啟發(fā)式搜索算法？不同于BFS和DFS在子節(jié)點選擇上其實是盲目的，啟發(fā)式搜索就是利用評估函數(shù)在平面中對所有的待搜索點進行評估，找出最佳的搜索點問題。那么A* 算法是如何利用這些思想的呢？

1.評估函數(shù)

對于地圖中的每一個點，都有一個評估標準值F，評估函數(shù)為：F= G+H

而G表示的是從起點到現(xiàn)在所在方格的總代價，計算G我們通常采用搜索樹的深度，及此節(jié)點的上一個節(jié)點G+1來計算，源點本身G=0；

H代表著從當前點到目的地點的預計代價，計算H我們通常采用“曼哈端距離算法”（譯注：Manhattan distance method），這個算法僅僅只是計算了當前點到終點的水平方向和豎直方向上的方格數(shù)，而沒有將障礙物或不同地形考慮進來。 如果你在游戲中采用此算法，則需要注意將地形的情況考慮到H的計算之中，假設是在grid地圖中，目的地坐標(4,4)，當前坐標(0,0)，當前坐標的$H=8$

2.待測點與已測點的存儲

我們使用closeList(閉表)來儲存那些我們被探測過的點和障礙點，當我們的終點被加入closeList中的時候，意味著我們已經(jīng)得到最短路徑，我們停止擴散搜索。
我們使用openList(開表)來記錄我們的待測點，我們通常將當前點A的上下左右（其他的斜角方向是否考慮在內(nèi)處于你的要求）中的那些沒有被搜索過且不為障礙點的節(jié)點加入到openList中，同時設置這些點的parent引用指向當前節(jié)點A，用于記錄路徑，便于最后輸出路徑，并設置他們的F= H + G，H根據(jù)此節(jié)點的實際情況進行計算，G取當前節(jié)點A的G再加1，如果這些點中有的已經(jīng)加入到openList中，我們將他的F值與根據(jù)節(jié)點A計算的F進行比較，如果新計算的評估值F小，我們就更新那個節(jié)點的F值。每次從開表中選擇評估值F最小的點，使每一次的搜索點為最優(yōu)點。

偽代碼：

closeList:= set contains barriers nodes at the beginning openList:= set contains the source node at the beginningwhile(!openList isEmpty())node = get_node_with_minF(openList)if(node == end_node)getPathTo(end_node)breakfor(each neighbor node的相鄰節(jié)點)//如果相鄰節(jié)點在閉表中，直接跳過if(neighbor in closeList)continue//計算相鄰節(jié)點的H和Gint G = node.G + 1int H = calcuH_from_neighbor_to_end(neighbor, end)//已在開表中，需要更新if(neighbor in openList)if(neighbor.F > G + H)neighbor.F = G+Hneighbor.parent = nodeelseneighbor.F = G+Hneighbor.parent = nodeopenList.add(neighbor)openList.remove(node)closeList.add(node)

二.算法實現(xiàn)

package com.example.astar;import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; import java.util.List;/*** @author 玄木.*/ public class AStar {private Node source;private Node end;private List<Node> openList;private List<Node> closeList;/**** @param map 0:for source node, 1:for nothing, 2:for barriers, 3:for end node, 4:for path* @return the path from source to end* @throws NotFoundException*/public void aStar(int[][] map) throws NotFoundException{//異常處理if(map.length==0||map[0].length==0){throw new NotFoundException("parameters invalid");}init(map);while(!openList.isEmpty()){Node node = getNodeWithMinF(openList);if(node.equals(end)){for(Node tmp : getPathTo(node)){map[tmp.y][tmp.x] = 4;}printMap(map);return;}for(Node neighbor : getNeighbors(node, map)){if (closeList.contains(neighbor)){continue;}int G = node.getG() + 1;int H = calcuH(neighbor, end);if(openList.contains(neighbor)) {if (neighbor.getF() > G + H) {neighbor.setG(G);neighbor.setH(H);neighbor.setF(G + H);neighbor.setParent(node);}}else{neighbor.setG(G);neighbor.setH(H);neighbor.setF(G + H);neighbor.setParent(node);openList.add(neighbor);}}openList.remove(node);closeList.add(node);}throw new NotFoundException("not found");}/*** init the openList,closeList,source,end node* @param map*/public void init(int[][] map){openList = new ArrayList<Node>();closeList = new ArrayList<Node>();for(int row=0;row<map.length;row++){for(int column=0;column<map[0].length;column++){//add the barriers nodes to the closeListif(map[row][column]==2){closeList.add(new Node(column, row));}else if(map[row][column]==1){source = new Node(column, row);}else if(map[row][column]==3){end = new Node(column, row);}}}source.setG(0);source.setH(calcuH(source, end));source.setF(source.getG()+source.getH());openList.add(source);}/*** return the path from source node to end node* @param end* @return*/public List<Node> getPathTo(Node end){List<Node> pathTo = new ArrayList<Node>();Node temp = end;while(temp!=null){pathTo.add(temp);temp = temp.parent;}Collections.reverse(pathTo);return pathTo;}/*** get neighbors of node* @param node* @param map* @return*/public List<Node> getNeighbors(Node node, int[][] map){List<Node> list = new ArrayList<Node>();if(node.x>0 && node.x<map[0].length-1){list.add(new Node(node.x-1,node.y));list.add(new Node(node.x+1,node.y));}else if(node.x == 0){list.add(new Node(node.x+1,node.y));}else{list.add(new Node(node.x-1,node.y));}if(node.y>0 && node.y<map.length-1){list.add(new Node(node.x,node.y+1));list.add(new Node(node.x,node.y-1));}else if(node.y == 0){list.add(new Node(node.x,node.y+1));}else{list.add(new Node(node.x,node.y-1));}return list;}/*** calculate H* @param node* @param end* @return*/public int calcuH(Node node, Node end){return Math.abs(node.x-end.x)+Math.abs(node.y-end.y);}/*** get the node with minimum F in openList* @param list* @return*/public Node getNodeWithMinF(List<Node> list){Collections.sort(list, Comparator.comparingInt(o -> o.F));return list.get(0);}/*** print the map* @param map*/public void printMap(int[][] map){int row=0,column=0;for(row=0;row<map.length;row++){for (column=0;column<map[0].length;column++){switch (map[row][column]){case 0:System.out.print("[]");break;case 2:System.out.print("##");break;case 1:case 3:System.out.print("@@");break;case 4:System.out.print("->");break;default:break;}}System.out.println();}System.out.println();}/*** static inner class Node*/public static class Node{private int x;private int y;private int G;private int H;private int F;private Node parent;public Node(int x, int y){this.x = x;this.y = y;this.G = 0;this.H = 0;this.F = Integer.MAX_VALUE;this.parent = null;}@Overridepublic boolean equals(Object obj) {if(obj instanceof Node){Node other = (Node)obj;return other.x==this.x && other.y==this.y;}return false;}public int getG() {return G;}public void setG(int g) {G = g;}public int getH() {return H;}public void setH(int h) {H = h;}public int getF() {return F;}public void setF(int f) {F = f;}public Node getParent() {return parent;}public void setParent(Node parent) {this.parent = parent;}}/*** static inner Exception class*/public static class NotFoundException extends Exception{public NotFoundException(String mess) {super(mess);}} }

三.實驗測試

1. 基礎測試

@Testpublic void aStarTest(){int[][] map = {{0, 0, 0, 0, 0, 0, 2, 0, 0, 0},{1, 0, 0, 0, 0, 0, 2, 0, 0, 0},{0, 0, 0, 0, 0, 2, 2, 0, 0, 0},{0, 0, 2, 0, 2, 2, 2, 0, 0, 0},{0, 0, 0, 0, 0, 2, 2, 0, 0, 0},{0, 0, 2, 0, 0, 2, 0, 0, 0, 0},{0, 0, 2, 0, 0, 2, 0, 0, 0, 0},{0, 0, 2, 0, 0, 2, 0, 0, 0, 0},{0, 0, 2, 0, 2, 0, 0, 0, 0, 0},{0, 0, 0, 0, 0, 0, 2, 0, 0, 3},};try {aStar.printMap(map);aStar.aStar(map);}catch (AStar.NotFoundException e){e.printStackTrace();}}

[]表示可以行走的空地
##表示障礙
->表示路徑
@ 表示起點和終點

實驗結果

測試通過

2.異常測試

@Testpublic void aStarTest(){int[][] map = {{0, 0, 0, 0, 0, 0, 2, 0, 0, 0},{1, 0, 0, 0, 0, 0, 2, 0, 0, 0},{0, 0, 0, 0, 0, 2, 2, 0, 0, 0},{0, 0, 0, 0, 0, 2, 2, 0, 0, 0},{0, 0, 0, 0, 0, 2, 2, 0, 0, 0},{0, 0, 2, 0, 0, 2, 0, 0, 0, 0},{0, 0, 2, 0, 0, 2, 0, 0, 0, 0},{0, 0, 2, 0, 0, 2, 0, 0, 0, 0},{0, 0, 2, 0, 0, 0, 2, 0, 0, 0},{0, 0, 0, 0, 0, 0, 2, 0, 0, 3},};try {aStar.printMap(map);aStar.aStar(map);}catch (AStar.NotFoundException e){e.printStackTrace();}}

實驗結果

測試通過

---

你可能還敢興趣的圖論算法(均附Java實現(xiàn)代碼)：

• 算法實驗–主函數(shù)只有五行的Floyed的算法以及最短路徑輸出

• 你必須會的–Dijkstra算法–單源最短路徑問題

• 你必須會的DFS的遞歸實現(xiàn)與堆棧實現(xiàn)

• 你了解歐拉回路嗎？

總結

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

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