A*算法
這是我寫(xiě)的第一篇有關(guān)A*算法的文章，寫(xiě)得比較簡(jiǎn)潔，我決定再寫(xiě)一篇蔓挖，補(bǔ)充一下對(duì)A*算法的理解。
A*算法的啟發(fā)函數(shù)：
f(n) = g(n) + h(n)
A*算法把Dijkstra算法（靠近初始點(diǎn)的結(jié)點(diǎn)）和BFS算法（靠近目標(biāo)點(diǎn)的結(jié)點(diǎn)）的信息塊結(jié)合起來(lái)馆衔。
g(n)表示從初始結(jié)點(diǎn)到任意結(jié)點(diǎn)n的實(shí)際代價(jià)
h(n)表示從結(jié)點(diǎn)n到目標(biāo)點(diǎn)的啟發(fā)式評(píng)估代價(jià)
啟發(fā)式函數(shù)
（1）h(n)=0瘟判，一種極端情況
如果h(n)=0，則只有g(shù)(n)起作用角溃，此時(shí)A*演變成Dijkstra算法拷获，這保證能找到最短路徑，但效率不到减细，因?yàn)榈貌坏絾l(fā)匆瓜。
（2）h(n)<實(shí)際代價(jià)
如果h(n)經(jīng)常都比從n移動(dòng)到目標(biāo)的實(shí)際代價(jià)小（或者相等）未蝌，則A*保證能找到一條最短路徑驮吱。h(n)越小，A*擴(kuò)展的結(jié)點(diǎn)越多树埠，運(yùn)行就越慢糠馆。
（3）h(n)=實(shí)際代價(jià)
如果h(n)精確地等于從n移動(dòng)到目標(biāo)的實(shí)際代價(jià)，則A*將會(huì)僅僅尋找最佳路徑而不擴(kuò)展別的任何結(jié)點(diǎn)怎憋，這會(huì)運(yùn)行得非秤致担快。盡管這不可能在所有情況下發(fā)生绊袋，你仍可以在一些特殊情況下讓它們精確地相等（指讓h(n)精確地等于實(shí)際代價(jià)）毕匀。只要提供完美的信息，A*就會(huì)運(yùn)行得很完美癌别。
（4）h(n)>實(shí)際代價(jià)
如果h(n)有時(shí)比從n移動(dòng)到目標(biāo)的實(shí)際代價(jià)大皂岔，則A*不能保證找到一條最短路徑，但它運(yùn)行得更快展姐。
（5）h(n)>>實(shí)際代價(jià)（>>遠(yuǎn)大于）躁垛，另一種極端情況
如果h(n)比g(n)大很多剖毯，則只有h(n)起作用，A*演變成BFS算法教馆。
實(shí)現(xiàn)Open集和Close集的數(shù)據(jù)結(jié)構(gòu)是什么逊谋？
數(shù)組？鏈表土铺？
在Open集上主要有三種操作：查找優(yōu)先級(jí)最高的結(jié)點(diǎn)&刪除結(jié)點(diǎn)胶滋、查找相鄰結(jié)點(diǎn)是否在集合中、插入新結(jié)點(diǎn)
在Close集上主要有兩種操作：查找相鄰結(jié)點(diǎn)是否在集合中悲敷、插入新節(jié)點(diǎn)
（1）未排序數(shù)組或鏈表
最簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)是未排序數(shù)組或鏈表究恤。查找結(jié)點(diǎn)，花費(fèi)O(N)后德；插入結(jié)點(diǎn)部宿，花費(fèi)O(1)；刪除結(jié)點(diǎn)探遵，花費(fèi)O(N)
（2）排序數(shù)組
為了加快刪除操作窟赏，可以對(duì)數(shù)組進(jìn)行排序。查找結(jié)點(diǎn)箱季，變成O(logN)涯穷，因?yàn)榭梢允褂谜郯氩檎遥徊迦虢Y(jié)點(diǎn)藏雏，花費(fèi)O(N)拷况；查找和刪除優(yōu)先級(jí)最高的結(jié)點(diǎn)，花費(fèi)O(1)
（3）排序鏈表
在排序數(shù)組中掘殴，插入操作很慢赚瘦。如果使用鏈表則可以加速該操作。查找結(jié)點(diǎn)奏寨，花費(fèi)O(N)起意；插入結(jié)點(diǎn)，花費(fèi)O(1)病瞳，但查找插入位置揽咕，需要花費(fèi)O(N)
（4）哈希表
使用哈希表，查找結(jié)點(diǎn)套菜，花費(fèi)O(1)亲善；插入結(jié)點(diǎn)，花費(fèi)O(1)逗柴；查找和刪除優(yōu)先級(jí)最高的結(jié)點(diǎn)蛹头，花費(fèi)O(N)
https://blog.csdn.net/coutamg/article/details/53923717#!/_alzvzu0wsphb4nstr5bbro1or
