【正文】 定義 希望解樹 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中 。 最有希望成為最優(yōu)解樹的樹，希望解樹是隨搜索過程不斷改進 與／或樹的啟發(fā)搜索步驟 (1) 把初始節(jié)點 S0放人 Open表中，計算 h(S0)； (2) 計算希望樹 T； (3) 依次在 Open表中取出 T的端節(jié)點放人 Closed表，并記該節(jié)點為 n； (4) 如果節(jié)點 n為終止節(jié)點，則做下列工作： ① 標記節(jié)點 n為可解節(jié)點； ② 在 T上應(yīng)用可解標記過程，對 n的先輩節(jié)點中的所有可解節(jié)點進行標記； ③ 如果初始節(jié)點 S0能夠被標記為可解節(jié)點，則 T就是最優(yōu)解樹，成功退出； ④ 否則，從 Open表中刪去具有可解先輩的所有節(jié)點； ⑤ 轉(zhuǎn)第 (2)步。 (5) 如果節(jié)點 n不是終止節(jié)點，但可擴展，則做下列工作： ① 擴展節(jié)點 n，生成 n的所有子節(jié)點； ② 把這些子節(jié)點都放入 Open表中，并為每一個子節(jié)點設(shè)置指向父節(jié)點 n的指針； ③ 計算這些子節(jié)點及其先輩節(jié)點的 h值； ④ 轉(zhuǎn)第 (2)步。 (6) 如果節(jié)點 n不是終止節(jié)點，且不可擴展，則做下列工作： ① 標記節(jié)點 n為不可解節(jié)點； ② 在 T上應(yīng)用不可解標記過程，對 n的先輩節(jié)點中的所有不可解節(jié)點進行標記； ③ 如果初始節(jié)點 S。能夠被標記為不可解節(jié)點，則問題無解，失敗退出； ④ 否則，從 Open表中刪去具有不可解先輩的所有節(jié)點； ⑤ 轉(zhuǎn)第 (2)步。 Open表， Closed表是數(shù)據(jù)結(jié)構(gòu)； Open表放剛生成，還沒有擴展的節(jié)點 Closed表放已經(jīng)擴展 ，或者要擴展的節(jié)點。 與／或樹的啟發(fā)搜索結(jié)果例子 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 E 3 B D 11 C F 7 6 例子 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后的與／或樹（（ 2層 做了） 擴展 E 后的與／或樹 希望樹 每邊代價為 1 希望樹 例子中，同時擴展了兩層節(jié)點，實際是一層層擴展的 例子 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ā)式搜索 44 雙人 完備信息博弈 ， 就是兩位選手對壘 ， 輪流走步 ， 每一方不僅知道對方已經(jīng)走過的棋步 ， 而且還能估計出對方未來的走步 。 對弈的結(jié)果是一方贏 ， 另一方輸；或者雙方和局 。 這類博弈的實例有象棋 、 圍棋等 。 所謂 機遇性博弈 ， 是指存在不可預(yù)測性的博弈 ， 例如擲幣等 。 對機遇性博弈 ，由于不具備完備信息 ， 因此我們不作討論 。 在雙人完備信息博弈過程中 ， 雙方都希望自己能夠獲勝 。 因此 ， 當任何一方走步時 ， 擇對自己最為有利 ， 而對另一方最為不利的行動方案 。 假設(shè)博弈的一方為 M， 另 m。 在博弈過程的每一步 ， 可供 M和 m選擇的行動方案都可能有多種 。 從 M觀點看 ， 可供自己選擇的那些行動方案之間是 “ 或 ” 的關(guān)系 ，原因是主動權(quán)掌握在 M選擇哪個方案完全是由自己決定的；而對那些可供 m選擇的行動方案之間則是與關(guān)系 ， 原因是主動權(quán)掌握在 m的手里 ， 任何一個方案都有可能被 m選中 ， M必須那種對自己最為不利的情況的發(fā)生 。 若把雙人完備信息博弈過程用圖表示出來 ， 就可得到一棵與／或樹 ， 這種與／或樹被稱博弈樹 。 在博弈樹中 ， 那些下一步該 M走步的節(jié)點稱為 M節(jié)點 ， 而下一步該 m走的 節(jié)點稱為 m節(jié)點 。 博弈樹的啟發(fā)式搜索 2 45 博弈樹具有如下特點： (1) 博弈的初始狀態(tài)是初始節(jié)點； (2) 博弈樹中的 “ 或 ” 節(jié)點和 “ 與 ” 節(jié)點是逐層交替出現(xiàn)的； (3) 整個博弈過程始終站在某一方的立場上，所有能使自己一方獲勝的終局都是習題，相應(yīng)的節(jié)點是可解節(jié)點；所有使對方獲勝的終局都是不可解節(jié)點。例如，站在 MAX有能使 MAX方獲勝的節(jié)點都是可解節(jié)點，所有能使 MIN方獲勝的節(jié)點都是不可解節(jié)點。 搜索效率 外顯率 (Perance)，也叫滲透率 .其定義為： P= L／ T ≤ 1 式中， L是從根節(jié)點到達目標節(jié)點的深度； T是在整個搜索過程中產(chǎn)生節(jié)點總數(shù) (不計根節(jié)點 )，因此 P反映的是朝著目標搜索時的搜索寬度。 兩種極端效率 47 (1) 兩種極端效率的搜索 ① 當 P=L／ T≈0， 沒有任何控制性知識作依據(jù) ， 搜索中的每一步都是 完全隨意而進行的 ， 稱為隨機搜索； ② P=L／ T＝ 1， 搜索以充分的控制性知識為依據(jù) ， 每一步搜索都十分嚴 密而正確 ， 即在其搜索路徑上 ， 所擴展的每一個節(jié)點都落在最佳路 徑上 ， 稱為最佳搜索 。 (2) 啟發(fā)信息 要求解的問題所聚集的有關(guān)資料 、 分析結(jié)果及與閑題求解相關(guān)等特性 信息 ， 啟發(fā)信息是控制性知識中活躍的 、 有利于提高求效率的特異性內(nèi)容； 啟發(fā)信息的作用在于綜合了人的經(jīng)驗及推理性常識等智能 ， 得出了有利 于找到問題解的較為完善的控制性信息與知識 。 把搜索中出現(xiàn)的諸如問 題的狀態(tài)條件 、 性質(zhì) 、 發(fā)展動態(tài) 、 解的過程特性 、 結(jié)構(gòu)特性等規(guī)律 ， 問 題求解的技巧性規(guī)則等 ， 統(tǒng)稱為搜索的啟發(fā)信息 。 題目 ． 5//198 有一農(nóng)夫帶一條狼 ， 一只羊和一筐菜欲從河的左岸乘船到右岸 ， 但受下列條件限制： (1)船太小 ， 農(nóng)夫每次只能帶一樣東西過河； (2)如果沒有農(nóng)夫看管 ， 則狼要吃羊 ， 羊要吃菜 。 請設(shè)計一個過河方案 ， 使得農(nóng)夫 、 狼 、 羊都能不受損失地過河 ， 畫出相應(yīng)的狀態(tài)空間圖 。 提示： (1)用四元組 (農(nóng)夫 ， 狼 ， 羊 ， 菜 )表示狀態(tài) ， 其中每個元素都為 0或 1， 用 0表示在左岸 ， 用 1表示在右岸 。 (2)把每次過河的一種安排作為一種操作，每次過河都必須有農(nóng)夫，因為只有他可以劃船。 傳教士和野人問題的搜索圖 王 191//