學(xué)號:17101223364
姓名:張海潮
轉(zhuǎn)載自：http://m.manew.com/forum.php?mod=viewthread&tid=102750&mobile=2沫浆，有刪節(jié)
【嵌牛導(dǎo)讀】：
搜索是AI解決問題的通用技術(shù)游岳。有一些單人游戲，如瓷磚游戲，數(shù)獨苟径，填字游戲等。搜索算法幫助您在這樣的游戲搜索特定的位置注益。
【嵌牛鼻子】：人工智能 搜索 算法
【嵌牛提問】：典型的人工智能搜索算法有哪些轿塔？它們的特點是什么？
【嵌牛正文】：?
? ? 單Agent尋路問題
譬如3X3蛾坯， 4X4光酣，5X5的瓷磚游戲都是單一Agent的尋路挑戰(zhàn)。這些路徑都是由一塊塊空白的瓷磚組成脉课。玩家必須水平或者是垂直的移動這些瓷磚到空白的空間救军，來完成游戲目標(biāo)财异。
其他的single agent尋路問題還有例如，旅行推銷員問題唱遭，魔方以及定理證明類問題
搜索術(shù)語
Problem Space ?這是搜索發(fā)生的環(huán)境（一組狀態(tài)以及運算符來改變這些狀態(tài)）Problem Instance ?是初始狀態(tài)+目標(biāo)狀態(tài)戳寸。
Problem Space Graph ?代表問題狀態(tài)。狀態(tài)由結(jié)點表示拷泽，而運算符由邊緣表示Depth of a problem —操作數(shù)從初始狀態(tài)到目標(biāo)狀態(tài)長度最短的路徑或者是最短的序列
·
·
Space Complexity? ?存儲在內(nèi)存中的最大節(jié)點數(shù)疫鹊。
Time Complexity ?創(chuàng)建的節(jié)點的最大數(shù)目
Admissibility ?能解決問題的的最佳解決方案算法
Branching Factor ? 在問題空間圖表中子節(jié)點的平均數(shù)
Depth ?從初始狀態(tài)到目標(biāo)狀態(tài)的最短路徑長度
Brute-強(qiáng)制搜索策略
他們是最簡單的，因為他們不需要任何特定領(lǐng)域的知識司致。在可能狀態(tài)很少的情亂他們可以最好的發(fā)揮性能
· 要求?
· ·狀態(tài)描述
· ·一套有效的操作數(shù)
· ·初始狀態(tài)
· ·目標(biāo)狀態(tài)描述
Breadth-優(yōu)先搜索
它從根節(jié)點開始拆吆，起初探索相鄰節(jié)點然后向下一級的相鄰節(jié)點探索。它一次生成一棵樹直到解決方案被發(fā)現(xiàn)脂矫。使用FIFO隊列數(shù)據(jù)結(jié)構(gòu)可以實現(xiàn)枣耀，這個方法提供了解決方案的最短路徑
如果分支因子（對于一個給定的節(jié)點的子節(jié)點的平均數(shù)）=b，深度=d庭再，那么d級別的節(jié)點數(shù)量= bd.
也就是說捞奕，在最壞的情況下，在這一級要創(chuàng)建的節(jié)點總數(shù)為 b + b2 + b3 + … + bd
缺點-因為每一級的節(jié)點將會被保留來創(chuàng)造下一級拄轻。它將消耗大量的內(nèi)存空間颅围。存儲節(jié)點的空間需求是呈指數(shù)級增長的。
它的復(fù)雜性取決于節(jié)點的數(shù)量哺眯。它可以檢查重復(fù)節(jié)點谷浅。
Depth-優(yōu)先搜索
它實現(xiàn)了遞歸后進(jìn)先出棧的數(shù)據(jù)結(jié)構(gòu)。和Breadth-First方法相同奶卓，它創(chuàng)建了相同的一套節(jié)點一疯，只不過有不同的順序
由于單路徑上的節(jié)點被存儲在每次迭代從根到葉節(jié)點，存儲節(jié)點的空間要求是線性的夺姑。分支因子帶寬深度為 m墩邀，存儲空間為 BM。
缺點-這個算法可能不會終止并且會在一個路徑上無限2延伸盏浙。這個問題的解決方案是選擇一個截止深度眉睹。如果給定一個截止深度cut-off isd，如果給定的截止深度小于d,那么這個算法有可能會失敗废膘。如果選擇的截止深度超過d,那么執(zhí)行的時間將會增加
其復(fù)雜性取決于路徑數(shù)竹海。它不能檢查重復(fù)節(jié)點。
雙向搜索
它從初始狀態(tài)和目標(biāo)狀態(tài)向后搜索丐黄，直到兩者達(dá)到共同狀態(tài)斋配。
從初始狀態(tài)開始的路徑被連接從目標(biāo)狀態(tài)出發(fā)的逆路徑。每個搜索只完成了一半的總路徑。
成本一致搜索
排序是以節(jié)點路徑的成本增加為代價的艰争。它總會引起最小成本節(jié)點的擴(kuò)大坏瞄。如果每個過度都有相同的成本，那么他和雙向優(yōu)先搜索是一致的
以增加開銷為代價的情況下甩卓，成本一致搜索得以探索路徑
缺點—可能存在很多長的路徑開銷≤ C*鸠匀。而Uniform Cost search必須探索所有的路徑。
迭代加深深度優(yōu)先搜索
它執(zhí)行深度優(yōu)先搜索到1級逾柿，然后從頭開始缀棍，以第2級執(zhí)行一個完整的深度優(yōu)先搜索，并繼續(xù)以這種方式机错，直到找到解決方案睦柴。
它不會創(chuàng)建一個節(jié)點，直到所有較低的節(jié)點生成毡熏。它只保存一組節(jié)點。當(dāng)它在深度 D發(fā)現(xiàn)一個解決方案時侣诵，算法結(jié)束.在深度 D 創(chuàng)建節(jié)點的數(shù)目是bd痢法，深度 D-1 創(chuàng)建的節(jié)點為 bd-1
Informed（啟發(fā)式）搜索策略
為了解決大的問題，大量的可能狀態(tài)杜顺，需要添加特定問題的知識财搁，以提高搜索算法的效率。
啟發(fā)式評估功能
他們計算兩個狀態(tài)之間的最佳路徑的成本躬络。一個推箱子的啟發(fā)函數(shù)通過計算每一個瓷磚從目標(biāo)狀態(tài)移動到現(xiàn)在的狀態(tài)需要移動的數(shù)量尖奔，然后添加這些數(shù)量給所有的瓷磚。
純粹的啟發(fā)式搜索
它根據(jù)啟發(fā)式值的順序擴(kuò)展節(jié)點穷当。它創(chuàng)造了兩個列表提茁，一個未開放的列表給已經(jīng)被擴(kuò)展的節(jié)點和一個開放的列表對于已經(jīng)創(chuàng)建但是還沒有被擴(kuò)展的節(jié)點
在每次迭代中，一個具有最小啟發(fā)式值的節(jié)點被擴(kuò)展馁菜，所有子節(jié)點都被創(chuàng)建并放置在封閉列表中茴扁。然后，啟發(fā)式函數(shù)被施加到子節(jié)點汪疮，它們被放置在開放列表中峭火，根據(jù)它們的啟發(fā)式值。較短的路徑被保存智嚷，較長的路徑被處理卖丸。
A* 搜索
他是著名的最佳優(yōu)先搜索策略。他避免了開銷已經(jīng)很昂貴的擴(kuò)展路徑盏道，而是首先擴(kuò)展最有可能的路徑稍浆。
f(n) = g(n) + h(n), 其中
g(n)為到達(dá)節(jié)點的成本（到目前為止）
h(n)為從節(jié)點到目標(biāo)的估計成本
f(n)為通過N到目標(biāo)的估計總成本。它采用優(yōu)先級隊列來增加F（n）。
Greedy Best First Search
它擴(kuò)展預(yù)估是最接近的目標(biāo)的節(jié)點粹湃。它在f（n）= H（n）的基礎(chǔ)上擴(kuò)展節(jié)點恐仑。使用優(yōu)先級隊列實現(xiàn)。
缺點—他有可能陷在死循環(huán)为鳄，不是最優(yōu)的方案
局部搜索算法
他們從一個前瞻性的解決方案開始裳仆，然后移動到鄰近的解決方案。他們可以返回一個有效的解決方案孤钦，即使它在結(jié)束前的任何時候都可以被中斷歧斟。
爬山搜尋法
它是一個迭代算法，從一個任意的問題的解決方案偏形，并試圖找到一個更好的解決方案静袖，通過改變一個單一的元素增量的解決方案。如果變化產(chǎn)生更好的解決方案俊扭，增量變化作為一個新的解決方案队橙。重復(fù)這個過程，直到?jīng)]有進(jìn)一步的改進(jìn)萨惑。
function Hill-Climbing會返回一個局部最大值的狀態(tài)
inputs: problem, a problem
local variables: current, a node
? ? ? ? ? ? ? ? neighbor, a node
current <-Make_Node(Initial-State[problem])
loop
? do neighbor <- a highest_valued successor of current
? ? ? if Value[neighbor] ≤ Value[current] then
? ? ? return State[current]
? ? ? current <- neighbor? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
end
缺點 ?這種算法既不完整捐康，也不是最優(yōu)的。
局部剪枝搜索
在該算法中庸蔼，它持有k個數(shù)在任何給定的時間解总。在開始時，這些狀態(tài)是隨機(jī)生成的姐仅。這些K狀態(tài)的繼承人的計算與幫助的目標(biāo)函數(shù)花枫。如果這些后繼的任何一個是目標(biāo)函數(shù)的最大值，則該算法停止掏膏。
否則（初始狀態(tài)k和k的狀態(tài)的繼任者= 2K）狀態(tài)被放置在一個池劳翰。然后對池進(jìn)行數(shù)值排序。最高k狀態(tài)被選擇為新的初始狀態(tài)壤追。這個過程一直持續(xù)直到達(dá)到最大值磕道。
搜索功能（ 問題，K）行冰，返回一個解決狀態(tài)溺蕉。
start with k randomly generated states
loop
? generate all successors of all k states
? if any of the states = solution, then return the state
? else select the k best successors
end
模擬退火法
退火是加熱和冷卻金屬以改變其內(nèi)部結(jié)構(gòu)以改變其物理性質(zhì)的過程。當(dāng)金屬冷卻時悼做，它的新結(jié)構(gòu)被固定疯特，金屬保留其新獲得的特性。在模擬退火過程中肛走，溫度保持不變漓雅。
· 開始
· Initialize k = 0; L = integer number of variables;
· From i → j, search the performance difference ?.
· If ? <= 0 then accept else if exp(-D/T(k)) > random(0,1) then accept;
· Repeat steps 1 and 2 for L(k) steps.
· k = k + 1;
End
Travelling Salesman Problem
在該算法中，目標(biāo)是找到一個低成本的路線，從一個城市開始邻吞，訪問所有城市的路線完全一次组题，并在同一個起點城市結(jié)束行程。
Start
? Find out all (n -1)! Possible solutions, where n is the total number of cities.
? Determine the minimum cost by finding out the cost of each of these (n -1)! solutions.
? Finally, keep the one with the minimum cost.
end
