與或圖搜索問題ppt課件(編輯修改稿)
2025-06-01 18:36 本頁面
【文章內(nèi)容簡介】 可解節(jié)點(diǎn)都標(biāo) 識為可解節(jié)點(diǎn)。 ? 若初始節(jié)點(diǎn) S0能被標(biāo)識為可解節(jié)點(diǎn)，則 T就是最優(yōu)解樹，成 功退出。 ? 否則，從 OPEN表中刪去具有可解先輩的所有節(jié)點(diǎn)。 22 與或樹的有序搜索：算法（續(xù)） ? 5. 如果節(jié)點(diǎn) N不是終止節(jié)點(diǎn)，且它不可擴(kuò)展，則作下列工作： ? 標(biāo)識 N為不可解節(jié)點(diǎn)。 ? 對 T應(yīng)用不可解 標(biāo)識過程，把 N的先輩節(jié)點(diǎn)中的不可解節(jié)點(diǎn) 都標(biāo)識為不可解節(jié)點(diǎn)。 ? 若初始節(jié)點(diǎn) S0也被標(biāo)識為不可解節(jié)點(diǎn)，則失敗退出。 ? 否則，從 OPEN表中刪去具有不可解先輩的所有節(jié)點(diǎn)。 ? N不是終止節(jié)點(diǎn)，但它可擴(kuò)展，則作下列工作： ? 擴(kuò)展節(jié)點(diǎn) N，產(chǎn)生 N的所有子節(jié)點(diǎn)。 ? 把這些子節(jié)點(diǎn)都放入 OPEN表中，并為每個子節(jié)點(diǎn)配置指向 父節(jié)點(diǎn)（節(jié)點(diǎn) N）的指針。 ? 計算這些子節(jié)點(diǎn)的 h值及其先輩節(jié)點(diǎn)的 h值。 ? 7. 轉(zhuǎn)第 2步。 23 與或樹的有序搜索：示例 S0 A B C D E F 3 3 3 2 h(A)=8, h(D)=7, h(S0)=8, 右子樹為希望樹 S0 A B C G D E H 2 2 2 3 2 F H(G)=7, h(H)=6, h(E)=7, h(D)=11, S0的右子樹算出的 h(S0)＝ 12，而左子樹的 h(S0)＝ 9，因此左子樹為希望樹 一次擴(kuò)展兩層， B C E F下面的值均為按某種啟發(fā)式方法估算出來的 24 與或樹的有序搜索：示例 S0 A C G D E H 2 2 2 3 2 F h(L)=2, h(M)=6, h(B)=3, h(A)=8, L、 B均為可解節(jié)點(diǎn)。但節(jié)點(diǎn) C目前不能肯定是可解節(jié)點(diǎn)，故 A和 S0也還不能確定為可解節(jié)點(diǎn)。左子樹仍然是希望樹，下面對節(jié)點(diǎn) C進(jìn)行擴(kuò)展。 M L B 0 0 2 2 3 25 與或樹的有序搜索：示例 S0 A C G D E H 2 2 2 3 2 F h(N)=2, h(P)=7, h(C)=3, h(A)=8, 由此可推算出 h(S0)＝ 9。 B P N 0 0 3 2 M L 0 0 2 2 博弈概述 ? 諸如下棋、打牌、競技、戰(zhàn)爭等一類競爭性智能活動稱為博弈。博弈有很多種，我們討論最簡單的 二人零和、全信息、非偶然 博弈，其特征如下： (1) 對壘的 MAX、 MIN雙方輪流采取行動，博弈的結(jié)果只有三種情況： MAX方勝， MIN方?。?MIN方勝， MAX方敗；和局。 (2) 在對壘過程中，任何一方都了解當(dāng)前的格局及過去的歷史。 (3) 任何一方在采取行動前都要根據(jù)當(dāng)前的實際情況，進(jìn)行得失分析，選取對自已為最有利而對對方最為不利的對策，不存在擲骰子之類的 碰運(yùn)氣 因素。即雙方都是很理智地決定自己的行動。 博弈概述 ? 在博弈過程中，任何一方都希望自己取得勝利。因此，當(dāng)某一方當(dāng)前有多個行動方案可供選擇時，他總是挑選對自己最為有利而對對方最為不利的那個行動方案。此時，如果我們站在 MAX方的立場上，則可供 MAX方選擇的若干行動方案之間是 或 關(guān)系，因為主動權(quán)操在 MAX方手里，他或者選擇這個行動方案，或者選擇另一個行動方案，完全由 MAX方自已決定。當(dāng) MAX方選取任一方案走了一步后， MIN方也有若干個可供選擇的行動方案，此時這些行動方案對 MAX方來說它們之間則是 與 關(guān)系，因為這時主動權(quán)操在 MIN方手里，這些可供選擇的行動方案中的任何一個都可能被 MIN方選中， MAX方必須應(yīng)付每一種情況的發(fā)生。 博弈概述 ? 這樣，如果站在某一方 (如 MAX方，即 MAX要取勝 )，把上述博弈過程用圖表示出來，則得到的是一棵 與或樹 。描述博弈過程的與或樹稱為博弈樹，它有如下特點(diǎn)： (1) 博弈的初始格局是初始節(jié)點(diǎn)。 (2) 在博弈樹中， 或 節(jié)點(diǎn)和 與 節(jié)點(diǎn)是逐層交替出現(xiàn)的。自己一方擴(kuò)展的節(jié)點(diǎn)之間是 或 關(guān)系，對方擴(kuò)展的節(jié)點(diǎn)之間是 與 關(guān)系。雙方輪流地擴(kuò)展節(jié)點(diǎn)。 (3) 所有自己一方獲勝的終局都是本原問題，相應(yīng)的節(jié)點(diǎn)是可解節(jié)點(diǎn)；所有使對方獲勝的終局都認(rèn)為是不可解節(jié)點(diǎn)。 我們假定 MAX先走，處于奇數(shù)深度級的節(jié)點(diǎn)都對應(yīng)下一步由MAX走，這些節(jié)點(diǎn)稱為 MAX節(jié)點(diǎn)，相應(yīng)地偶數(shù)級為 MIN節(jié)點(diǎn)。 1997年 5月 11日， IBM開發(fā)的 “ 深藍(lán) ”擊敗了國際象棋冠軍卡斯帕羅夫。 ?1980年他獲得世界少年組冠軍 ?1982年他并列奪得蘇聯(lián)冠軍 ?1985年 22歲的卡斯帕羅夫成為 歷史上最年輕 的國 際象棋冠軍 ?積分是 2849，這一分?jǐn)?shù)是有史以來最高分。 遠(yuǎn)遠(yuǎn)領(lǐng)先于第二位的克拉姆尼克的 2770 卡氏何許人也？ 電腦棋手：永不停歇的挑戰(zhàn)！ ? 1988年 “ 深思 ” 擊敗了丹麥特級大師拉森。 ? 1993年 “ 深思 ” 第二代擊敗了丹麥?zhǔn)澜鐑?yōu)秀女棋手小波爾加。 電腦棋手：永不停歇的挑戰(zhàn)！ ? 2022年 “ 更弗里茨 ” 擊敗了除了克拉姆尼克之外的所有排名世界前十位的棋手。 ? 2022年 10月 “ 更弗里茨 ” 與世界棋王克拉姆尼克在巴林交手，雙方以4比 4戰(zhàn)平
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1