時(shí)間真是過(guò)的飛快！每次放松去享受一下生活，就感覺(jué)里職業(yè)高端精英的夢(mèng)想遠(yuǎn)了一些。而森林里松樹(shù)的氣息，實(shí)在讓人心曠神怡。真希望每天可以去森林公園給大腦補(bǔ)補(bǔ)氧氣！回頭看看2019這已經(jīng)過(guò)去的2個(gè)月，完全想不起任何知識(shí)點(diǎn)了。還是不能只學(xué)數(shù)學(xué)！ 看起計(jì)算機(jī)有不會(huì)的數(shù)學(xué)再去查閱吧 ~
-----------------------------------------------------廢話分割線----------------------------------------------------
基本概念：
啟發(fā)式搜索： 啟發(fā)式搜索就是在狀態(tài)空間中的搜索對(duì)每一個(gè)搜索的位置進(jìn)行評(píng)估，得到最好的位置，再?gòu)倪@個(gè)位置進(jìn)行搜索直到目標(biāo)。這樣可以省略大量無(wú)畏的搜索路徑，提到了效率。在啟發(fā)式搜索中，對(duì)位置的估價(jià)是十分重要的。采用了不同的估價(jià)可以有不同的效果。
?IDA*算法： 這種算法被稱為迭代加深A(yù)算法，可以有效的解決A空間增長(zhǎng)帶來(lái)的問(wèn)題，甚至可以不用到優(yōu)先級(jí)隊(duì)列。
搜索區(qū)域（The Search Area）： 圖中的搜索區(qū)域被劃分為了簡(jiǎn)單的二維數(shù)組，數(shù)組每個(gè)元素對(duì)應(yīng)一個(gè)小方格，當(dāng)然我們也可以將區(qū)域等分成是五角星，矩形等，通常將一個(gè)單位的中心點(diǎn)稱之為搜索區(qū)域節(jié)點(diǎn)（Node）?！ ?
開(kāi)放列表(Open List)： 我們將路徑規(guī)劃過(guò)程中待檢測(cè)的節(jié)點(diǎn)存放于Open List中，而已檢測(cè)過(guò)的格子則存放于Close List中。
關(guān)閉列表(Close List)： 我們將路徑規(guī)劃過(guò)程中已經(jīng)檢查過(guò)的節(jié)點(diǎn)放在Close List。
啟發(fā)函數(shù)（Heuristics Function）（估價(jià)函數(shù)）： H為啟發(fā)函數(shù)，也被認(rèn)為是一種試探，由于在找到唯一路徑前，我們不確定在前面會(huì)出現(xiàn)什么障礙物，因此用了一種計(jì)算H的算法，具體根據(jù)實(shí)際場(chǎng)景決定。在我們簡(jiǎn)化的模型中，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ù)； 對(duì)于A*算法來(lái)說(shuō)，評(píng)判函數(shù)也是f(n)=g?(n)+h?(n) 這個(gè)，只不過(guò)加了約束條件，g?(n)>0，h*(n)<=任意h(n)； 以上只不過(guò)是定義，對(duì)于一個(gè)實(shí)例來(lái)說(shuō)，h(n)由很多種，h(n)只是估值函數(shù)的一個(gè)集合，有各種方法h1(n)h2(n) h3(n)…，取其中任意一個(gè)方法帶入上述公式，組成評(píng)判函數(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.算法的過(guò)程8步：
3.代碼演示
二.A*算法
A*（A-Star)算法是一種靜態(tài)路網(wǎng)中求解最短路徑最有效的直接搜索方法，也是解決許多搜索問(wèn)題的有效算法。算法中的距離估算值與實(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à)。
（對(duì)于路徑搜索問(wèn)題，狀態(tài)就是圖中的節(jié)點(diǎn)，代價(jià)就是距離）
h(n)的選取
保證找到最短路徑（最優(yōu)解的）條件，關(guān)鍵在于估價(jià)函數(shù)f(n)的選取（或者說(shuō)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)過(guò)任何預(yù)處理； 啟發(fā)式算法：通過(guò)啟發(fā)函數(shù)引導(dǎo)算法的搜索方向； 靜態(tài)圖搜索算法：被搜索的圖的權(quán)值不隨時(shí)間變化。
看了這些還是不清楚他是什么！？做個(gè)題來(lái)親自體會(huì)一下 ！
距離估計(jì)與實(shí)際值越接近，估價(jià)函數(shù)取得就越好 例如對(duì)于幾何路網(wǎng)來(lái)說(shuō)，可以取兩節(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值相對(duì)就小，能保證最短路的搜索向終點(diǎn)的方向進(jìn)行。明顯優(yōu)于Dijkstra算法的毫無(wú)方向的向四周搜索。 算法實(shí)現(xiàn)（路徑搜索） 創(chuàng)建兩個(gè)表，OPEN表保存所有已生成而未考察的節(jié)點(diǎn)，CLOSED表中記錄已訪問(wèn)過(guò)的節(jié)點(diǎn)。 算起點(diǎn)的h(s); 將起點(diǎn)放入OPEN表;?
2.算法過(guò)程
1）將起點(diǎn)A添加到open列表中（A沒(méi)有計(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列表沒(méi)有則尋路失敗，直接結(jié)束）。
3）對(duì)于與M相鄰的每一節(jié)點(diǎn)N：（下面本來(lái)沒(méi)有序號(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ī)語(yǔ)言實(shí)現(xiàn)A*算法不同?？梢栽诰W(wǎng)絡(luò)上查找到代碼。我沒(méi)找到動(dòng)圖。
推薦一個(gè) app:算法動(dòng)畫(huà)圖解。
剛開(kāi)始學(xué)習(xí)計(jì)算機(jī)，有些凌亂，有錯(cuò)誤之處還請(qǐng)指出！
多謝！
Have a nice day !
希望通過(guò)結(jié)構(gòu)化知識(shí)，提高學(xué)習(xí)效率，讓你的工作時(shí)間更值錢，賺錢更高效！------------《 數(shù)據(jù)分析筆記》
