人工智能中的搜索問題3

SearchingProblemsinAI人工智能中的搜索問題智能體的初始形狀是確定的智能體當前形狀能否為目的形狀是可以檢測的智能體的形狀空間是離散的智能體在每個形狀可以采取的合法行動和相應后繼形狀是確定的環(huán)境是靜態(tài)的途徑的耗散函數(shù)是知的什么是搜索問題搜索問題：知智能體的初始形狀和目的形狀，求解一個行動序列使得智能體能從初始形狀轉移到目的形狀。假設所求序列可以使得總耗散最低，那么問題稱為最優(yōu)搜索問題。幾個典型的搜索問題起始形狀：Arad途徑規(guī)劃問題目的形狀：Bucharest合法行動與后繼確實定性：與某一城市相鄰的城市才干成為合法后繼形狀空間的離散性：城市是離散的環(huán)境的靜態(tài)性：城市的相對位置不會改動途徑的耗散函數(shù)確實定性：城市之間的間隔是知的搜索問題：從Arad到Bucharest的途徑最優(yōu)化搜索問題：從Arad到Bucharest的最短途徑幾個典型的搜索問題起始形狀8-Puzzle問題目的形狀合法行動與后繼確實定性：只需空格周圍的格子是可以挪動的形狀空間的離散性：8個格子的陳列方式是離散的環(huán)境的靜態(tài)性：九宮格的大小和外形在格子挪動過程中不會改動途徑的耗散函數(shù)確實定性：相鄰兩個形狀之間所需步驟為1搜索問題：從起始形狀到目的形狀的挪動方法最優(yōu)化搜索問題：從起始形狀到目的形狀步驟最少的挪動方法華容道是不是一個搜索問題？幾個典型的搜索問題八皇后問題合法行動與后繼確實定性：滿足棋盤上一切皇后不能相互攻擊的后繼才是合法的形狀空間的離散性：0-8個皇后在棋盤上的擺放方式環(huán)境的靜態(tài)性：棋盤的格局和大小不會改動途徑的耗散函數(shù)確實定性：相鄰兩個形狀之間所需步驟為1搜索問題：求出〔一切〕合法的目的形狀起始形狀：空的棋盤目的形狀：棋盤上擺了八個皇后，并且恣意兩個皇后都不能相互攻擊。目的形狀不確定，但是當前形狀能否為目的形狀是可以檢測的。搜索問題的組成初始形狀：智能體所處的初始形狀后繼函數(shù)：輸入給定形狀，可以輸出合法行動和相應的后繼形狀目的測試：用來確定給定的形狀能否為目的形狀途徑耗散函數(shù)：在兩個給定形狀之間進展轉移所需的“代價〞普通搜索問題：求出一條從初始形狀到目的形狀之間的行動序列全局搜索問題：求出一切從初始形狀到目的形狀之間的行動序列最優(yōu)化搜索問題：求出從初始形狀到目的形狀之間耗散最少的行動序列搜索問題的求解一切搜索過程都可以用搜索樹算法來進展表示搜索樹搜索問題的求解搜索樹實例搜索問題的求解搜索樹實例搜索問題的求解搜索樹實例搜索問題的求解節(jié)點與形狀的區(qū)別節(jié)點〔Node〕是一種數(shù)據(jù)構造，每個節(jié)點的信息包括當前形狀、父節(jié)點、子節(jié)點、深度和途徑耗散形狀〔State〕只是一種系統(tǒng)能夠存在的方式不同節(jié)點包含的形狀能夠是一樣的搜索問題的求解完備性：當問題有解時，這個算法能否保證能找到一個解？最優(yōu)性：這個搜索戰(zhàn)略能否能找到最優(yōu)解？時間復雜度：找一個解需求破費多長時間？空間復雜度：在執(zhí)行搜索過程中需求多少內存？普通搜索問題：求出一條從初始形狀到目的形狀之間的行動序列全局搜索問題：求出一切從初始形狀到目的形狀之間的行動序列最優(yōu)化搜索問題：求出從初始形狀到目的形狀之間耗散最少的行動序列搜索戰(zhàn)略的性能搜索問題的求解無信息的搜索戰(zhàn)略：無法知道當前形狀離目的形狀的“遠近〞或者不利用類似的先驗信息來進展搜索的戰(zhàn)略廣度優(yōu)先搜索〔BFS，Breadth-firstsearch〕代價一致搜索〔UCS，Uniform-costsearch〕深度優(yōu)先搜索〔DFS，Depth-firstsearch〕深度有限搜索〔Depth-limitedsearch〕迭代深化搜索〔Iterativedeepeningsearch〕有信息的〔啟發(fā)式〕搜索戰(zhàn)略：利用啟發(fā)式信息來進展搜索的戰(zhàn)略貪婪最正確優(yōu)先搜索〔Greedybestfirstsearch〕A*搜索〔A*search〕搜索戰(zhàn)略的分類不同搜索戰(zhàn)略的區(qū)別僅在于擴展節(jié)點的順序無信息的搜索戰(zhàn)略廣度優(yōu)先搜索先被訪問的節(jié)點先進展擴展每次擴展深度最淺的節(jié)點可以用一個先進先出的數(shù)據(jù)構造來保管待擴展節(jié)點序列CBDECFGDEDGEFCDEDEFG無信息的搜索戰(zhàn)略代價一致搜索累積途徑耗散最小的節(jié)點先被擴展倘假設每一步的耗散都為正，那么保證可以得到最優(yōu)解假設單步耗散相等，該算法和廣度優(yōu)先搜索一樣CBDE？？？CDE？為累積途徑耗散最小的節(jié)點無信息的搜索戰(zhàn)略深度優(yōu)先搜索后被訪問的節(jié)點先進展擴展每次擴展深度最深的節(jié)點“一條路走到黑〞，對于無邊境搜索問題無法保證完備性可以用一個后進先出的數(shù)據(jù)構造來保管待擴展節(jié)點序列無信息的搜索戰(zhàn)略深度優(yōu)先搜索CBEDDIHCECEDCEIH無信息的搜索戰(zhàn)略深度優(yōu)先搜索CHICECEICEIHEICE無信息的搜索戰(zhàn)略深度有限搜索深度優(yōu)先搜索它能夠錯誤地選擇一條分支并且沿著一條很長的〔甚至是無限的〕途徑不斷走下去對于無邊境的搜索問題，可以經過對深度優(yōu)先搜索提供一個預先設定的深度限制m來防止深度優(yōu)先搜索進入死循環(huán)假設目的深度d>深度限制m，深度有限搜索能夠無法得到解，因此完備性也無法保證無信息的搜索戰(zhàn)略迭代深化搜索用來尋覓最適宜的深度限制的通用戰(zhàn)略，經常和深度優(yōu)先搜索結合運用不斷增大深度限制，直到找到目的節(jié)點結合了深度有限搜索的優(yōu)點，又保證了完備性，還能保證得到最優(yōu)解無信息的搜索戰(zhàn)略迭代深化搜索無信息的搜索戰(zhàn)略戰(zhàn)略之間的比較為了防止含有一樣形狀的節(jié)點被反復擴展，可以用一個數(shù)據(jù)構造來記錄一切被訪問過的節(jié)點。假設當前待擴展節(jié)點與某個已訪問過的節(jié)點對應的形狀一樣的話，那么當前節(jié)點將不會被擴展。這時樹搜索〔TreeSearch〕戰(zhàn)略將成為圖〔GraphSearch〕戰(zhàn)略啟發(fā)式搜索戰(zhàn)略最正確搜索戰(zhàn)略最正確優(yōu)先搜索的通用思想：用一個評價函數(shù)f(n)來對節(jié)點進展評價。在擴展節(jié)點的過程中，從候選節(jié)點中選擇f(n)最小的節(jié)點來進展擴展。對于BFS，f(n)表示節(jié)點深度；對于UCS，f(n)表示節(jié)點的累計途徑耗散；對于DFS，f(n)表示節(jié)點深度的負值很多時候f(n)不能真正度量節(jié)點的好壞，因此可以思索引進啟發(fā)式信息來估計節(jié)點離目的形狀的間隔啟發(fā)式函數(shù)：h(n)=從節(jié)點n到目的節(jié)點的最低耗散途徑的耗散估計值啟發(fā)式搜索戰(zhàn)略貪婪最正確優(yōu)先搜索評價函數(shù)f(n)=h(n)在這個途徑規(guī)劃問題中，h(n)取為當前城市離目的Bucharest的直線間隔啟發(fā)式搜索戰(zhàn)略貪婪最正確優(yōu)先搜索評價函數(shù)f(n)=h(n)啟發(fā)式搜索戰(zhàn)略貪婪最正確優(yōu)先搜索評價函數(shù)f(n)=h(n)啟發(fā)式搜索戰(zhàn)略貪婪最正確優(yōu)先搜索評價函數(shù)f(n)=h(n)啟發(fā)式搜索戰(zhàn)略貪婪最正確優(yōu)先搜索與深度優(yōu)先搜索一樣，它更傾向于沿著一條途徑搜索下去直到目的由于在擴展節(jié)點時沒有思索累計途徑耗散，因此它也不能保證得到最優(yōu)解假設形狀空間是無限的，它也能夠是不完備的啟發(fā)式搜索戰(zhàn)略A*搜索為了彌補貪婪最正確優(yōu)先搜索無法找到最優(yōu)解的缺陷，思索在評價函數(shù)里參與累計途徑耗散，由此構成A*搜索算法評價函數(shù)f(n)=g(n)+h(n)g(n)：從起始節(jié)點到節(jié)點n的途徑耗散h(n)：從節(jié)點n到目的節(jié)點的最低耗散途徑的耗散估計值f(n)：經過節(jié)點n到目的節(jié)點的總耗散估計值啟發(fā)式搜索戰(zhàn)略A*搜索啟發(fā)式搜索戰(zhàn)略A*搜索啟發(fā)式搜索戰(zhàn)略A*搜索啟發(fā)式搜索戰(zhàn)略