前言
a*搜尋算法俗稱a星算法。這是一種在圖形平面上，有多個(gè)節(jié)點(diǎn)的路徑，求出最低通過成本的算法。常用于游戲中
通過二維數(shù)組構(gòu)建的一個(gè)迷宮，“%”表示墻壁，a為起點(diǎn)，b為終點(diǎn)，“#”代表障礙物，“*”代表算法計(jì)算后的路徑
本文實(shí)例代碼結(jié)構(gòu)：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
% % % % % % % % o o o o o % % o o # o o % % a o # o b % % o o # o o % % o o o o o % % % % % % % % ============================= 經(jīng)過a*算法計(jì)算后 ============================= % % % % % % % % o o * o o % % o * # * o % % a o # o b % % o o # o o % % o o o o o % % % % % % % % < |
算法理論
算法的核心公式為：f=g+h
把地圖上的節(jié)點(diǎn)看成一個(gè)網(wǎng)格。
g=從起點(diǎn)a,沿著產(chǎn)生的路徑，移動(dòng)到網(wǎng)格上指定節(jié)點(diǎn)的移動(dòng)消耗，在這個(gè)例子里，我們令水平或者垂直移動(dòng)的耗費(fèi)為10，對(duì)角線方向耗費(fèi)為14。我們?nèi)∵@些值是因?yàn)檠貙?duì)角線
的距離是沿水平或垂直移動(dòng)耗費(fèi)的的根號(hào)2，或者約1.414倍。為了簡(jiǎn)化，我們用10和14近似。
既然我們?cè)谟?jì)算沿特定路徑通往某個(gè)方格的g值，求值的方法就是取它父節(jié)點(diǎn)的g值，然后依照它相對(duì)父節(jié)點(diǎn)是對(duì)角線方向或者直角方向(非對(duì)角線)，分別增加14和10。例子中這
個(gè)方法的需求會(huì)變得更多，因?yàn)槲覀儚钠瘘c(diǎn)方格以外獲取了不止一個(gè)方格。
h=從當(dāng)前格移動(dòng)到終點(diǎn)b的預(yù)估移動(dòng)消耗。為什么叫”預(yù)估“呢，因?yàn)槲覀儧]有辦法事先知道路徑的長(zhǎng)度，這里我們使用曼哈頓方法，它計(jì)算從當(dāng)前格到目的格之間水平和垂直
的方格的數(shù)量總和，忽略對(duì)角線方向。然后把結(jié)果乘以10。
f的值是g和h的和，這是我們用來判斷優(yōu)先路徑的標(biāo)準(zhǔn)，f值最小的格，我們認(rèn)為是優(yōu)先的路徑節(jié)點(diǎn)。
實(shí)現(xiàn)步驟
算法使用java寫的，先看一看節(jié)點(diǎn)類的內(nèi)容
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
|
package a_star_search; /** * 節(jié)點(diǎn)類 * @author zx * */public class node { private int x; //x坐標(biāo) private int y; //y坐標(biāo) private string value; //表示節(jié)點(diǎn)的值 private double fvalue = 0; //f值 private double gvalue = 0; //g值 private double hvalue = 0; //h值 private boolean reachable; //是否可到達(dá)（是否為障礙物） private node pnode; //父節(jié)點(diǎn) public node(int x, int y, string value, boolean reachable) { super(); this.x = x; this.y = y; this.value = value; reachable = reachable; } public node() { super(); } public int getx() { return x; } public void setx(int x) { this.x = x; } public int gety() { return y; } public void sety(int y) { this.y = y; } public string getvalue() { return value; } public void setvalue(string value) { this.value = value; } public double getfvalue() { return fvalue; } public void setfvalue(double fvalue) { fvalue = fvalue; } public double getgvalue() { return gvalue; } public void setgvalue(double gvalue) { gvalue = gvalue; } public double gethvalue() { return hvalue; } public void sethvalue(double hvalue) { hvalue = hvalue; } public boolean isreachable() { return reachable; } public void setreachable(boolean reachable) { reachable = reachable; } public node getpnode() { return pnode; } public void setpnode(node pnode) { pnode = pnode; } } |
還需要一個(gè)地圖類，在map的構(gòu)造方法中，我通過創(chuàng)建節(jié)點(diǎn)的二維數(shù)組來實(shí)現(xiàn)一個(gè)迷宮地圖，其中包括起點(diǎn)和終點(diǎn)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
|
package a_star_search;public class map { private node[][] map; //節(jié)點(diǎn)數(shù)組 private node startnode; //起點(diǎn) private node endnode; //終點(diǎn) public map() { map = new node[7][7]; for (int i = 0;i<7;i++){ for (int j = 0;j<7;j++){ map[i][j] = new node(i,j,"o",true); } } for (int d = 0;d<7;d++){ map[0][d].setvalue("%"); map[0][d].setreachable(false); map[d][0].setvalue("%"); map[d][0].setreachable(false); map[6][d].setvalue("%"); map[6][d].setreachable(false); map[d][6].setvalue("%"); map[d][6].setreachable(false); } map[3][1].setvalue("a"); startnode = map[3][1]; map[3][5].setvalue("b"); endnode = map[3][5]; for (int k = 1;k<=3;k++){ map[k+1][3].setvalue("#"); map[k+1][3].setreachable(false); } } <span style="white-space:pre"> </span>//展示地圖 public void showmap(){ for (int i = 0;i<7;i++){ for (int j = 0;j<7;j++){ system.out.print(map[i][j].getvalue()+" "); } system.out.println(""); } } public node[][] getmap() { return map; } public void setmap(node[][] map) { this.map = map; } public node getstartnode() { return startnode; } public void setstartnode(node startnode) { this.startnode = startnode; } public node getendnode() { return endnode; } public void setendnode(node endnode) { this.endnode = endnode; }} |
下面是最重要的astar類
操作過程
1從起點(diǎn)a開始，并且把它作為待處理點(diǎn)存入一個(gè)“開啟列表”，這是一個(gè)待檢查方格的列表。
2尋找起點(diǎn)周圍所有可到達(dá)或者可通過的方格，跳過無法通過的方格。也把他們加入開啟列表。為所有這些方格保存點(diǎn)a作為“父方格”。當(dāng)我們想描述路徑的時(shí)候，父方格的資
料是十分重要的。后面會(huì)解釋它的具體用途。
3從開啟列表中刪除起點(diǎn)a，把它加入到一個(gè)“關(guān)閉列表”，列表中保存所有不需要再次檢查的方格。
經(jīng)過以上步驟，“開啟列表”中包含了起點(diǎn)a周圍除了障礙物的所有節(jié)點(diǎn)。他們的父節(jié)點(diǎn)都是a,通過前面講的f=g+h的公式，計(jì)算每個(gè)節(jié)點(diǎn)的g，h，f值，并按照f的值大小，從小
到大進(jìn)行排序。并對(duì)f值最小的那個(gè)節(jié)點(diǎn)做以下操作
4，把它從開啟列表中刪除，然后添加到關(guān)閉列表中。
5，檢查所有相鄰格子。跳過那些不可通過的(1.在”關(guān)閉列表“中，2.障礙物)，把他們添加進(jìn)開啟列表，如果他們還不在里面的話。把選中的方格作為新的方格的父節(jié)點(diǎn)。
6，如果某個(gè)相鄰格已經(jīng)在開啟列表里了，檢查現(xiàn)在的這條路徑是否更好。換句話說，檢查如果我們用新的路徑到達(dá)它的話，g值是否會(huì)更低一些。如果不是，那就什么都不
做。（這里，我的代碼中并沒有判斷）
7，我們重復(fù)這個(gè)過程，直到目標(biāo)格（終點(diǎn)“b”）被添加進(jìn)“開啟列表”，說明終點(diǎn)b已經(jīng)在上一個(gè)添加進(jìn)“關(guān)閉列表”的節(jié)點(diǎn)的周圍，只需走一步，即可到達(dá)終點(diǎn)b。
8，我們將終點(diǎn)b添加到“關(guān)閉列表”
9，最后一步，我們要將從起點(diǎn)a到終點(diǎn)b的路徑表示出來。父節(jié)點(diǎn)的作用就顯示出來了，通過“關(guān)閉列表”中的終點(diǎn)節(jié)點(diǎn)的父節(jié)點(diǎn)，改變其value值，順藤摸瓜即可以顯示出路徑。
看看代碼
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
|
package a_star_search;import java.util.arraylist;public class astar { /** * 使用arraylist數(shù)組作為“開啟列表”和“關(guān)閉列表” */ arraylist<node> open = new arraylist<node>(); arraylist<node> close = new arraylist<node>(); /** * 獲取h值 * @param currentnode：當(dāng)前節(jié)點(diǎn) * @param endnode：終點(diǎn) * @return */ public double gethvalue(node currentnode,node endnode){ return (math.abs(currentnode.getx() - endnode.getx()) + math.abs(currentnode.gety() - endnode.gety()))*10; } /** * 獲取g值 * @param currentnode：當(dāng)前節(jié)點(diǎn) * @return */ public double getgvalue(node currentnode){ if(currentnode.getpnode()!=null){ if(currentnode.getx()==currentnode.getpnode().getx()||currentnode.gety()==currentnode.getpnode().gety()){ //判斷當(dāng)前節(jié)點(diǎn)與其父節(jié)點(diǎn)之間的位置關(guān)系（水平？對(duì)角線） return currentnode.getgvalue()+10; } return currentnode.getgvalue()+14; } return currentnode.getgvalue(); } /** * 獲取f值 ： g + h * @param currentnode * @return */ public double getfvalue(node currentnode){ return currentnode.getgvalue()+currentnode.gethvalue(); } /** * 將選中節(jié)點(diǎn)周圍的節(jié)點(diǎn)添加進(jìn)“開啟列表” * @param node * @param map */ public void inopen(node node,map map){ int x = node.getx(); int y = node.gety(); for (int i = 0;i<3;i++){ for (int j = 0;j<3;j++){ //判斷條件為：節(jié)點(diǎn)為可到達(dá)的（即不是障礙物，不在關(guān)閉列表中），開啟列表中不包含，不是選中節(jié)點(diǎn) if(map.getmap()[x-1+i][y-1+j].isreachable()&&!open.contains(map.getmap()[x-1+i][y-1+j])&&!(x==(x-1+i)&&y==(y-1+j))){ map.getmap()[x-1+i][y-1+j].setpnode(map.getmap()[x][y]); //將選中節(jié)點(diǎn)作為父節(jié)點(diǎn) map.getmap()[x-1+i][y-1+j].setgvalue(getgvalue(map.getmap()[x-1+i][y-1+j])); map.getmap()[x-1+i][y-1+j].sethvalue(gethvalue(map.getmap()[x-1+i][y-1+j],map.getendnode())); map.getmap()[x-1+i][y-1+j].setfvalue(getfvalue(map.getmap()[x-1+i][y-1+j])); open.add(map.getmap()[x-1+i][y-1+j]); } } } } /** * 使用冒泡排序?qū)㈤_啟列表中的節(jié)點(diǎn)按f值從小到大排序 * @param arr */ public void sort(arraylist<node> arr){ for (int i = 0;i<arr.size()-1;i++){ for (int j = i+1;j<arr.size();j++){ if(arr.get(i).getfvalue() > arr.get(j).getfvalue()){ node tmp = new node(); tmp = arr.get(i); arr.set(i, arr.get(j)); arr.set(j, tmp); } } } } /** * 將節(jié)點(diǎn)添加進(jìn)”關(guān)閉列表“ * @param node * @param open */ public void inclose(node node,arraylist<node> open){ if(open.contains(node)){ node.setreachable(false); //設(shè)置為不可達(dá) open.remove(node); close.add(node); } } public void search(map map){ //對(duì)起點(diǎn)即起點(diǎn)周圍的節(jié)點(diǎn)進(jìn)行操作 inopen(map.getmap()[map.getstartnode().getx()][map.getstartnode().gety()],map); close.add(map.getmap()[map.getstartnode().getx()][map.getstartnode().gety()]); map.getmap()[map.getstartnode().getx()][map.getstartnode().gety()].setreachable(false); map.getmap()[map.getstartnode().getx()][map.getstartnode().gety()].setpnode(map.getmap()[map.getstartnode().getx()][map.getstartnode().gety()]); sort(open); //重復(fù)步驟 do{ inopen(open.get(0), map); inclose(open.get(0), open); sort(open); } while(!open.contains(map.getmap()[map.getendnode().getx()][map.getendnode().gety()])); //知道開啟列表中包含終點(diǎn)時(shí)，循環(huán)退出 inclose(map.getmap()[map.getendnode().getx()][map.getendnode().gety()], open); showpath(close,map); } /** * 將路徑標(biāo)記出來 * @param arr * @param map */ public void showpath(arraylist<node> arr,map map) { if(arr.size()>0){ node node = new node(); //<span style="white-space:pre"> </span>node = map.getmap()[map.getendnode().getx()][map.getendnode().gety()]; //<span style="white-space:pre"> </span>while(!(node.getx() ==map.getstartnode().getx()&&node.gety() ==map.getstartnode().gety())){ //<span style="white-space:pre"> </span>node.getpnode().setvalue("*"); //<span style="white-space:pre"> </span>node = node.getpnode(); //<span style="white-space:pre"> </span>} } //<span style="white-space:pre"> </span>map.getmap()[map.getstartnode().getx()][map.getstartnode().gety()].setvalue("a"); }} |
最后寫一個(gè)main方法
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
package a_star_search; public class maintest { public static void main(string[] args) { map map = new map(); astar astar = new astar(); map.showmap(); astar.search(map); system.out.println("============================="); system.out.println("經(jīng)過a*算法計(jì)算后"); system.out.println("============================="); map.showmap(); } } |
修改地圖再測(cè)試一下，看看效果
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
% % % % % % % % o o o o o % % o o # o o % % a o # o b % % o o # o o % % o o o o o % % % % % % % % =============================經(jīng)過a*算法計(jì)算后=============================% % % % % % % % o o o o o % % o o # o o % % a o # o b % % o o # o o % % o o o o o % % % % % % % % |
總結(jié)
保證找到最短路徑（最優(yōu)解的）條件，關(guān)鍵在于估價(jià)函數(shù)h(n)的選取：估價(jià)值h(n)<=n到目標(biāo)節(jié)點(diǎn)的距離實(shí)際值，這種情況下，搜索的點(diǎn)數(shù)多，搜索范圍大，效率低。但能得到
最優(yōu)解。如果估價(jià)值>實(shí)際值,搜索的點(diǎn)數(shù)少，搜索范圍小，效率高，但不能保證得到最優(yōu)解。
最大的感觸就是：做事最忌三天打漁，兩天曬網(wǎng)。量可以不大，但必須有連續(xù)性，貴在堅(jiān)持。
希望每一個(gè)程序員，都能開心的敲著代碼，做自己喜歡做的事。
以上就是本文關(guān)于java編程實(shí)現(xiàn)a*算法完整代碼的全部?jī)?nèi)容，希望對(duì)大家有所幫助。感興趣的朋友可以繼續(xù)參閱本站其他相關(guān)專題，如有不足之處，歡迎留言指出。
原文鏈接：http://blog.csdn.net/u014735301/article/details/40039595
