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