a演算法下載

㈠ A*演算法java實現

首先，你要知道走迷宮的思路：就是遇到岔路都往一個方向，比如往右，遇到死路就回頭，回頭遇到岔路繼續往右。
線法線在同一平面上，反射光線與入射光線分

㈡ 人工智慧 A*演算法原理

A 演算法是啟發式演算法重要的一種，主要是用於在兩點之間選擇一個最優路徑，而A 的實現也是通過一個估值函數

上圖中這個熊到樹葉的 曼哈頓距離 就是藍色線所表示的距離，這其中不考慮障礙物，假如上圖每一個方格長度為1，那麼此時的熊的曼哈頓距離就為9.
起點（X1,Y1）,終點（X2,Y2）,H=|X2-X1|+|Y2-Y1|
我們也可以通過幾何坐標點來算出曼哈頓距離，還是以上圖為例，左下角為（0，0）點，熊的位置為（1，4），樹葉的位置為（7，1），那麼H=|7-1|+|1-4|=9。

還是以上圖為例，比如剛開始熊位置我們會加入到CLOSE列表中，而熊四周它可以移動到的點位我們會加入到OPEN列表中，並對熊四周的8個節點進行F=G+H這樣的估值運算，然後在這8個節點中選中一個F值為最小的節點，然後把再把這個節點從OPEN列表中刪除，加入到Close列表中，從接著在對這個節點的四周8個節點進行一個估值運算，再接著依次運算，這樣說大家可能不是太理解，我會在下邊做詳細解釋。

從起點到終點，我們通過A星演算法來找出最優路徑

我們把每一個方格的長度定義為1，那從起始點到5位置的代價就是1，到3的代價為1.41，定義好了我們接著看上圖，接著運算

第一步我們會把起始點四周的點加入OPEN列表中然後進行一個估值運算，運算結果如上圖，這其中大家看到一個小箭頭都指向了起點，這個箭頭就是指向父節點，而open列表的G值都是根據這個進行計算的，意思就是我從上一個父節點運行到此處時所需要的總代價，如果指向不一樣可能G值就不一樣，上圖中我們經過計算發現1點F值是7.41是最小的，那我們就選中這個點，並把1點從OPEN列表中刪除，加入到CLOSE列表中，但是我們在往下運算的時候發現1點的四周，2點，3點和起始點這三個要怎麼處理，首先起始點已經加入到了CLOSE，他就不需要再進行這種運算，這就是CLOSE列表的作用，而2點和3點我們也可以對他進行運算，2點的運算，我們從1移動到2點的時候，他需要的代價也就是G值會變成2.41，而H值是不會變的F=2.41+7=9.41，這個值我們發現大於原來的的F值，那我們就不能對他進行改變（把父節點指向1，把F值改為9.41，因為我們一直追求的是F值最小化），3點也同理。

在對1點四周進行運算後整個OPEN列表中有兩個點2點和3點的F值都是7.41，此時我們系統就可能隨機選擇一個點然後進行下一步運算，現在我們選中的是3點，然後對3點的四周進行運算，結果是四周的OPEN點位如果把父節點指向3點值時F值都比原來的大，所以不發生改變。我們在看整個OPEN列表中，也就2點的7.41值是最小的，那我們就選中2點接著運算。

我們在上一部運算中選中的是1點，上圖沒有把2點加入OPEN列表，因為有障礙物的阻擋從1點他移動不到2點，所以沒有把2點加入到OPEN列表中，整個OPEN列表中3的F=8是最小的，我們就選中3，我們對3點四周進行運算是我們發現4點經過計算G=1+1=2，F=2+6=8所以此時4點要進行改變，F變為8並把箭頭指向3點（就是把4點的父節點變為3），如下圖

我們就按照這種方法一直進行運算，最後 的運算結果如下圖

而我們通過目標點位根據箭頭（父節點），一步一步向前尋找最後我們發現了一條指向起點的路徑，這個就是我們所需要的最優路徑。 如下圖的白色選中區域

但是我們還要注意幾點

最優路徑有2個

