A搜索演算法的基本思想是什麼

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

a*演算法：a*（a-star)演算法是一種靜態路網中求解最短路徑最有效的直接搜索方法。估價值與實際值越接近，估價函數取得就越好
a*
（a-star)演算法是一種靜態路網中求解最短路最有效的直接搜索方法。
注意是最有效的直接搜索演算法。之後涌現了很多預處理演算法（alt，ch，hl等等），在線查詢效率是a*演算法的數千甚至上萬倍。
公式表示為：
f(n)=g(n)+h(n),
其中
f(n)
是從初始點經由節點n到目標點的估價函數，
g(n)
是在狀態空間中從初始節點到n節點的實際代價，
h(n)
是從n到目標節點最佳路徑的估計代價。
保證找到最短路徑（最優解的）條件，關鍵在於估價函數f(n)的選取：
估價值h(n)<=
n到目標節點的距離實際值，這種情況下，搜索的點數多，搜索范圍大，效率低。但能得到最優解。並且如果h(n)=d(n)，即距離估計h(n)等於最短距離，那麼搜索將嚴格沿著最短路徑進行，
此時的搜索效率是最高的。
如果
估價值>實際值,搜索的點數少，搜索范圍小，效率高，但不能保證得到最優解。

❷ 什麼是A搜索演算法

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

❸ A*演算法的原理

A* （A-Star)演算法是一種靜態路網中求解最短路最有效的直接搜索方法。
注意是最有效的直接搜索演算法。之後涌現了很多預處理演算法（ALT，CH，HL等等），在線查詢效率是A*演算法的數千甚至上萬倍。
公式表示為： f(n)=g(n)+h(n),
其中 f(n) 是從初始點經由節點n到目標點的估價函數，
g(n) 是在狀態空間中從初始節點到n節點的實際代價，
h(n) 是從n到目標節點最佳路徑的估計代價。
保證找到最短路徑（最優解的）條件，關鍵在於估價函數f(n)的選取：
估價值h(n)<= n到目標節點的距離實際值，這種情況下，搜索的點數多，搜索范圍大，效率低。但能得到最優解。並且如果h(n)=d(n)，即距離估計h(n)等於最短距離，那麼搜索將嚴格沿著最短路徑進行， 此時的搜索效率是最高的。
如果 估價值>實際值,搜索的點數少，搜索范圍小，效率高，但不能保證得到最優解。

❹ A*搜尋演算法的簡介

速度和精確度之間的選擇前不是靜態的。你可以基於CPU的速度、用於路徑搜索的時間片數、地圖上物體（units）的數量、物體的重要性、組（group）的大小、難度或者其他任何因素來進行動態的選擇。取得動態的折衷的一個方法是，建立一個啟發式函數用於假定通過一個網格空間的最小代價是1，然後建立一個代價函數（cost function）用於測量（scales）：
g』(n) = 1 + alpha * ( g(n) – 1 )
如果alpha是0，則改進後的代價函數的值總是1。這種情況下，地形代價被完全忽略，A*工作變成簡單地判斷一個網格可否通過。如果alpha是1，則最初的代價函數將起作用，然後你得到了A*的所有優點。你可以設置alpha的值為0到1的任意值。
你也可以考慮對啟發式函數的返回值做選擇：絕對最小代價或者期望最小代價。例如，如果你的地圖大部分地形是代價為2的草地，其它一些地方是代價為1的道路，那麼你可以考慮讓啟發式函數不考慮道路，而只返回2*距離。
速度和精確度之間的選擇並不是全局的。在地圖上的某些區域，精確度是重要的，你可以基於此進行動態選擇。例如，假設我們可能在某點停止重新計算路徑或者改變方向，則在接近當前位置的地方，選擇一條好的路徑則是更重要的，因此為何要對後續路徑的精確度感到厭煩？或者，對於在地圖上的一個安全區域，最短路徑也許並不十分重要，但是當從一個敵人的村莊逃跑時，安全和速度是最重要的。
在游戲中，路徑潛在地花費了許多存儲空間，特別是當路徑很長並且有很多物體需要尋路時。路徑壓縮，導航點和beacons通過把多個步驟保存為一個較小數據從而減少了空間需求。Waypoints rely on straight-line segments being common so that we have to store only the endpoints, while beacons rely on there being well-known paths calculated beforehand between specially marked places on the map.如果路徑仍然用了許多存儲空間，可以限制路徑長度，這就回到了經典的時間-空間折衷法：為了節省空間，信息可以被丟棄，稍後才重新計算它。

❺ 什麼是局部搜索演算法

局部搜索演算法是從爬山法改進而來的。
簡單來說，局部搜索演算法是一種簡單的貪心搜索演算法，該演算法每次從當前解的臨近解空間中選擇一個最優解作為當前解，直到達到一個局部最優解。
在計算機科學中，局部搜索是解決最優化問題的一種元啟發式演算法。局部搜索從一個初始解出發，然後搜索解的鄰域，如有更優的解則移動至該解並繼續執行搜索，否則返回當前解。
1、局部搜索演算法的基本思想：
在搜索過程中，始終選擇當前點的鄰居中與離目標最近者的方向搜索。
2、局部搜索的優點：
簡單、靈活及易於實現，缺點是容易陷入局部最優且解的質量與初始解和鄰域的結構密切相關。常見的改進方法有模擬退火、禁忌搜索等。
3、局部搜索廣泛應用：
計算機科學（主要是人工智慧）、數學、運籌學、工程學、生物信息學中各種很難找到全局最優解的計算問題。

