時(shí)間真是過的飛快宁否！每次放松去享受一下生活窒升，就感覺里職業(yè)高端精英的夢想遠(yuǎn)了一些。而森林里松樹的氣息慕匠，實(shí)在讓人心曠神怡饱须。真希望每天可以去森林公園給大腦補(bǔ)補(bǔ)氧氣！回頭看看2019這已經(jīng)過去的2個(gè)月台谊，完全想不起任何知識(shí)點(diǎn)了蓉媳。還是不能只學(xué)數(shù)學(xué)！ 看起計(jì)算機(jī)有不會(huì)的數(shù)學(xué)再去查閱吧 ~
-----------------------------------------------------廢話分割線----------------------------------------------------
基本概念：
啟發(fā)式搜索： 啟發(fā)式搜索就是在狀態(tài)空間中的搜索對每一個(gè)搜索的位置進(jìn)行評估锅铅，得到最好的位置酪呻，再從這個(gè)位置進(jìn)行搜索直到目標(biāo)。這樣可以省略大量無畏的搜索路徑盐须，提到了效率玩荠。在啟發(fā)式搜索中，對位置的估價(jià)是十分重要的贼邓。采用了不同的估價(jià)可以有不同的效果阶冈。
?IDA*算法： 這種算法被稱為迭代加深A(yù)算法，可以有效的解決A空間增長帶來的問題塑径，甚至可以不用到優(yōu)先級(jí)隊(duì)列女坑。
搜索區(qū)域（The Search Area）： 圖中的搜索區(qū)域被劃分為了簡單的二維數(shù)組，數(shù)組每個(gè)元素對應(yīng)一個(gè)小方格统舀，當(dāng)然我們也可以將區(qū)域等分成是五角星匆骗，矩形等，通常將一個(gè)單位的中心點(diǎn)稱之為搜索區(qū)域節(jié)點(diǎn)（Node）绑咱〈律福
開放列表(Open List)： 我們將路徑規(guī)劃過程中待檢測的節(jié)點(diǎn)存放于Open List中，而已檢測過的格子則存放于Close List中描融。
關(guān)閉列表(Close List)： 我們將路徑規(guī)劃過程中已經(jīng)檢查過的節(jié)點(diǎn)放在Close List。
啟發(fā)函數(shù)（Heuristics Function）（估價(jià)函數(shù)）： H為啟發(fā)函數(shù)衡蚂，也被認(rèn)為是一種試探窿克，由于在找到唯一路徑前骏庸，我們不確定在前面會(huì)出現(xiàn)什么障礙物，因此用了一種計(jì)算H的算法年叮，具體根據(jù)實(shí)際場景決定具被。在我們簡化的模型中，H采用的是傳統(tǒng)的曼哈頓距離（Manhattan Distance）估價(jià)函數(shù)只损，也就是橫縱向走的距離之和一姿。 F(n) = G + H。F代表當(dāng)前檢查點(diǎn)的總花費(fèi)跃惫，G代表起點(diǎn)到當(dāng)前檢查點(diǎn)的花費(fèi)叮叹，H代表當(dāng)前檢查點(diǎn)到終點(diǎn)的預(yù)估花費(fèi)。
父節(jié)點(diǎn)（parent）： 在路徑規(guī)劃中用于回溯的節(jié)點(diǎn)爆存。
---------------------------------------前提介紹分割線--------------------------------------------------------
??我理解的高效學(xué)習(xí)計(jì)算機(jī)蛉顽，”理論公式+ 圖形動(dòng)態(tài)演示+ 代碼演示“三合一療效顯著！
一.A算法
1.A算法的公式表示：
A算法由f(n)=g(n)+h(n) 倆個(gè)因素決定先较，g(n)是這一步的代價(jià)函數(shù),h(n)是這一步的預(yù)估函數(shù)携冤； 對于A*算法來說，評判函數(shù)也是f(n)=g?(n)+h?(n) 這個(gè)闲勺，只不過加了約束條件曾棕，g?(n)>0，h*(n)<=任意h(n)菜循； 以上只不過是定義翘地，對于一個(gè)實(shí)例來說，h(n)由很多種债朵，h(n)只是估值函數(shù)的一個(gè)集合子眶，有各種方法h1(n)h2(n) h3(n)…，取其中任意一個(gè)方法帶入上述公式序芦，組成評判函數(shù)臭杰，都是A算法的實(shí)現(xiàn)，現(xiàn)在取從集合中一個(gè)函數(shù)h?(n) h?(n)h*(n)谚中，使得它比集合中任意的函數(shù)都優(yōu)秀渴杆，這樣的算法叫A*算法。 也就是A*算法是最優(yōu)的A算法宪塔。（因?yàn)楣乐岛瘮?shù)最優(yōu)）磁奖。
2.算法的過程8步：
3.代碼演示
二.A*算法
A*（A-Star)算法是一種靜態(tài)路網(wǎng)中求解最短路徑最有效的直接搜索方法，也是解決許多搜索問題的有效算法某筐。算法中的距離估算值與實(shí)際值越接近比搭，最終搜索速度越快。
1.公式表示為：?
其中
?f(n) 是從初始狀態(tài)經(jīng)由狀態(tài)n到目標(biāo)狀態(tài)的代價(jià)估計(jì)南誊，
g(n) 是在狀態(tài)空間中從初始狀態(tài)到狀態(tài)n的實(shí)際代價(jià)身诺，
?h(n) 是從狀態(tài)n到目標(biāo)狀態(tài)的最佳路徑的估計(jì)代價(jià)蜜托。
（對于路徑搜索問題，狀態(tài)就是圖中的節(jié)點(diǎn)霉赡，代價(jià)就是距離）
h(n)的選取
保證找到最短路徑（最優(yōu)解的）條件橄务，關(guān)鍵在于估價(jià)函數(shù)f(n)的選取（或者說h(n)的選妊鳌）蜂挪。 我們以d(n)表達(dá)狀態(tài)n到目標(biāo)狀態(tài)的距離，那么h(n)的選取大致有如下三種情況：
?1. 如果h(n)< d(n)到目標(biāo)狀態(tài)的實(shí)際距離嗓化，這種情況下棠涮，搜索的點(diǎn)數(shù)多，搜索范圍大蟆湖，效率低故爵。但能得到最優(yōu)解。
?2. 如果h(n)=d(n)隅津，即距離估計(jì)h(n)等于最短距離诬垂，那么搜索將嚴(yán)格沿著最短路徑進(jìn)行， 此時(shí)的搜索效率是最高的伦仍。
3. 如果 h(n)>d(n)结窘，搜索的點(diǎn)數(shù)少，搜索范圍小充蓝，效率高隧枫，但不能保證得到最優(yōu)解。
該算法在最短路徑搜索算法中分類為： 直接搜索算法：直接在實(shí)際地圖上進(jìn)行搜索谓苟，不經(jīng)過任何預(yù)處理官脓； 啟發(fā)式算法：通過啟發(fā)函數(shù)引導(dǎo)算法的搜索方向； 靜態(tài)圖搜索算法：被搜索的圖的權(quán)值不隨時(shí)間變化涝焙。
看了這些還是不清楚他是什么１氨俊？做個(gè)題來親自體會(huì)一下 仑撞！
距離估計(jì)與實(shí)際值越接近赤兴，估價(jià)函數(shù)取得就越好 例如對于幾何路網(wǎng)來說，可以取兩節(jié)點(diǎn)間曼哈頓距離做為距離估計(jì)隧哮，即f=g(n) + (abs(dx - nx) + abs(dy - ny))桶良；這樣估價(jià)函數(shù)f(n)在g(n)一定的情況下，會(huì)或多或少的受距離估計(jì)值h(n)的制約沮翔，節(jié)點(diǎn)距目標(biāo)點(diǎn)近陨帆，h值小，f值相對就小，能保證最短路的搜索向終點(diǎn)的方向進(jìn)行歧譬。明顯優(yōu)于Dijkstra算法的毫無方向的向四周搜索岸浑。 算法實(shí)現(xiàn)（路徑搜索） 創(chuàng)建兩個(gè)表搏存，OPEN表保存所有已生成而未考察的節(jié)點(diǎn)瑰步，CLOSED表中記錄已訪問過的節(jié)點(diǎn)。 算起點(diǎn)的h(s); 將起點(diǎn)放入OPEN表;?
2.算法過程
1）將起點(diǎn)A添加到open列表中（A沒有計(jì)算花費(fèi)F是因?yàn)楫?dāng)前open列表只有這一個(gè)節(jié)點(diǎn)）璧眠。
2?）檢查open列表缩焦，選取花費(fèi)F最小的節(jié)點(diǎn)M（檢查M如果為終點(diǎn)是則結(jié)束尋路，如果open列表沒有則尋路失敗责静，直接結(jié)束）袁滥。
3）對于與M相鄰的每一節(jié)點(diǎn)N：（下面本來沒有序號(hào)的，csdn markdown的bug）
a.如果N是阻擋障礙灾螃，那么不管它题翻。
b.如果N在closed列表中，那么不管它腰鬼。
c.如果N不在open列表中：添加它然后計(jì)算出它的花費(fèi)F(n)=G+H嵌赠。
d.如果N已在open列表中：當(dāng)我們使用當(dāng)前生成的路徑時(shí)，檢查F花費(fèi)是否更小熄赡。如果是姜挺，更新它的花費(fèi)F和它的父節(jié)點(diǎn)。
4?)重復(fù)b,c步彼硫。
3.代碼演示
用不同計(jì)算機(jī)語言實(shí)現(xiàn)A*算法不同炊豪。可以在網(wǎng)絡(luò)上查找到代碼拧篮。我沒找到動(dòng)圖词渤。
推薦一個(gè) app:算法動(dòng)畫圖解。
剛開始學(xué)習(xí)計(jì)算機(jī)串绩，有些凌亂缺虐，有錯(cuò)誤之處還請指出！
多謝赏参！
Have a nice day !
希望通過結(jié)構(gòu)化知識(shí)志笼，提高學(xué)習(xí)效率，讓你的工作時(shí)間更值錢把篓，賺錢更高效纫溃！------------《 數(shù)據(jù)分析筆記》