這是我對A*演算法的一些理解，有些地方可能有BUG，歡迎大家指出，共同學習。

㈢ A*演算法——啟發式路徑搜索

A*是一種路徑搜索演算法，比如為游戲中的角色規劃行動路徑。

A* 演算法的輸入是， 起點（初始狀態） 和 終點（目標狀態） ，以及兩點間 所有可能的路徑 ，以及涉及到的 中間節點（中間狀態） ，每兩個節點間的路徑的 代價 。

一般還需要某種 啟發函數 ，即從任意節點到終點的近似代價，啟發函數能夠非常快速的估算出該代價值。

輸出是從 起點到終點的最優路徑 ，即代價最小。同時，好的啟發函數將使得這一搜索運算盡可能高效，即搜索盡量少的節點/可能的路徑。

f(n)=g(n)+h(n)

f(n) 是從初始狀態經由狀態n到目標狀態的代價估計

g(n) 是在狀態空間中從初始狀態到狀態n的實際代價

h(n) 是從狀態n到目標狀態的最佳路徑的估計代價

A*演算法是從起點開始，檢查所有可能的擴展點（它的相鄰點），對每個點計算g+h得到f，在所有可能的擴展點中，選擇f最小的那個點進行擴展，即計算該點的所有可能擴展點的f值，並將這些新的擴展點添加到擴展點列表（open list）。當然，忽略已經在列表中的點、已經考察過的點。

不斷從open list中選擇f值最小的點進行擴展，直到到達目標點（成功找到最優路徑），或者節點用完，路徑搜索失敗。

演算法步驟：

參考

A* 演算法步驟的詳細說明請參考 A*尋路演算法 ，它包含圖文案例清楚的解釋了A*演算法計算步驟的一些細節，本文不再詳細展開。

看一下上面參考文檔中的案例圖，最終搜索完成時，藍色邊框是close list中的節點，綠色邊框是open list中的節點，每個方格中三個數字，左上是f（=g+h），左下是g（已經過路徑的代價），右下是h（估計未經過路徑的代價）。藍色方格始終沿著f值最小的方向搜索前進，避免了對一些不好的路徑（f值較大）的搜索。（圖片來自 A*尋路演算法 ）

現在我們可以理解，A*演算法中啟發函數是最重要的，它有幾種情況：

1) h(n) = 0
一種極端情況，如果h(n)是0，則只有g(n)起作用，此時A*演變成Dijkstra演算法，這保證能找到最短路徑。但效率不高，因為得不到啟發。

2) h(n) < 真實代價
如果h(n)經常都比從n移動到目標的實際代價小（或者相等），則A*保證能找到一條最短路徑。h(n)越小，A*擴展的結點越多，運行就得越慢。越接近Dijkstra演算法。

3) h(n) = 真實代價
如果h(n)精確地等於從n移動到目標的代價，則A*將會僅僅尋找最佳路徑而不擴展別的任何結點，這會運行得非常快。盡管這不可能在所有情況下發生，你仍可以在一些特殊情況下讓它們精確地相等（譯者：指讓h(n)精確地等於實際值）。只要提供完美的信息，A*會運行得很完美，認識這一點很好。

4) h(n) > 真實代價
如果h(n)有時比從n移動到目標的實際代價高，則A*不能保證找到一條最短路徑，但它運行得更快。

5) h(n) >> 真實代價
另一種極端情況，如果h(n)比g(n)大很多，則只有h(n)起作用，A*演變成BFS演算法。

關於啟發函數h、Dijkstra演算法、BFS（最佳優先搜索）演算法、路徑規劃情況下啟發函數的選擇、演算法實現時List的數據結構、演算法變種等等更多問題，請參考： A*演算法

㈣ A*演算法詳解

我們討論一個移動機器人遇到問題：如何移動到指定位置

這里討論的是路徑規劃問題。而A*演算法是廣為使用的解決這個問題的演算法。

如圖1，綠色點為start設為A，紅色點為goal設為B，藍色點為不可通過的障礙物，黑色點為自由區域。目標是規劃從A到B的路徑。