❻ A*搜尋演算法的演算法描述

f(x) = g(x) + h(x)
function A*(start,goal)
var closed := the empty set
var q := make_queue(path(start))
while q is not empty
var p := remove_first(q)
var x := the last node of p
if x in closed
continue
if x = goal
return p
add x to closed
foreach y in successors(x)
enqueue(q, p, y)
return failure A*改變它自己行為的能力基於啟發式代價函數，啟發式函數在游戲中非常有用。在速度和精確度之間取得折衷將會讓你的游戲運行得更快。在很多游戲中，你並不真正需要得到最好的路徑，僅需要近似的就足夠了。而你需要什麼則取決於游戲中發生著什麼，或者運行游戲的機器有多快。假設你的游戲有兩種地形，平原和山地，在平原中的移動代價是1而在山地的是3，那麼A星演算法就會認為在平地上可以進行三倍於山地的距離進行等價搜尋。 這是因為有可能有一條沿著平原到山地的路徑。把兩個鄰接點之間的評估距離設為1.5可以加速A*的搜索過程。然後A*會將3和1.5比較，這並不比把3和1比較差。然而，在山地上行動有時可能會優於繞過山腳下進行行動。所以花費更多時間尋找一個繞過山的演算法並不經常是可靠的。 同樣的，想要達成這樣的目標，你可以通過減少在山腳下的搜索行為來打到提高A星演算法的運行速率。弱項如此可以將A星演算法的山地行動耗費從3調整為2即可。這兩種方法都會給出可靠地行動策略 。

❼ 選擇排序演算法的思想是什麼

次序關系，採用分治策略，可在最壞的情況下用O(log n)完成搜索任務。它的基本思想是，將n個元素分成個數大致相同的兩半，取a[n/2]與欲查找的x作比較，如果x=a[n/2]則找到x，演算法終止。如果x<a[n/2]，則我們只要在數組a的左半部繼續搜索x（這里假設數組元素呈升序排列）。如果x>a[n/2]，則我們只要在數組a的右半部繼續搜索x。二分搜索法的應用極其廣泛，而且它的思想易於理解，但是要寫一個正確的二分搜索演算法也不是一件簡單的事。第一個二分搜索演算法早在1946年就出現了，但是第一個完全正確的二分搜索演算法直到1962年才出現。Bentley在他的著作《Writing Correct Programs》中寫道，90%的計算機專家不能在2小時內寫出完全正確的二分搜索演算法。問題的關鍵在於准確地制定各次查找范圍的邊界以及終止條件的確定，正確地歸納奇偶數的各種情況，其實整理後可以發現它的具體演算法是很直觀的，我們可用C++描述如下：

template<class Type>

int BinarySearch(Type a[],const Type& x,int n)

{

int left=0;

int right=n-1;

while(left<=right){

int middle=(left+right)/2;

if (x==a[middle]) return middle;

if (x>a[middle]) left=middle+1;

else right=middle-1;

}

return -1;

}

模板函數BinarySearch在a[0]<=a[1]<=...<=a[n-1]共n個升序排列的元素中搜索x,找到x時返回其在數組中的位置，否則返回-1。容易看出，每執行一次while循環，待搜索數組的大小減少一半,因此整個演算法在最壞情況下的時間復雜度為O(log n)。在數據量很大的時候，它的線性查找在時間復雜度上的優劣一目瞭然。
選擇排序
基本思想是：每次選出第i小的記錄，放在第i個位置（i的起點是0，按此說法，第0小的記錄實際上就是最小的，有點別扭，不管這么多了）。當i＝N－1時就排完了。

直接選擇排序
直選排序簡單的再現了選擇排序的基本思想，第一次尋找最小元素的代價是O(n)，如果不做某種特殊處理，每次都使用最簡單的尋找方法，自然的整個排序的時間復雜度就是O(n2)了。

冒泡法
為了在a[1]中得到最大值，我們將a[1]與它後面的元素a[2]，a[3]，...，a[10]進行比較。首先比較a[1]與a[2]，如果a[1]<a[2]，則將a[1]與a[2]交換，否則不交換。這樣在a[1]中得到的是a[1]與a[2]中的大數。然後將a[1]與a[3]比較，如果a[1]<a[3]，則將a[1]與a[3]交換，否則不交換。這樣在a[1]中得到的是a[1]，a[2]，a[3]中的最大值，...。如此繼續，最後a[1]與a[10]比較，如果a[1]<a[10]，則將a[1]與a[10]交換，否則不交換。這樣在a[1]中得到的數就是數組a的最大值（一共進行了9次比較）。

為了在a[2]中得到次大值，應將a[2]與它後面的元素a[3]，a[4]，...，a[10]進行比較。這樣經過8次比較，在a[2]是將得到次大值。

如此繼續，直到最後a[9]與a[10]比較，將大數放於a[9]，小數放於a[10]，全部排序到此結束。
從上面可以看出，對於10個數，需進行9趟比較，每一趟的比較次數是不一樣的。第一趟需比較9次，第二趟比較8次，...，最後一趟比較1次。

以上數組元素的排序，用二重循環實現，外循環變數設為i，內循環變數設為j。外循環重復9次，內循環依次重復9，8，...，1次。每次進行比較的兩個元素，第一個元素與外循環i有關的，用a[i]標識，第二個元素是與內循環j有關的，用a[j]標識，i的值依次為1,2,...,9，對於每一個i, j的值依次為i+1,i+2,...。