1.簡(jiǎn)述
A星算法就是試圖在地圖中找到一條最短路徑猫态，但不保證一定存在。
- 任務(wù)
小貓去找青蛙玩（好TM弱智啊~） - 條件
黑色方塊無(wú)法通行，每走一個(gè)格子小貓消耗的體力都為1喜每。
2.如果說(shuō)你是小貓掷伙，你會(huì)怎么走是己？
嗯，毫無(wú)疑問(wèn)
你肯定這么走任柜。卒废。。很簡(jiǎn)單的對(duì)吧宙地，但是你這么走的時(shí)候摔认，真的沒(méi)經(jīng)過(guò)思考？并非如此吧宅粥，你要找最短路徑是不是直接連線是最快的参袱？但是連線有障礙物阻擋了，所以逼迫你先往上走出障礙物的區(qū)域秽梅，然后一路直線當(dāng)然就是最短路徑了抹蚀。
BUT，你所做的思考风纠，都是建立在你腦海里已經(jīng)有整張地圖的概念上况鸣，代碼是不知道地圖的，它要知道怎么走竹观，就是一步一步的探索镐捧，你的行為對(duì)于代碼來(lái)說(shuō)，那叫-未卜先知臭增！
3.基本概念
要實(shí)現(xiàn)A星算法懂酱，先要知道一些基本概念
- open列表
所謂open列表，我的理解是誊抛，知道但是沒(méi)有走過(guò)的路 - close列表
已經(jīng)走過(guò)的路 - F值
這個(gè)叫做和值列牺，指的是走到終點(diǎn)消耗的代價(jià)值，這里就是指的是小貓消耗的體力了
F = G + H,所以要知道F值拗窃，需要計(jì)算G和H的值 - G值
從起點(diǎn)到該點(diǎn)消耗的代價(jià) - H值
從該點(diǎn)到終點(diǎn)的預(yù)估代價(jià)瞎领，為何G值不是預(yù)估泌辫，這里是預(yù)估呢？因?yàn)镚值是從起點(diǎn)到該點(diǎn)九默，是一段已經(jīng)走過(guò)的路程震放，代價(jià)是準(zhǔn)確可知的，H值是到終點(diǎn)驼修，但是這段路還沒(méi)有走殿遂，所以是一段預(yù)估的值。
這些概念聽(tīng)起來(lái)有辣么一點(diǎn)對(duì)角懵逼~乙各，沒(méi)關(guān)系墨礁，我們實(shí)際演示下
4.手工走起
我們用粉色代表open列表，用綠色代表close列表
首先起點(diǎn)是我們走過(guò)的第一個(gè)點(diǎn)耳峦，將它先加入到close列表中
然后這只貓有四個(gè)方向可以選擇恩静，分別是上下左右，將這四個(gè)方塊加入到open表中蹲坷，表示知道但是還沒(méi)走過(guò)的路蜕企，現(xiàn)在是決定怎么走的時(shí)候了，于是我們分別求著四個(gè)方塊的F值冠句。
G值都是很好求的，都是1幸乒，從起點(diǎn)走到這里嘛懦底，都只走一步，H值從該點(diǎn)到終點(diǎn)的預(yù)估代價(jià)罕扎，這個(gè)可怎么求聚唐？
一般來(lái)說(shuō)，這個(gè)值就是忽略所有障礙的情況下走出來(lái)的值腔召，很明顯杆查，在這種只能直行的條件下，H值就是兩點(diǎn)之間的橫向格子數(shù)差加上縱向格子數(shù)差了
上格子 H = 橫向7 + 縱向2 = 9
下格子 H = 橫向7 + 縱向0 = 7
左格子 H = 橫向8 + 縱向1 = 9
右格子 H = 橫向6 + 縱向1 = 7
加上G值可以求得他們的F值分別為10,8,10,8
將這些數(shù)據(jù)標(biāo)注在格子上
上面是F值臀蛛，下左是G亲桦，下右是H
有了這些數(shù)據(jù)，小貓就挑一個(gè)F值最小的走浊仆，這里8是最小客峭，但是有兩個(gè)，怎么辦抡柿？無(wú)所謂了舔琅，隨便走一條，但是一般是最后加入open表的那個(gè)格子洲劣。至于為什么無(wú)所謂备蚓，可以看完整篇文章反過(guò)來(lái)想想课蔬。
就走右邊了，于是將右邊的方塊加入到close表郊尝，已經(jīng)走過(guò)了嘛二跋，記得要將它從open表中剔除
接著在這個(gè)新的格子上，又有4個(gè)選擇的方向虚循，但是這里要注意了同欠，每次選擇新格子加入open列表的時(shí)候，要保證3點(diǎn)
- 這個(gè)點(diǎn)不能在close表中
- 這個(gè)點(diǎn)不能在open表中
- 這個(gè)點(diǎn)是合法的横缔，什么叫合法铺遂？這里簡(jiǎn)單的就是可以通行的，不能是障礙物
于是又加入了上下右三個(gè)點(diǎn)到open列表中茎刚，此時(shí)open列表已經(jīng)有6個(gè)點(diǎn)了襟锐，接著計(jì)算這三個(gè)點(diǎn)的各項(xiàng)值
然后在open表中再次尋找F值最低的格子，發(fā)現(xiàn)是8膛锭，這里有3個(gè)粮坞，還是隨意選一個(gè)，選下面的吧初狰，將它從open表中剔除莫杈，加入close表中
緊接著再次尋找新的格子加入open列表中，依舊遵循上面說(shuō)的3點(diǎn)奢入，發(fā)現(xiàn)符合加入的只有右邊的格子
接著還是計(jì)算新加入open列表的格子的值
在open列表中尋找F值最低的格子筝闹，發(fā)現(xiàn)還是8，有3個(gè)腥光，我們選擇最新加入的关顷。
經(jīng)過(guò)這幾步之后，你是不是漸漸發(fā)現(xiàn)了規(guī)律武福？
5.偽代碼
我們來(lái)總結(jié)下規(guī)律
將起點(diǎn)加入close表
while(結(jié)束條件)
{
獲取close表的最后一個(gè)節(jié)點(diǎn)S
獲取S點(diǎn)周圍所有符合加入條件（條件就是指上文所說(shuō)的那3點(diǎn)）的點(diǎn)议双，加入open列表
計(jì)算open列表F值最低的格子T
T從open表中刪除加入close表
}
再次循環(huán)的時(shí)候，是不是第一步獲取的節(jié)點(diǎn)S就是最后加入的T了捉片，如此就可以跟隨著這個(gè)T平痰，一步步的擴(kuò)展路徑了
結(jié)束條件：如果有這條路徑存在，則是當(dāng)青蛙所在的節(jié)點(diǎn)被加入到close后界睁，尋路就結(jié)束了觉增。
或者不存在這條路徑，那么就是open列表中不再有節(jié)點(diǎn)的時(shí)候翻斟。
open列表實(shí)際上是一步步往外擴(kuò)展的格子逾礁，當(dāng)這個(gè)列表沒(méi)有節(jié)點(diǎn)的時(shí)候并且終點(diǎn)還沒(méi)有在close列表中，
那么說(shuō)明所有能擴(kuò)展到的格子已經(jīng)都被走過(guò)了，仍然沒(méi)有走到終點(diǎn)嘹履，此時(shí)便是沒(méi)有這條路了
6.注意項(xiàng)
A星得到的結(jié)果是一條路徑腻扇，這條路徑最終是反推回去的，所以在寫Node的數(shù)據(jù)結(jié)構(gòu)時(shí)候砾嫉，要記錄這個(gè)節(jié)點(diǎn)是從哪個(gè)節(jié)點(diǎn)走過(guò)來(lái)的幼苛，也就是他的父節(jié)點(diǎn)，如此在最終才能反推回去焕刮。
A星不是沿著一條路走到黑的舶沿，你會(huì)發(fā)現(xiàn)它是不停地計(jì)算open表中最小F值的格子，當(dāng)最小F值超過(guò)10的時(shí)候配并，你發(fā)現(xiàn)它又開(kāi)始從F為10的格子上開(kāi)始探索括荡，實(shí)際上是幾條不同的路徑輪詢的探索，最終走向終點(diǎn)溉旋，這也是為為何在open列表F值最低同時(shí)存在多個(gè)的時(shí)候畸冲，隨便選擇的原因，因?yàn)橐坏┨剿鞯母褡覨值超過(guò)了這個(gè)最低值观腊，它又會(huì)回到這個(gè)最低F值的格子上開(kāi)始探索
7關(guān)于死胡同
在我剛開(kāi)始學(xué)習(xí)A星的時(shí)候邑闲，我總是會(huì)覺(jué)得，如果碰到死胡同梧油，尋路仿佛就要終止苫耸，其實(shí)不然，A星是一個(gè)不同的搜索最小值過(guò)程的算法儡陨，除非open列表不存在鲸阔，否則open列表中一定有一個(gè)是最小值的格子，只要存在這個(gè)格子迄委，那么尋路就能繼續(xù)下去，而對(duì)于最終的路徑类少，我們是通過(guò)回溯的方式來(lái)獲取叙身，所以對(duì)于尋路，并不是說(shuō)close表里的格子就都是路徑了硫狞，想明白這回事信轿，對(duì)A星就有比較明確的認(rèn)識(shí)了