對相鄰點，一次計算每一點的g_score，h_score，最後得到f_score。如圖3，節點的右下角為g_score值，左下角為h_score值，右上角為f_score。

㈤ 搜索演算法中,A演算法A*演算法的區別（急）

A演算法一般指某個搜索演算法的樸素的思路
A*指使用了啟發式搜索之後的演算法,也就是運算速度會快很多,但不一定能保證最後得到最優解

㈥ A*演算法的介紹

A*演算法；A*（A-Star)演算法是一種靜態路網中求解最短路徑最有效的直接搜索方法。估價值與實際值越接近，估價函數取得就越好。

㈦ A*演算法C＋＋源程序

A*演算法在人工智慧中是一種典型的啟發式搜索演算法，為了說清楚A*演算法，我看還是先說說何謂啟發式演算法。

一、何謂啟發式搜索演算法

在說它之前先提提狀態空間搜索。狀態空間搜索，如果按專業點的說法就是將問題求解過程表現為從初始狀態到目標狀態尋找這個路徑的過程。通俗點說，就是在解一個問題時，找到一條解題的過程可以從求解的開始到問題的結果（好象並不通俗哦）。由於求解問題的過程中分枝有很多，主要是求解過程中求解條件的不確定性，不完備性造成的，使得求解的路徑很多這就構成了一個圖，我們說這個圖就是狀態空間。問題的求解實際上就是在這個圖中找到一條路徑可以從開始到結果。這個尋找的過程就是狀態空間搜索。

常用的狀態空間搜索有深度優先和廣度優先。廣度優先是從初始狀態一層一層向下找，直到找到目標為止。深度優先是按照一定的順序前查找完一個分支，再查找另一個分支，以至找到目標為止。這兩種演算法在數據結構書中都有描述，可以參看這些書得到更詳細的解釋。

前面說的廣度和深度優先搜索有一個很大的缺陷就是他們都是在一個給定的狀態空間中窮舉。這在狀態空間不大的情況下是很合適的演算法，可是當狀態空間十分大，且不預測的情況下就不可取了。他的效率實在太低，甚至不可完成。在這里就要用到啟發式搜索了。

啟發式搜索就是在狀態空間中的搜索對每一個搜索的位置進行評估，得到最好的位置，再從這個位置進行搜索直到目標。這樣可以省略大量無畏的搜索路徑，提到了效率。在啟發式搜索中，對位置的估價是十分重要的。採用了不同的估價可以有不同的效果。我們先看看估價是如何表示的。

啟發中的估價是用估價函數表示的，如：

f(n) = g(n) + h(n)

其中f(n)是節點n的估價函數，g(n)實在狀態空間中從初始節點到n節點的實際代價，h(n)是從n到目標節點最佳路徑的估計代價。在這里主要是h(n)體現了搜索的啟發信息，因為g(n)是已知的。如果說詳細點，g(n)代表了搜索的廣度的優先趨勢。但是當h(n)>>g(n)時，可以省略g(n),而提高效率。這些就深了，不懂也不影響啦！我們繼續看看何謂A*演算法。

二、初識A*演算法

啟發式搜索其實有很多的演算法，比如：局部擇優搜索法、最好優先搜索法等等。當然A*也是。這些演算法都使用了啟發函數，但在具體的選取最佳搜索節點時的策略不同。象局部擇優搜索法，就是在搜索的過程中選取「最佳節點」後舍棄其他的兄弟節點，父親節點，而一直得搜索下去。這種搜索的結果很明顯，由於舍棄了其他的節點，可能也把最好的節點都舍棄了，因為求解的最佳節點只是在該階段的最佳並不一定是全局的最佳。最好優先就聰明多了，他在搜索時，便沒有舍棄節點（除非該節點是死節點），在每一步的估價中都把當前的節點和以前的節點的估價值比較得到一個「最佳的節點」。這樣可以有效的防止「最佳節點」的丟失。那麼A*演算法又是一種什麼樣的演算法呢？其實A*演算法也是一種最好優先的演算法。只不過要加上一些約束條件罷了。由於在一些問題求解時，我們希望能夠求解出狀態空間搜索的最短路徑，也就是用最快的方法求解問題，A*就是干這種事情的！我們先下個定義，如果一個估價函數可以找出最短的路徑，我們稱之為可採納性。A*演算法是一個可採納的最好優先演算法。A*演算法的估價函數可表示為：

