與或圖搜索問題ppt課件-在線瀏覽
2025-06-22 18:36本頁面
【正文】 可解節(jié)點(diǎn)，并應(yīng)用可解標(biāo)識(shí)過程對(duì)其父節(jié)點(diǎn)、祖父節(jié)點(diǎn)等先輩節(jié)點(diǎn)中的可解節(jié)點(diǎn)進(jìn)行標(biāo)識(shí)。 ? 轉(zhuǎn)第 2步。 ? . 標(biāo)識(shí)節(jié)點(diǎn) n為不可解節(jié)點(diǎn)。 ? 轉(zhuǎn)第 2步。像這樣根據(jù)代價(jià)決定搜索路線的方法稱為與或樹的有序搜索，它是一種啟發(fā)式搜索策略。 2. 如果 x是“或”節(jié)點(diǎn)， y1, y2, …, yn是它的子節(jié)點(diǎn)，則節(jié)點(diǎn) x的代價(jià)由下式計(jì)算得到 h(x)=min{c(x, yi) + h(yi)} 3. 如果 x是“與”節(jié)點(diǎn)， 則節(jié)點(diǎn) x的代價(jià)有兩種計(jì)算方法：和代價(jià)法與最大代價(jià)法。 ?? ?? n 1i ii ))y(h)y,x(c()x(h)}y(h)y,x(c{)x(h iini1m ax????17 耗散值（代價(jià)值）的計(jì)算：示例 ? 解樹： S0, A, t1和 t2。 ? 由左邊的解樹可得： ? 和代價(jià)： h(A)=11,h(S0)=13 ? 最大代價(jià)： h(A)=6,h(S0)=8 ? 由右邊的解樹可得： ? 和代價(jià)： h(G)=3,h(D)=4,h(B)=6,h(S0)=8 ? 最大代價(jià)： h(G)=2,h(D)=3,h(B)=5,h(S0)=7 ? 顯然，若按和代價(jià)計(jì)算，右邊的解樹是最優(yōu)解樹，其代價(jià)為 8；若按最大代價(jià)計(jì)算，右邊解樹解樹仍然是最優(yōu)解樹，其代價(jià)為 7。但搜索是自上而下進(jìn)行的，即先有父節(jié)點(diǎn)，后有子節(jié)點(diǎn)，除非節(jié)點(diǎn) x的全部子節(jié)點(diǎn)都是不可擴(kuò)展節(jié)點(diǎn)，否則子節(jié)點(diǎn)的代價(jià)是不知道的。有了 h(x)，節(jié)點(diǎn) x的父節(jié)點(diǎn)、祖父節(jié)點(diǎn)以及直到初始節(jié)點(diǎn) S0的各先輩節(jié)點(diǎn)的代價(jià) h都可自下而上的逐層推算出來。此時(shí)算出的 h(yi)可能與原先估算出的 h(yi)不相同，這時(shí)應(yīng)該用后算出的 h(yi)取代原先估算出的 h(yi)，并且按此 h(yi)自下而上地重新計(jì)算各先輩節(jié)點(diǎn)的 h值?？傊慨?dāng)有一代新的節(jié)點(diǎn)生成時(shí)，都要自下而上地重新計(jì)算其先輩節(jié)點(diǎn)的代價(jià)，這是一個(gè) 自上而下 地生成節(jié)點(diǎn)，又 自下而上 地計(jì)算代價(jià) h的反復(fù)進(jìn)行的過程。這就是要求搜索過程中任一時(shí)刻求出的部分解樹其代價(jià)是最小的。由于這些節(jié)點(diǎn)及其先輩節(jié)點(diǎn)（包括初始節(jié)點(diǎn) S0）所構(gòu)成的與 /或樹有可能成為最優(yōu)解樹的一部分，因此稱它為希望樹。 ? 2. 如果節(jié)點(diǎn) x在希望樹中，則一定有： ? 如果 x是具有節(jié)點(diǎn) y1， y2， … ， yn的“或” 節(jié)點(diǎn)，則具有 h(x) = min{c(x, yi) + h(yi)}值 的那個(gè)子節(jié)點(diǎn)也應(yīng)在 T中。 21 與或樹的有序搜索：算法 ? 1. 把初始節(jié)點(diǎn) S0放入 OPEN表中。 ? 3. 依次把 OPEN表中 T的端節(jié)點(diǎn) N選出放入 CLOSED表中。 ? 對(duì) T應(yīng)用可解標(biāo)識(shí)過程，把 N的先輩節(jié)點(diǎn)中的可解節(jié)點(diǎn)都標(biāo) 識(shí)為可解節(jié)點(diǎn)。 ? 否則，從 OPEN表中刪去具有可解先輩的所有節(jié)點(diǎn)。 ? 對(duì) T應(yīng)用不可解 標(biāo)識(shí)過程，把 N的先輩節(jié)點(diǎn)中的不可解節(jié)點(diǎn) 都標(biāo)識(shí)為不可解節(jié)點(diǎn)。 ? 否則，從 OPEN表中刪去具有不可解先輩的所有節(jié)點(diǎn)。 ? 把這些子節(jié)點(diǎn)都放入 OPEN表中，并為每個(gè)子節(jié)點(diǎn)配置指向 父節(jié)點(diǎn)（節(jié)點(diǎn) N）的指針。 ? 7. 轉(zhuǎn)第 2步。但節(jié)點(diǎn) C目前不能肯定是可解節(jié)點(diǎn)，故 A和 S0也還不能確定為可解節(jié)點(diǎn)。 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。博弈有很多種，我們討論最簡單的 二人零和、全信息、非偶然 博弈，其特征如下： (1) 對(duì)壘的 MAX、 MIN雙方輪流采取行動(dòng)，博弈的結(jié)果只有三種情況： MAX方勝， MIN方??； MIN方勝， MAX方?。缓途?。 (3) 任何一方在采取行動(dòng)前都要根據(jù)當(dāng)前的實(shí)際情況，進(jìn)行得失分析，選取對(duì)自已為最有利而對(duì)對(duì)方最為不利的對(duì)策，不存在擲骰子之類的 碰運(yùn)氣 因素。 博弈概述 ? 在博弈過程中，任何一方都希望自己取得勝利。此時(shí)，如果我們站在 MAX方的立場上，則可供 MAX方選擇的若干行動(dòng)方案之間是 或 關(guān)系，因?yàn)橹鲃?dòng)權(quán)操在 MAX方手里，他或者選擇這個(gè)行動(dòng)方案，或者選擇另一個(gè)行動(dòng)方案，完全由 MAX方自已決定。 博弈概述 ? 這樣，如果站在某一方 (如 MAX方，即 MAX要取勝 )，把上述博弈過程用圖表示出來，則得到的是一棵 與或樹 。 (2) 在博弈樹中， 或 節(jié)點(diǎn)和 與 節(jié)點(diǎn)是逐層交替出現(xiàn)的。雙方輪流地?cái)U(kuò)展節(jié)點(diǎn)。 我們假定 MAX先走，處于奇數(shù)深度級(jí)的節(jié)點(diǎn)都對(duì)應(yīng)下一步由MAX走，這些節(jié)點(diǎn)稱為 MAX節(jié)點(diǎn)，相應(yīng)地偶數(shù)級(jí)為 MIN節(jié)點(diǎn)。 ?1980年他獲得世界少年組冠軍 ?1982年他并列奪得蘇聯(lián)冠軍 ?1985年 22歲的卡斯帕羅夫成為 歷史上最年輕 的國 際象棋冠軍 ?積分是 2849，這一分?jǐn)?shù)是有史以來最高分。 ? 1993年 “ 深思 ” 第二代擊敗了丹麥?zhǔn)澜鐑?yōu)秀女棋手小波爾加。 ? 2022年 10月 “ 更弗里茨 ” 與世界棋王克拉姆尼克在巴林交手，雙方以4比 4戰(zhàn)平。 許多人在努力 機(jī)器博弈 ? 20世紀(jì) 50年代，有人設(shè)想利用機(jī)器智能來實(shí)現(xiàn)機(jī)器
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1