a星演算法c語言

❶ A星搜索演算法

A星演算法是定義了一個函數f，公式為：
f = g + h
其中g函數代表目前為止從出發地到達該節點的成本，h函數是預估的當前節點到到目的地的成本，即
g(path) = path cost
h(path) = h(s) = estimated distance to goal
朝著使函數f具有最小值的路徑拓展,該演算法可以找到消耗最小消耗的路徑

注意A星演算法並不是總能找到最優解，能否找到最優解依賴於h函數，條件是

❷ 深度優先搜索和廣度優先搜索、A星演算法三種演算法的區別和聯系

1、何謂啟發式搜索演算法
在說它之前先提提狀態空間搜索.狀態空間搜索,如果按專業點的說法就是將問題求解過程表現為從初始狀態到目標狀態尋找這個路徑的過程.通俗點說,就是 在解一個問題時,找到一條解題的過程可以從求解的開始到問題的結果（好象並不通俗哦）.由於求解問題的過程中分枝有很多,定性,不完備性造成的,使得求解的路徑很多這就構成了一個圖,我們說這個圖就是狀態空間.問題的求解實際上就是在這個圖中找到一條路徑可以從開始到結果.這個尋找的過程就是狀態空間搜索.
常用的狀態空間搜索有深度優先和廣度優先.廣度優先是從初始狀態一層一層向下找,直到找到目標為止.深度優先是按照一定的順序前查找完一個分支,再查找另一個分支,以至找到目標為止.這兩種演算法在數據結構書中都有描述,可以參看這些書得到更詳細的解釋.
前面說的廣度和深度優先搜索有一個很大的缺陷就是他們都是在一個給定的狀態空間中窮舉.這在狀態空間不大的情況下是很合適的演算法,可是當狀態空間十分大,且不預測的情況下就不可取了.他的效率實在太低,甚至不可完成.在這里就要用到啟發式搜索了.
啟發式搜索就是在狀態空間中的搜索對每一個搜索的位置進行評估,得到最好的位置,再從這個位置進行搜索直到目標.這樣可以省略大量無畏的搜索路徑,提 到了效率.在啟發式搜索中,對位置的估價是十分重要的.採用了不同的估價可以有不同的效果.我們先看看估價是如何表示的.
啟發中的估價是用估價函數表示的,如：
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*演算法.
2、初識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)

❸ 人工智慧 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，歡迎大家指出，共同學習。

❹ 演算法過程是什麼

❺ 人機交互屬於人工智慧嗎

首先，人工智慧並不等於「XX學習」。
人工智慧是一個非常古老的名詞，在今天看來，是個很抽象的概念。
與「人工智慧」這個詞距離最近的，是游戲行業。在幾年之前，人工智慧這個概念並不火，也沒聽說有別的行業討論過人工智慧。
唯獨在游戲行業，人工智慧在許多年前，就已經是個爛大街的概念了。我在小學六年級的暑假(1997年)，大舅手把手教我用C語言寫出了人生中第一個小游戲(一個控制台飛行棋)。那時候，我就第一次從大舅口中聽到了「人工智慧」這個詞。
以游戲為例，你控制主角的那些操作，就叫做人機交互，比如按W，主角往前跑，按空格，主角就跳起來。而NPC的行為，就是人工智慧。
在游戲行業，凡是用來製作NPC尋路，以及戰斗相關邏輯的技術，都被稱作AI。
比如《英雄聯盟》《王者榮耀》等游戲，小兵NPC從出生之後就一路向對方的水晶移動，若途中遇到敵人，就追擊敵人，敵人走遠，就再次向敵方水晶移動。這就是用游戲行業最常見的WayPoint演算法實現的。
再比如戰棋類的游戲，簡單的就如《中國象棋》、《五子棋》，復雜一點的就如《火焰之紋章》、《三國志》、《超級機器人大戰》等。這些棋子或角色在移動之前，通常都會顯示出它所能移動的范圍。這是使用排序演算法實現的，排序演算法通常會分成「深度優先演算法」和「廣度優先演算法」兩類，但這不是今天要說的主題，故略去不談。
這些演算法，就是游戲行業的人工智慧。其中WayPoint(路點演算法)，排序演算法，另外還有一種A*演算法(中文讀作A星演算法)，是游戲AI演算法中最常見的三種。而游戲行業中的AI演算法，其實遠遠不止這些，幾十種還是有的。
後來的機器學習、深度學習，其實也只是演算法而已。演算法是新的，但人工智慧這個概念卻是早已有之，演算法也是多種多樣，遠非「XX學習」可以代表的。
XX學習也可以用於游戲行業，但對於游戲行業來說，其實並沒什麼幫助。有了它，做NPC時又多了一些選擇。沒有它，相關的解決技術也已經足夠多了。
最大的不同在於，XX學習把「人工智慧」這個名詞，擴散到了游戲之外的行業。至少聽起來，像個高端大氣的新概念似的。。。

❻ 計算機求百錢買百雞問題採用的演算法是

演算法如下：

int main()

{

int x, y, z;

for (int k = 1; k <= 3; k++)

{

x = 4 * k;

y = 25 - 7 * k;

z = 75 + 3 * k;

printf("公雞:%d只，母雞:%d只,小雞:%d只 ", x, y, z);

(6)a星演算法c語言擴展閱讀：

A*搜尋演算法

俗稱A星演算法。這是一種在圖形平面上，有多個節點的路徑，求出最低通過成本的演算法。常用於游戲中的NPC的移動計算，或線上游戲的BOT的移動計算上。該演算法像Dijkstra演算法一樣，可以找到一條最短路徑；也像BFS一樣，進行啟發式的搜索。

Beam Search

束搜索(beam search)方法是解決優化問題的一種啟發式方法，它是在分枝定界方法基礎上發展起來的，它使用啟發式方法估計k個最好的路徑，僅從這k個路徑出發向下搜索，即每一層只有滿意的結點會被保留，其它的結點則被永久拋棄，從而比分枝定界法能大大節省運行時間。

束搜索於20 世紀70年代中期首先被應用於人工智慧領域,1976 年Lowerre在其稱為HARPY的語音識別系統中第一次使用了束搜索方法。他的目標是並行地搜索幾個潛在的最優決策路徑以減少回溯，並快速地獲得一個解。

二分取中查找演算法

一種在有序數組中查找某一特定元素的搜索演算法。搜索過程從數組的中間元素開始，如果中間元素正好是要查找的元素，則搜索過程結束；

如果某一特定元素大於或者小於中間元素，則在數組大於或小於中間元素的那一半中查找，而且跟開始一樣從中間元素開始比較。這種搜索演算法每一次比較都使搜索范圍縮小一半。