f'(n) = g'(n) + h'(n)

這里，f'(n)是估價函數，g'(n)是起點到終點的最短路徑值，h'(n)是n到目標的最斷路經的啟發值。由於這個f'(n)其實是無法預先知道的，所以我們用前面的估價函數f(n)做近似。g(n)代替g'(n)，但g(n)>=g'(n)才可（大多數情況下都是滿足的，可以不用考慮），h(n)代替h'(n)，但h(n)<=h'(n)才可（這一點特別的重要）。可以證明應用這樣的估價函數是可以找到最短路徑的，也就是可採納的。我們說應用這種估價函數的最好優先演算法就是A*演算法。哈！你懂了嗎？肯定沒懂！接著看！

舉一個例子，其實廣度優先演算法就是A*演算法的特例。其中g(n)是節點所在的層數，h(n)=0，這種h(n)肯定小於h'(n)，所以由前述可知廣度優先演算法是一種可採納的。實際也是。當然它是一種最臭的A*演算法。

再說一個問題，就是有關h(n)啟發函數的信息性。h(n)的信息性通俗點說其實就是在估計一個節點的值時的約束條件，如果信息越多或約束條件越多則排除的節點就越多，估價函數越好或說這個演算法越好。這就是為什麼廣度優先演算法的那麼臭的原因了，誰叫它的h(n)=0，一點啟發信息都沒有。但在游戲開發中由於實時性的問題，h(n)的信息越多，它的計算量就越大，耗費的時間就越多。就應該適當的減小h(n)的信息，即減小約束條件。但演算法的准確性就差了，這里就有一個平衡的問題。可難了，這就看你的了！

好了我的話也說得差不多了，我想你肯定是一頭的霧水了，其實這是寫給懂A*演算法的同志看的。哈哈！你還是找一本人工智慧的書仔細看看吧！我這幾百字是不足以將A*演算法講清楚的。

㈧ A*演算法 和 最佳優先搜索演算法（Best-First-Search）

最佳優先搜索演算法是一種啟發式搜索演算法（Heuristic Algorithm），其基於廣度優先搜索演算法，不同點是其依賴於估價函數對將要遍歷的節點進行估價，選擇代價小的節點進行遍歷，直到找到目標點為止。 BFS演算法不能保證找到的路徑是一條最短路徑，但是其計算過程相對於Dijkstra
演算法會快很多 。

最佳優先搜索是一種啟發式搜索演算法。廣度優先搜索和深度優先搜索都屬於窮舉類型的搜索，需要依次遍歷所有的節點，當空間非常大的時候，這種方式的效率就會非常差。而啟發式的搜索是對狀態控制項中的每個點進行評估，然後選出最好的位置。

啟發估價函數公式為：

n表示當前的點，g(n)為從起始點到點n的實際代價，h(n)為從點n到目標點的估價。

（圖片來源於網路）

A*演算法將BFS演算法和Dijkstra演算法結合在一起，結合兩演算法的優點，既可以查找最短路徑的，有擁有和BFS差不多的效率。

（圖片來源於網路）

A*演算法詳解

模擬尋路的地址

㈨ A*演算法介紹

姓名：車文揚 學號：16020199006

【嵌牛導讀】：A*演算法的逐步詳解

【嵌牛鼻子】：啟發式演算法

【嵌牛提問】：A*演算法的原理是什麼？

【嵌牛正文】：

A*演算法

路徑規劃是指的是機器人的最優路徑規劃問題，即依據某個或某些優化准則（如工作代價最小、行走路徑最短、行走時間最短等），在工作空間中找到一個從起始狀態到目標狀態能避開障礙物的最優路徑。機器人的路徑規劃應用場景極豐富，最常見如游戲中NPC及控制角色的位置移動，網路地圖等導航問題，小到家庭掃地機器人、無人機大到各公司正爭相開拓的無人駕駛汽車等。

