[工學(xué)]狀態(tài)空間的搜索策略-展示頁
2025-01-28 11:37本頁面
【正文】 有解并成功退出 ， 解是追蹤圖 G中沿指針 從 n到 S這條路徑得到 （ 指針在第 ⑦ 步中設(shè)置 ） ； ⑥ 擴展 n， 生成不是 n的祖先的那些后繼節(jié)點的集合 M， 把M的這些成員作為 n的后繼節(jié)點添入圖 G中； 一般搜索過程算法流程 ⑦ 對 M中子節(jié)點進行如下處理： ? 對沒在 G中出現(xiàn)過的 （ 即沒在 OPEN或 CLOSED表中出現(xiàn)過的 ） M成員設(shè)置一個指向 n的指針 ， 把 M的這些成員加進 OPEN表； ? 已在 OPEN或 CLOSED表中的每個 M成員 ， 確定是否需要更改指向 n的指針方向； ? 已在 CLOSED表中的每個 M成員 ， 確定是否需要更改圖 G中它的每個后裔節(jié)點指向父節(jié)點的指針 。 ? 不同搜索策略 ， 節(jié)點在 OPEN表中的排列順序不同 。 一般搜索過程的數(shù)據(jù)結(jié)構(gòu) OPEN：未擴展節(jié)點表 ? 擴展：用合適算符對一個節(jié)點進行操作 ， 生成一組子節(jié)點 。 應(yīng)綜合考慮各種因素 ， 盡量使搜索系統(tǒng)的總開銷較小 。 ? 啟發(fā)式搜索 – 考慮特定問題領(lǐng)域可應(yīng)用的啟發(fā)性信息 ， 動態(tài)確定調(diào)用操作算子的步驟 ， 指導(dǎo)搜索朝最有希望的方向前進 。 ? 盲目搜索 – 對特定問題不具有任何有關(guān)信息 ， 按預(yù)定步驟 （ 依次或隨機 ）進行搜索 ， 搜索過程中獲得的中間信息不用來改進控制策略 。 搜索策略 搜索是人工智能中的一個基本問題 ， 是推理不可分割的一部分 ， 它直接關(guān)系到智能系統(tǒng)的性能與運行效率 ， 因而尼爾遜把它列為人工智能研究中的核心問題之一 。 已提出的搜索策略 求任一解路的搜索策略 ? 爬山法 （ Hill Climbing） 、 深度優(yōu)先法 （ Depthfirst） 、 限定范圍搜索法 （ Beam Search） 、 回溯法 （ Backtracking） 、 最好優(yōu)先法 （ Bestfirst） 求最佳解路的搜索策略 ? 寬度優(yōu)先法 （ Breadthfirst ） 、 分枝界限法 （ Branch and Bound） 、 動態(tài)規(guī)劃法 （ Dynamic Programming） 、 最佳圖搜索法 （ A*） 求與或關(guān)系解圖的搜索法 ? 一般的與或圖搜索法 （ AO*） 、 極大極小法 （ Minima） 、 ??剪枝法 （ Alphabeta Pruning） 、 啟發(fā)式剪枝法 （ Heuristic Pruning） 搜索策略選取操作算子的方式 搜索策略的主要任務(wù)是確定選取操作算子的方式 。 – 特點：能快速調(diào)用操作算子 。 – 特點：優(yōu)先選取合適的操作算子 ， 減少不必要搜索 ， 提高效率 啟發(fā)式搜索一般優(yōu)于盲目搜索 ， 但不能過于追求更多的甚至更完整的啟發(fā)信息 。 搜索策略 狀態(tài)空間的搜索策略 與 /或樹的搜索策略 狀態(tài)空間的搜索策略 一般搜索過程 盲目搜索策略 ? 回溯策略 、 寬度優(yōu)先搜索 （ 廣度優(yōu)先搜索 ） 、 深度優(yōu)先搜索 、 代價樹的寬度優(yōu)先搜索 、 代價樹的深度優(yōu)先搜索 啟發(fā)式搜索策略 ? 有序搜索 、 A*算法 搜索的基本問題 是否一定能找到一個解； 是否能終止運行或陷入一個死循環(huán)； 找到的是否是最佳解； 時間與空間復(fù)雜性如何 。 ? 存放剛生成的節(jié)點 。 CLOSED：已擴展節(jié)點表 ? 存放將擴展或已擴展節(jié)點 。 ⑧ 按某種方式或按某個試探值 ， 重排 OPEN表； ⑨ 轉(zhuǎn)第 ③ 步 。 各種搜索策略的 主要區(qū)別在于： 步驟 ⑧ 對 OPEN表上的節(jié)點進行排序的準則 ， 以便選出一個“ 最好 ” 的節(jié)點作為步驟 ④ 擴展使用 。 ? 可以用啟發(fā)信息為依據(jù) —— 啟發(fā)式搜索 。 ? 由圖 G中所有節(jié)點及反向指針 （ 在第 ⑦ 步 形成的指向父節(jié)點的指針 ） 構(gòu)成的集合 T， 是一棵樹 ， 稱為搜索樹 。 – G中每個節(jié)點 （ S除外 ） 都有且僅有一個指向 G中一個父節(jié)點的指針 。 – CLOSED表上的節(jié)點 ， 或者是已被擴展但沒有生成后繼節(jié)點的端節(jié)點 ， 或者是搜索樹的非端節(jié)點 。 – 從目標節(jié)點按指向父節(jié)點的指針 （ 第 ⑦ 步形成 ） 不斷回溯 ，能重現(xiàn)從初始節(jié)點到目標節(jié)點的成功路徑 。 ? 當搜索樹不再有末被擴展的端節(jié)點時 ， 即 OPEN表為空 ，搜索過程失敗 ， 從初始節(jié)點達不到目標節(jié)點 。 由于適用于一個節(jié)點的算符可能有多個 ， 此時就會生成一組子節(jié)點 。 余下的子節(jié)點記做集合 M， 加入
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1