【正文】 行擴展； (3) 為每個子節(jié)點設置指向父節(jié)點的指針； (4) 選擇合適的子節(jié)點作為當前節(jié)點 ， 反復執(zhí)行第 (2)步和第 (3)步 ， 在此期間需要 多次調用可解標記過程或不可解標記過程 ， 直到初始節(jié)點被標記為可解節(jié)點或不可解節(jié)點為止 。 當搜索成功時 ， 經可解標記過程標識的由初始節(jié)點及其下屬的可解節(jié)點構成的子樹稱為解樹 。 搜索過程中的可解標記過程與不可解標記過程都是自下而上進行的 ， 即由子節(jié)點的可解性確定父節(jié)點的可解性； 在與／或樹中 ， 除端節(jié)點和終止節(jié)點外 ， 一個節(jié)點的可解性完全是由其子節(jié)點來決定的 。 對與節(jié)點 ， 只有其所有子節(jié)點都為可解時它才為可解 ， 只要有一個子節(jié)點不可解它就是不可解的；對或節(jié)點 ， 只要有一個子節(jié)點可解它就是可解的 ， 僅當所有子節(jié)點都是不可解時它才為不可解 。 這種由可解子節(jié)點來確定其父節(jié)點為可解節(jié)點的過程稱為可解標記過程； 與／或樹的廣度優(yōu)先搜索 40 1 2 3 4 5 A B C t3 t1 t2 與／或樹的深度優(yōu)先搜索 1→ 2→ 3→ 4→ 5 1→ 3→ 5→ 2→ 4 與／或樹啟發(fā)搜索 41 解樹的代價 (1) 若 n為終止節(jié)點，則其代價 h(n)＝ 0 (2) 若 n為或節(jié)點，且子節(jié)點為 n1， n2．．．，則 n的代價為 : h(n)＝ min{C (n， ni)+h(ni)} 其中 C (n， ni)是節(jié)點 n到其子節(jié)點 ni的邊代價。 (3) 若 n為與節(jié)點，則 n的代價可用和代價法或最大代價法。 若用和代價法，則其計算公式為： h(n)＝ ∑{C (n， ni)+h(ni)} 若用最大代價法，則其計算公式為： h(n)＝ max{C (n， ni)+h(ni)} (4) 若 n是端節(jié)點，但又不是終止節(jié)點，則 n不可擴展，其代價定義為 h(n)＝ ∞ (5) 根節(jié)點的代價即為解樹的代價。 S0 2 2 4 6 A E F t3 t1 t2 2 B D 5 3 1 t4 按和代價： h(So)＝ 2+4+6+2＝ 14 按最大代價： h(So)=2+6+2=10 按和代價： h(So)＝ 1+5+3+2=11 按最大代價： h(So)＝ 1+5+2＝ 8 希望 解樹 42 定義 希望解樹 T (1) 初始節(jié)點 S0在希望樹 T中； (2) 如果 n是具有子節(jié)點 nl， n2， 的或節(jié)點 ， 則 n的某個子節(jié)點 ni在希望樹 T中的充分必要條件是 h(n)＝ min{C (n， ni)+h(ni)} (3) 如果是與節(jié)點 ， 則 n的全部子節(jié)點都在希望樹 T中 。 與／或樹的啟發(fā)搜索步驟 (1) 把初始節(jié)點 S0放人 Open表中，計算 h(S0)； (2) 計算希望樹 T； (3) 依次在 Open表中取出 T的端節(jié)點放人 Closed表，并記該節(jié)點為 n； (4) 如果節(jié)點 n為終止節(jié)點，則做下列工作： ① 標記節(jié)點 n為可解節(jié)點； ② 在 T上應用可解標記過程，對 n的先輩節(jié)點中的所有可解節(jié)點進行標記； ③ 如果初始節(jié)點 S0能夠被標記為可解節(jié)點，則 T就是最優(yōu)解樹，成功退出； ④ 否則，從 Open表中刪去具有可解先輩的所有節(jié)點； ⑤ 轉第 (2)步。 (5) 如果節(jié)點 n不是終止節(jié)點，但可擴展，則做下列工作： ① 擴展節(jié)點 n，生成 n的所有子節(jié)點； ② 把這些子節(jié)點都放入 Open表中，并為每一個子節(jié)點設置指向父節(jié)點 n的指針； ③ 計算這些子節(jié)點及其先輩節(jié)點的 h值； ④ 轉第 (2)步。 (6) 如果節(jié)點 n不是終止節(jié)點，且不可擴展，則做下列工作： ① 標記節(jié)點 n為不可解節(jié)點； ② 在 T上應用不可解標記過程，對 n的先輩節(jié)點中的所有不可解節(jié)點進行標記； ③ 如果初始節(jié)點 S。能夠被標記為不可解節(jié)點，則問題無解，失敗退出； ④ 否則，從 Open表中刪去具有不可解先輩的所有節(jié)點； ⑤ 轉第 (2)步。 例子 S0 8 9 h值 3 3 A E 2 B D 11節(jié)點代價 7 C F 7 S0 8 9 3 3 A E 2 B D 11 C F 7 6 3 2 2 2 擴展 So后的與／或樹 擴展 E 后的與／或樹 希望樹 每邊代價為 1 希望樹 例子 0 0 2 2 0 0 5 0 3 2 2 2 G 2 J 6 M 2 9 7 6 H I K L N P 7 S0 8 9 3 3 A E 3 B D 11 C F 7 6 0 0 2 2 3 2 2 2 G 2 J 6 7 6 H I K L 7 S0 8 9 3 3 A E 3 B D 11 C F 博弈樹的啟發(fā)式搜索 46 雙人 完備信息博弈 ， 就是兩位選手對壘 ， 輪流走步 ， 每一方不僅知道對方已經走過的棋步 ， 而且還能估計出對方未來的走步 。 對弈的結果是一方贏 ， 另一方輸；或者雙方和局 。 這類博弈的實例有象棋 、 圍棋等 。 所謂 機遇性博弈 ， 是指存在不可預測性的博弈 ， 例如擲幣等 。 對機遇性博弈 ，由于不具備完備信息 ， 因此我們不作討論 。 在雙人完備信息博弈過程中 ， 雙方都希望自己能夠獲勝 。 因此 ， 當任何一方走步時 ， 擇對自己最為有利 ， 而對另一方最為不利的行動方案 。 假設博弈的一方為 M， 另 m。 在博弈過程的每一步 ， 可供 M和 m選擇的行動方案都可能有多種 。 從 M觀點看 ， 可供自己選擇的那些行動方案之間是 “ 或 ” 的關系 ，原因是主動權掌握在 M選擇哪個方案完全是由自己決定的；而對那些可供 m選擇的行動方案之間則是與關系 ， 原因是主動權掌握在 m的手里 ， 任何一個方案都有可能被 m選中 ， M必須那種對自己最為不利的情況的發(fā)生 。 若把雙人完備信息博弈過程用圖表示出來 ， 就可得到一棵與／或樹 ， 這種與／或樹被稱博弈樹 。 在博弈樹中 ， 那些下一步該 M走步的節(jié)點稱為 M節(jié)點 ， 而下一步該 m走的 節(jié)點稱為 m節(jié)點 。 博弈樹的啟發(fā)式搜索 2 47 博弈樹具有如下特點： (1) 博弈的初始狀態(tài)是初始節(jié)點； (2) 博弈樹中的 “ 或 ” 節(jié)點和 “ 與 ” 節(jié)點是逐層交替出現的； (3) 整個博弈過程始終站在某一方的立場上，所有能使自己一方獲勝的終局都是習題，相應的節(jié)點是可解節(jié)點；所有使對方獲勝的終局都是不可解節(jié)點。例如，站在 MAX有能使 MAX方獲勝的節(jié)點都是可解節(jié)點，所有能使 MIN方獲勝的節(jié)點都是不可解節(jié)點。