目前路徑規劃演算法分為：

A*演算法原理：

在計算機科學中，A*演算法作為Dijkstra演算法的擴展，因其高效性而被廣泛應用於尋路及圖的遍歷，如星際爭霸等游戲中就大量使用。在理解演算法前，我們需要知道幾個概念：

搜索區域（The Search Area）：圖中的搜索區域被劃分為了簡單的二維數組，數組每個元素對應一個小方格，當然我們也可以將區域等分成是五角星，矩形等，通常將一個單位的中心點稱之為搜索區域節點（Node）。

開放列表(Open List)：我們將路徑規劃過程中待檢測的節點存放於Open List中，而已檢測過的格子則存放於Close List中。

父節點（parent）：在路徑規劃中用於回溯的節點，開發時可考慮為雙向鏈表結構中的父結點指針。

路徑排序（Path Sorting）：具體往哪個節點移動由以下公式確定：F(n) = G + H 。G代表的是從初始位置A沿著已生成的路徑到指定待檢測格子的移動開銷。H指定待測格子到目標節點B的估計移動開銷。

啟發函數（Heuristics Function）：H為啟發函數，也被認為是一種試探，由於在找到唯一路徑前，我們不確定在前面會出現什麼障礙物，因此用了一種計算H的演算法，具體根據實際場景決定。在我們簡化的模型中，H採用的是傳統的曼哈頓距離（Manhattan Distance），也就是橫縱向走的距離之和。

如下圖所示，綠色方塊為機器人起始位置A，紅色方塊為目標位置B，藍色為障礙物。

我們把要搜尋的區域劃分成了正方形的格子。這是尋路的第一步，簡化搜索區域。這個特殊的方法把我們的搜索區域簡化為了2 維數組。數組的每一項代表一個格子，它的狀態就是可走(walkalbe)或不可走(unwalkable) 。現用A*演算法尋找出一條自A到B的最短路徑，每個方格的邊長為10，即垂直水平方向移動開銷為10。因此沿對角移動開銷約等於14。具體步驟如下：

從起點 A 開始，把它加入到一個由方格組成的open list(開放列表) 中，這個open list像是一個購物清單。Open list里的格子是可能會是沿途經過的，也有可能不經過。因此可以將其看成一個待檢查的列表。查看與A相鄰的8個方格 ，把其中可走的 (walkable) 或可到達的(reachable) 方格加入到open list中。並把起點 A 設置為這些方格的父節點 (parent node) 。然後把 A 從open list中移除，加入到close list(封閉列表) 中，close list中的每個方格都是不需要再關注的。

如下圖所示，深綠色的方格為起點A，它的外框是亮藍色，表示該方格被加入到了close list 。與它相鄰的黑色方格是需要被檢查的，他們的外框是亮綠色。每個黑方格都有一個灰色的指針指向他們的父節點A。

下一步，我們需要從open list中選一個與起點A相鄰的方格。但是到底選擇哪個方格好呢？選F值最小的那個。我們看看下圖中的一些方格。在標有字母的方格中G = 10 。這是因為水平方向從起點到那裡只有一個方格的距離。與起點直接相鄰的上方，下方，左方的方格的G 值都是10 ，對角線的方格G 值都是14 。H值通過估算起點到終點( 紅色方格) 的Manhattan 距離得到，僅作橫向和縱向移動，並且忽略沿途的障礙。使用這種方式，起點右邊的方格到終點有3 個方格的距離，因此H = 30 。這個方格上方的方格到終點有4 個方格的距離( 注意只計算橫向和縱向距離) ，因此H = 40 。

比較open list中節點的F值後，發現起點A右側節點的F=40，值最小。選作當前處理節點，並將這個點從Open List刪除，移到Close List中。

對這個節點周圍的8個格子進行判斷，若是不可通過（比如牆，水，或是其他非法地形）或已經在Close List中，則忽略。否則執行以下步驟：

