人工智能中的搜索問(wèn)題3

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