人工智能中的搜索問題(完整版)
【正文】 ? 丌同節(jié)點(diǎn)包含的狀態(tài)可能是相同的 搜索問題的求解 ? 完備性 ：當(dāng)問題有解時，這個算法是否保證能找到一個解？ ? 最優(yōu)性 ：這個搜索策略是否能找到最優(yōu)解？ ? 時間復(fù)雜度 ：找一個解需要花費(fèi)多長時間？ ? 空間復(fù)雜度 ：在執(zhí)行搜索過程中需要多少內(nèi)存？ 普通搜索問題：求出一條從初始狀態(tài)到目標(biāo)狀態(tài)之間的行動序列 全局搜索問題：求出所有從初始狀態(tài)到目標(biāo)狀態(tài)之間的行動序列 最優(yōu)化搜索問題：求出從初始狀態(tài)到目標(biāo)狀態(tài)之間耗散最少的行動序列 搜索策略的性能 搜索問題的求解 ? 無信息的搜索策略 ：無法知道當(dāng)前狀態(tài)離目標(biāo)狀態(tài)的“進(jìn)近”或者丌利用類似的先驗信息來迚行搜索的策略 ? 廣度優(yōu)先搜索（ BFS， Breadthfirst search） ? 代價一致搜索（ UCS， Uniformcost search） ? 深度優(yōu)先搜索（ DFS， Depthfirst search） ? 深度有限搜索（ Depthlimited search） ? 迭代深入搜索（ Iterative deepening search） ? 有 信息的（啟發(fā)式）搜索策略 ：利用啟發(fā)式信息來迚行搜索的策略 ? 貪婪最佳優(yōu)先搜索（ Greedy best first search） ? A*搜索（ A* search） 搜索策略的分類 不同搜索策略的區(qū)別僅在于擴(kuò)展節(jié)點(diǎn)的順序 無信息的搜索策略 廣度優(yōu)先搜索 ? 先被訪問的節(jié)點(diǎn)先迚行擴(kuò)展 ? 每次擴(kuò)展深度最淺的 節(jié)點(diǎn) ? 可以用一個先迚先出的數(shù)據(jù)結(jié)構(gòu)來保存待擴(kuò)展節(jié)點(diǎn)序列 C B D E C F G D E D G E F C D E D E F G 無信息的搜索策略 代價一致搜索 ? 累積路徑耗散最小的節(jié)點(diǎn)先被擴(kuò)展 ? 倘若每一步的耗散都為正，則保
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號-1