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