若當前處理節點的相鄰格子已經在Open List中，則檢查這條路徑是否更優，即計算經由當前處理節點到達那個方格是否具有更小的 G值。如果沒有，不做任何操作。相反，如果G值更小，則把那個方格的父節點設為當前處理節點 ( 我們選中的方格 ) ，然後重新計算那個方格的 F 值和 G 值。

若當前處理節點的相鄰格子不在Open List中，那麼把它加入，並將它的父節點設置為該節點。

按照上述規則我們繼續搜索，選擇起點右邊的方格作為當前處理節點。它的外框用藍線打亮，被放入了close list 中。然後我們檢查與它相鄰的方格。它右側的3個方格是牆壁，我們忽略。它左邊的方格是起點，在close list 中，我們也忽略。其他4個相鄰的方格均在open list 中，我們需要檢查經由當前節點到達那裡的路徑是否更好。我們看看上面的方格，它現在的G值為14 ，如果經由當前方格到達那裡，G值將會為20( 其中10為從起點到達當前方格的G值，此外還要加上從當前方格縱向移動到上面方格的G值10) ，因此這不是最優的路徑。看圖就會明白直接從起點沿對角線移動到那個方格比先橫向移動再縱向移動要好。

當把4個已經在open list 中的相鄰方格都檢查後，沒有發現經由當前節點的更好路徑，因此不做任何改變。接下來要選擇下一個待處理的節點。因此再次遍歷open list ，現在open list中只有7 個方格了，我們需要選擇F值最小的那個。這次有兩個方格的F值都是54，選哪個呢？沒什麼關系。從速度上考慮，選擇最後加入open list 的方格更快。因此選擇起點右下方的方格，如下圖所示。

接下來把起點右下角F值為54的方格作為當前處理節點，檢查其相鄰的方格。我們發現它右邊是牆（牆下面的一格也忽略掉，假定牆角不能直接穿越)，忽略之。這樣還剩下 5 個相鄰的方格。當前方格下面的 2 個方格還沒有加入 open list ，所以把它們加入，同時把當前方格設為他們的父親。在剩下的 3 個方格中，有 2 個已經在 close list 中 ( 一個是起點，一個是當前方格上面的方格，外框被加亮的 ) ，我們忽略它們。最後一個方格，也就是當前方格左邊的方格，檢查經由當前方格到達那裡是否具有更小的 G 值。沒有，因此我們准備從 open list 中選擇下一個待處理的方格。

不斷重復這個過程，直到把終點也加入到了open list 中，此時如下圖所示。注意在起點下方2 格處的方格的父親已經與前面不同了。之前它的G值是28並且指向它右上方的方格。現在它的G 值為20 ，並且指向它正上方的方格。這是由於在尋路過程中的某處使用新路徑時G值更小，因此父節點被重新設置，G和F值被重新計算。

那麼我們怎樣得到實際路徑呢？很簡單，如下圖所示，從終點開始，沿著箭頭向父節點移動，直至回到起點，這就是你的路徑。

A*演算法總結：

1. 把起點加入 open list 。

2. 重復如下過程：

a. 遍歷open list ，查找F值最小的節點，把它作為當前要處理的節點，然後移到close list中

b. 對當前方格的 8 個相鄰方格一一進行檢查，如果它是不可抵達的或者它在close list中，忽略它。否則，做如下操作：

□  如果它不在open list中，把它加入open list，並且把當前方格設置為它的父親

□  如果它已經在open list中，檢查這條路徑 ( 即經由當前方格到達它那裡 ) 是否更近。如果更近，把它的父親設置為當前方格，並重新計算它的G和F值。如果你的open list是按F值排序的話，改變後你可能需要重新排序。

c. 遇到下面情況停止搜索：

□  把終點加入到了 open list 中，此時路徑已經找到了，或者

□  查找終點失敗，並且open list 是空的，此時沒有路徑。

3. 從終點開始，每個方格沿著父節點移動直至起點，形成路徑。