人工智能第三章_搜索策略-2(編輯修改稿)
2025-01-28 14:09 本頁面
【文章內(nèi)容簡介】 圖的啟發(fā)式搜索與或圖的啟發(fā)式搜索o 2) AO*算法 ★o 符號(hào)說明：n G搜索圖；n G’被選中的 待擴(kuò)展局部解圖 ；n LGS待擴(kuò)展 局部解圖集 ；n n0根節(jié)點(diǎn) ，即初始狀態(tài)節(jié)點(diǎn)；n n被選中的 待擴(kuò)展節(jié)點(diǎn) ；n fi(n0)第 i個(gè) 待擴(kuò)展局部解圖 的 可能代價(jià) 。2023/5/15 38與或圖的啟發(fā)式搜索與或圖的啟發(fā)式搜索o 2) AO*算法 ★o 算法劃分二個(gè)階段：n 初始化 o 建立只包含 初始狀態(tài)節(jié)點(diǎn) n0的搜索圖 G:={n0}；o 待擴(kuò)展局部解圖集 LGS:={}；n 搜索循環(huán)o 選擇 和 擴(kuò)展 LGS中的 局部解圖 ；o 精化 新局部解圖 代價(jià)的估計(jì) ；o 傳遞 節(jié)點(diǎn)的 能解性 。2023/5/15 39與或圖的啟發(fā)式搜索與或圖的啟發(fā)式搜索o 搜索循環(huán)n 選擇 和 擴(kuò)展 LGS中的 局部解圖 ；o ④ 選擇 LGS中 fi(n0)最小的待擴(kuò)展解圖 G’；o ⑤ 隨機(jī) 選擇 G’中一個(gè) 非終節(jié)點(diǎn) 的 葉節(jié)點(diǎn) 作為 n；o ⑥ 擴(kuò)展 nn 建立 K連接 ，子節(jié)點(diǎn) ni并加入 G；n 計(jì)算 子節(jié)點(diǎn) ni的 f(ni)=h(ni)o ⑦ 若 n存在 j個(gè) K連接n LGS中刪除 G’n 將 j個(gè) 新的局部解圖 加入 LGS。2023/5/15 40與或圖的啟發(fā)式搜索與或圖的啟發(fā)式搜索o 搜索循環(huán)n 選擇 和 擴(kuò)展 LGS中的 局部解圖 ；n ⑧ 精化 新 局部解圖 代價(jià)的估計(jì)o 用公式 f(n) = K + h(n1) + h(n2) + … + h(nk)取代原先的 f(n)。o 遞歸地 作用到 初始節(jié)點(diǎn) n0；n ⑨ 傳遞 新局部解圖中 節(jié)點(diǎn)的 能解性o 標(biāo)記 作為 終節(jié)點(diǎn) 的子節(jié)點(diǎn)為 能解節(jié)點(diǎn) ；o 遞歸地 傳遞節(jié)點(diǎn)的 能解性 到 初始節(jié)點(diǎn) n0 。f(n)=h(n)2023/5/15 412023/5/15 42與或圖的啟發(fā)式搜索與或圖的啟發(fā)式搜索o 2) AO*算法o AO*算法應(yīng)用例o 搜索過程中，啟發(fā)式函數(shù) h(ni)的 估算如下：o h(n0)=3o h(n1)=2o h(n2)=1o h(n3)=1o h(n4)=4o h(n5)=2o h(n6)=2o h(n7)=1o h(n8)=1o h(n13)=301 2 3 546 7 8 9 10 11 1213 14 15 16 1718 19 202023/5/15 43初始化候選的待擴(kuò)展局部解圖集 LGS:0 302023/5/15 4401 2 3 54循環(huán) 1候選的待擴(kuò)展局部解圖集 LGS:32 1 1 4 202023/5/15 4501 2 3 54循環(huán) 1候選的待擴(kuò)展局部解圖集 LGS:32 1 1 4 2031 201 2 3 5432 1 1 4 202023/5/15 4601 2 3 54循環(huán) 1候選的待擴(kuò)展局部解圖集 LGS:102 1 1 4 2051 2f(n) = K + h(n1) + h(n2) + … + h(nk)取代原先的 f(n)。f1(n0) = 2 + h(n1) + h(n2)=5f2(n0) = 3 + h(n3) + h(n4)+h(n5)=102023/5/15 4701 2 3 54循環(huán) 2候選的待擴(kuò)展局部解圖集 LGS:102 1 1 4 2056 7 82 1 11 22023/5/15 4801 23 54循環(huán) 2候選的待擴(kuò)展局部解圖集 LGS:102 11 4 2057 81 101 22 15623 422023/5/15 4901 23 54循環(huán) 2候選的待擴(kuò)展局部解圖集 LGS:104 11 4 2077 81 101 23 16623 4225252023/5/15 5001 23 54候選的待擴(kuò)展局部解圖集 LGS:104 11 4 2077 81 101 23 166 23 4213 143 0循環(huán) 32023/5/15 5101 23 54候選的待擴(kuò)展局部解圖集 LGS:10411 4 2077 81 101 26 196 53 4213 143 0循環(huán) 33622023/5/15 5201 23 54循環(huán) 4候選的待擴(kuò)展局部解圖集 LGS:104 11 4 2077 81 101 26 196 53 4213 143 01402023/5/15 5301 23 54循環(huán) 5 候選的待擴(kuò)展局部解圖集 LGS:104 11 4 2077 81 101 26 196 53 4213 143 01401502023/5/15 5401 23 54循環(huán) 5 候選的待擴(kuò)展局部解圖集 LGS:105 11 4 2087 81 201 26 196 53 4213 143 01401504712023/5/15 5501 23 54循環(huán) 6 候選的待擴(kuò)展局部解圖集 LGS:105 11 42087 81 201 26 196 53 4213 143 0140150902023/5/15 5601 23 54搜索成功！ 候選的待擴(kuò)展局部解圖集 LGS:105 11 4 2087 81 201 26 196 53 4213 143 0140150902023/5/15 57與或圖的啟發(fā)式搜索與或圖的啟發(fā)式搜索o 4）算法應(yīng)用的若干問題o 從局部解圖 G’中選擇加以擴(kuò)展的節(jié)點(diǎn) nn 與或圖搜索的是 解圖 而 非解路徑 ；n 選擇 f(n) = h(n)的值最小 的節(jié)點(diǎn) n加以擴(kuò)展并不一定會(huì)加速搜索過程；n 應(yīng)選擇導(dǎo)致解圖代價(jià)發(fā)生較大變化 的節(jié)點(diǎn) n優(yōu)先加以擴(kuò)展；o 使搜索的注意力快速地聚焦到實(shí)際代價(jià)較小的候選解圖上；n 簡單情況下，可 隨機(jī)選擇 加以擴(kuò)展的節(jié)點(diǎn)。2023/5/15 58與或圖的啟發(fā)式搜索與或圖的啟發(fā)式搜索o 4）算法應(yīng)用的若干問題o 算法 AO*與 A*的比較 ★n 解圖 ——解答路徑 ，n 估計(jì) 代價(jià)最小的局部解圖 加以優(yōu)先擴(kuò)展 ——OPEN表中 f(n)最小的節(jié)點(diǎn) ；n 只考慮 評(píng)價(jià)函數(shù) f(n)=h(n)——同時(shí)計(jì)算分量 g(n)和 h(n)，n 應(yīng)用 LGS存放 待擴(kuò)展局部解圖 ，并依據(jù) fi(n0)值排序 ——應(yīng)用 OPEN表和 CLOSE表分別存放 待擴(kuò)展節(jié)點(diǎn) 和 已擴(kuò)展節(jié)點(diǎn) ，并依據(jù) f(n)值 排序 OPEN表。2023/5/15 59與或圖的啟發(fā)式搜索與或圖的啟發(fā)式搜索o 4）算法應(yīng)用的若干問題o 解圖代價(jià)的重復(fù)計(jì)算n 某些 子節(jié)點(diǎn) 可能會(huì)有 多個(gè)父節(jié)點(diǎn) ；n 這種 子節(jié)點(diǎn) 到終節(jié)點(diǎn)集合的 解圖代價(jià) 在計(jì)算自根節(jié)點(diǎn) n0出發(fā)的解圖時(shí)被 重復(fù)累計(jì) 。17 817 814 151 25 17 8142 2162 41 182023/5/15 60博弈博弈 n 博弈提供了一個(gè)可構(gòu)造的任務(wù)領(lǐng)域，在這個(gè)領(lǐng)域中，具有明確的 勝利 和 失敗
物理相關(guān)推薦
鄂ICP備17016276號(hào)-1