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