【正文】 弧線或節(jié)點 子節(jié)點終節(jié)點2023/5/15 28與或圖搜索與或圖搜索o 1)與或圖搜索的基本概念n 解圖的生成 ★o 解圖純粹是一種 “ 與 ” 圖o 解圖 中， 節(jié)點 或 節(jié)點組間 不存在 “或 ” 關(guān)系；o 所有葉節(jié)點都是終節(jié)點2023/5/15 29與或圖搜索與或圖搜索o 1)與或圖搜索的基本概念n 解圖的生成 ★n 自 根節(jié)點 開始選 K連接 。n 如此反復(fù)進行，直到所有 K連接 都指向 終節(jié)點 為止 .2023/5/15 302023/5/15 31與或圖搜索與或圖搜索o 1)與或圖搜索的基本概念n 解圖的生成 ★o 解圖純粹是一種 “ 與 ” 圖n 解圖 中， 節(jié)點 或 節(jié)點組間 不存在 “ 或 ” 關(guān)系；n 所有 葉節(jié)點 都是 終節(jié)點o 與或圖 中存在 “ 或 ” 關(guān)系， 搜索到多個解圖 ；2023/5/15 32與或圖搜索與或圖搜索o 2) 解圖 、解圖代價、能解節(jié)點和不能解節(jié)點的定義n (1)解圖 ——與或圖 （記為 G）任一節(jié)點（記為 n）到 終節(jié)點集合 的 解圖 （記為 G‘）是 G的 子圖 。o (3)否則不存在 n到 終節(jié)點集合 的 解圖 。 能解節(jié)點不能解節(jié)點能解節(jié)點不能解節(jié)點不能解節(jié)點2023/5/15 36與或圖的啟發(fā)式搜索與或圖的啟發(fā)式搜索o 與或圖中搜索的是 解圖 ，不是解答路徑；n 評價函數(shù) f(n)=h(n)n h(n)是對 n到 終節(jié)點集合 解圖最小解圖代價 的估計；o 與或圖中存在 “ 或 ” 關(guān)系 ， 會有 多個候選的局部解圖 ；n 選擇 局部解圖中可能代價最小 的用于下一步搜索。n 父節(jié)點 n的 K連接 指向的子節(jié)點： n1， n2， …nkn f(n) = K + h(n1) + h(n2) + … + h(nk)，代替 h(n)2023/5/15 37與或圖的啟發(fā)式搜索與或圖的啟發(fā)式搜索o 2) AO*算法 ★o 符號說明：n G搜索圖；n G’被選中的 待擴展局部解圖 ；n LGS待擴展 局部解圖集 ；n n0根節(jié)點 ，即初始狀態(tài)節(jié)點；n n被選中的 待擴展節(jié)點 ；n fi(n0)第 i個 待擴展局部解圖 的 可能代價 。2023/5/15 39與或圖的啟發(fā)式搜索與或圖的啟發(fā)式搜索o 搜索循環(huán)n 選擇 和 擴展 LGS中的 局部解圖 ；o ④ 選擇 LGS中 fi(n0)最小的待擴展解圖 G’；o ⑤ 隨機 選擇 G’中一個 非終節(jié)點 的 葉節(jié)點 作為 n；o ⑥ 擴展 nn 建立 K連接 ，子節(jié)點 ni并加入 G；n 計算 子節(jié)點 ni的 f(ni)=h(ni)o ⑦ 若 n存在 j個 K連接n LGS中刪除 G’n 將 j個 新的局部解圖 加入 LGS。o 遞歸地 作用到 初始節(jié)點 n0；n ⑨ 傳遞 新局部解圖中 節(jié)點的 能解性o 標記 作為 終節(jié)點 的子節(jié)點為 能解節(jié)點 ；o 遞歸地 傳遞節(jié)點的 能解性 到 初始節(jié)點 n0 。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候選的待擴展局部解圖集 LGS:102 1 1 4 2056 7 82 1 11 22023/5/15 4801 23 54循環(huán) 2候選的待擴展局部解圖集 LGS:102 11 4 2057 81 101 22 15623 422023/5/15 4901 23 54循環(huán) 2候選的待擴展局部解圖集 LGS:104 11 4 2077 81 101 23 16623 4225252023/5/15 5001 23 54候選的待擴展局部解圖集 LGS:104 11 4 2077 81 101 23 166 23 4213 143 0循環(huán) 32023/5/15 5101 23 54候選的待擴展局部解圖集 LGS:10411 4 2077 81 101 26 196 53 4213 143 0循環(huán) 33622023/5/15 5201 23 54循環(huán) 4候選的待擴展局部解圖集 LGS:104 11 4 2077 81 101 26 196 53 4213 143 01402023/5/15 5301 23 54循環(huán) 5 候選的待擴展局部解圖集 LGS:104 11 4 2077 81 101 26 196 53 4213 143 01401502023/5/15 5401 23 54循環(huán) 5 候選的待擴展局部解圖集 LGS:105 11 4 2087 81 201 26 196 53 4213 143 01401504712023/5/15 5501 23 54循環(huán) 6 候選的待擴展局部解圖集 LGS:105 11 42087 81 201 26 196 53 4213 143 0140150902023/5/15 5601 23 54搜索成功！ 候選的待擴展局部解圖集 LGS:105 11 4 2087 81 201 26 196 53 4213 143 0140150902023/5/15 57與或圖的啟發(fā)式搜索與或圖的啟發(fā)式搜索o 4）算法應(yīng)用的若干問題o 從局部解圖 G’中選擇加以擴展的節(jié)點 nn 與或圖搜索的是 解圖 而 非解路徑 ；n 選擇 f(n) = h(n)的值最小 的節(jié)點 n加以擴展并不一定會加速搜索過程；n 應(yīng)選擇導(dǎo)致解圖代價發(fā)生較大變化 的節(jié)點 n優(yōu)先加以擴展；o 使搜索的注意力快速地聚焦到實際代價較小的候選解圖上；n 簡單情況下，可 隨機選擇 加以擴展的節(jié)點。2023/5/15 59與或圖的啟發(fā)式搜索與或圖的啟發(fā)式搜索o 4）算法應(yīng)用的若干問題o 解圖代價的重復(fù)計算n 某些 子節(jié)點 可能會有 多個父節(jié)點 ；n 這種 子節(jié)點 到終節(jié)點集合的 解圖代價 在計算自根節(jié)點 n0出發(fā)的解圖時被 重復(fù)累計 。例如，如何表示博弈問題的狀態(tài)、博弈過程和博弈知識等。 2023/5/15 61n 所謂 “ 二人零和 ” ，是指在博弈中只有 “ 敵、我 ” 二方。 即：博弈的雙方有三種結(jié)局： (1)我勝： φ10；敵負： φ2= φ10。 (3)平局： φ1=0， φ2=0。例如，如何表示博弈問題的狀態(tài)、博弈過程和博弈知識等。 n 所謂 “ 非偶然 ，是指博弈雙方都可 根據(jù)得失大小進行分析 ，選取 我方贏得最大，敵方贏得最小的對策 ，而不是偶然的隨機對策。（ 2）在對壘過程中，任何一方都了解當(dāng)前的格局和過去的歷史。216。博弈的特點博弈的特點 2023/5/15 64o 另外一種博弈是機遇性博弈，是指不可預(yù)測性的博弈，如擲硬幣游戲等。 2023/5/15 66o 用數(shù)字序列加上一個說明表示一個狀態(tài)，其中數(shù)字表示不同堆中錢幣的個數(shù)，說明表示下一步由誰來分，o 如 （ 7， MIN） 表示只有一個由七枚錢幣組成的堆，由 MIN走， MIN有 3種