人工智能中的搜索問(wèn)題(文件)
【正文】 息的搜索策略 深度優(yōu)先搜索 ? 后被訪問(wèn)的節(jié)點(diǎn)先迚行擴(kuò)展 ? 每次擴(kuò)展深度 最深的節(jié)點(diǎn) ? “一條路走到黑”，對(duì)于無(wú)邊界搜索問(wèn)題無(wú)法保證完備性 ? 可以用一個(gè)后迚先出的數(shù)據(jù)結(jié)構(gòu)來(lái)保存待擴(kuò)展節(jié)點(diǎn)序列 無(wú)信息的搜索策略 深度優(yōu)先搜索 C B E D D I H C E C E D C E I H 無(wú)信息的搜索策略 深度優(yōu)先搜索 C H I C E C E I C E I H E I C E 無(wú)信息的搜索策略 深度 有限 搜索 ? 深度優(yōu)先搜索它可能錯(cuò)誤地選擇一條分支并且沿著一條徆長(zhǎng)的（甚至是無(wú)限的）路徑一直走下去 ? 對(duì)于無(wú)邊界的搜索問(wèn)題，可以通過(guò)對(duì)深度優(yōu)先搜索提供一個(gè)預(yù)先設(shè)定的深度限制 m來(lái)防止深度優(yōu)先搜索迚入死循環(huán) ? 如果目標(biāo)深度 d深度限制 m，深度有限搜索可能無(wú)法得到解，因此完備性也無(wú)法保證 無(wú)信息的搜索策略 迭代深入搜索 ? 用來(lái)尋找最合適的深度限制的通用策略，經(jīng)常和深度優(yōu)先搜索結(jié)合使用 ? 丌斷增大深度限制，直到找到目標(biāo)節(jié)點(diǎn) ? 結(jié)合了深度有限搜索的優(yōu)點(diǎn)，又保證了完備性，還能保證得到最優(yōu)解 無(wú)信息的搜索策略 迭代深入搜索 無(wú)信息的搜索策略 策略之間的比較 為了避免含有相同狀態(tài)的節(jié)點(diǎn)被重復(fù)擴(kuò)展，可以用一個(gè)數(shù)據(jù)結(jié)構(gòu)來(lái)記錄所有被訪問(wèn)過(guò)的節(jié)點(diǎn)。 ? 對(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)的好壞，因此可以考慮引迚啟發(fā)式信息來(lái)估計(jì)節(jié)點(diǎn)離目標(biāo)狀態(tài)的距離 啟發(fā)式函數(shù)： h(n)=從節(jié)點(diǎn) n到目標(biāo)節(jié)點(diǎn)的最低耗散路徑的耗散估計(jì)值 啟發(fā)式 搜索策略 貪婪最佳優(yōu)先搜索 評(píng)價(jià)函數(shù) f(n)=h(n) 在這個(gè)路徑規(guī)劃問(wèn)題
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號(hào)-1