【正文】 為可解節(jié)點(diǎn)。此時(shí) 5號(hào)節(jié)點(diǎn)是 OPEN表中的第一個(gè)待考察的節(jié)點(diǎn)，所以下一步擴(kuò)展 5號(hào)節(jié)點(diǎn)。基本概念 狀態(tài)空間的搜索策略 與 /或圖的搜索策略 博弈樹(shù)搜索103第七章 搜索策略⑸ 擴(kuò)展 5號(hào)節(jié)點(diǎn)，得到 t3和 t4。由于 t3和 t4均為終止節(jié)點(diǎn)，所以被標(biāo)示為可解節(jié)點(diǎn)，通過(guò)應(yīng)用可解標(biāo)示過(guò)程可得到 5號(hào)、3號(hào)及 1號(hào)節(jié)點(diǎn)均為可解節(jié)點(diǎn)。⑹ 搜索成功， 得到了由 1， 2， 3， 4， 5號(hào)節(jié)點(diǎn)及 t1， t2， t3， t4節(jié)點(diǎn)構(gòu)成的解樹(shù) 。如圖 723中粗線所示。 基本概念 狀態(tài)空間的搜索策略 與 /或圖的搜索策略 博弈樹(shù)搜索104第七章 搜索策略　　與 /或圖的 寬度優(yōu)先搜索 等都是 非啟發(fā)式搜索 ， 其共同點(diǎn)是：⑴ 搜索從初始節(jié)點(diǎn)開(kāi)始 ，先 自上而下 地進(jìn)行搜索 ， 尋找終止節(jié)點(diǎn)及端節(jié)點(diǎn) ，然后再 自下而上 地進(jìn)行可解性標(biāo)示 ， 一旦初始節(jié)點(diǎn)被標(biāo)示為可解節(jié)點(diǎn)或不可解節(jié)點(diǎn)，搜索就不再繼續(xù)進(jìn)行下去 。⑵ 搜索都是 按確定路線進(jìn)行的 ，當(dāng)要選擇一個(gè)節(jié)點(diǎn)進(jìn)行擴(kuò)展時(shí)， 只是根據(jù)節(jié)點(diǎn)在與 /或圖中所處的位置，而沒(méi)有考慮要付出的代價(jià) ，因而 求得的解樹(shù)不一定是代價(jià)最小的解樹(shù) ，即 不一定是最優(yōu)解樹(shù) 。216。 啟發(fā)式與 /或圖搜索 基本概念 狀態(tài)空間的搜索策略 與 /或圖的搜索策略 博弈樹(shù)搜索105第七章 搜索策略　　 為了 求得最優(yōu)解樹(shù) ，就要在 每次確定欲擴(kuò)展的節(jié)點(diǎn)時(shí) ，先 往前多看幾步 ， 計(jì)算一下擴(kuò)展這個(gè)節(jié)點(diǎn)可能要付出的代價(jià)，并選擇代價(jià)最小的節(jié)點(diǎn)進(jìn)行擴(kuò)展 ?！　∠襁@樣 根據(jù)代價(jià)決定搜索路線的方法 稱(chēng)為 與 /或圖的有序搜索 ，它是一種重要的 啟發(fā)式搜索策略 ?！　∠旅嬗懻?與 /或圖有序搜索的有關(guān)概念及其搜索過(guò)程 。 基本概念 狀態(tài)空間的搜索策略 與 /或圖的搜索策略 博弈樹(shù)搜索216。 啟發(fā)式與 /或圖搜索 106第七章 搜索策略解樹(shù)的代價(jià)　　 解樹(shù)的代價(jià)就是樹(shù)根的代價(jià) ?！　?樹(shù)根的代價(jià) 是 從樹(shù)葉開(kāi)始自下而上逐層計(jì)算求得的 ?！　?解樹(shù)的根 對(duì)應(yīng)的就是 初始節(jié)點(diǎn) S0?！　∵@就是說(shuō)，在 與 /或圖的搜索過(guò)程中 ， 代價(jià)的計(jì)算方向與搜索樹(shù)的生長(zhǎng)方向相反 。這一點(diǎn)是與狀態(tài)圖不同的?；靖拍?狀態(tài)空間的搜索策略 與 /或圖的搜索策略 博弈樹(shù)搜索216。 啟發(fā)式與 /或圖搜索 107第七章 搜索策略具體來(lái)講，有下面的 計(jì)算方法： 　　設(shè) g（ x） 表示節(jié)點(diǎn) x的代價(jià) ， c（ x， y） 表示節(jié)點(diǎn) x到其子節(jié)點(diǎn) y的代價(jià) （即邊 x y的代價(jià)），則⑴ 若 x是 “ 終止節(jié)點(diǎn) ” ， g（ x） = 0；⑵ 若 x是 “ 或 ” 節(jié)點(diǎn) ，　　其中 y1， y2， …， yn是 x的子節(jié)點(diǎn)；基本概念 狀態(tài)空間的搜索策略 與 /或圖的搜索策略 博弈樹(shù)搜索216。 啟發(fā)式與 /或圖搜索 108第七章 搜索策略⑶ 若 x是 “ 與 ” 節(jié)點(diǎn) ，則有 兩種計(jì)算公式 ：　　 ① 　稱(chēng)為 和代價(jià)法 ；　　 ② 　稱(chēng)為 最大代價(jià)法 ；　　其中 y1， y2， …， yn是 x的子節(jié)點(diǎn)。⑷ 對(duì) “ 非終止 ” 的端節(jié)點(diǎn) x， g（ x） = ∞ ?；靖拍?狀態(tài)空間的搜索策略 與 /或圖的搜索策略 博弈樹(shù)搜索216。 啟發(fā)式與 /或圖搜索 109第七章 搜索策略例 7． 11 如圖 724所示的與 /或圖，其中 包括兩棵解樹(shù) ， 一棵解樹(shù)由 S0， A， t1和 t2組成 ； 另一棵解樹(shù)由 S0， B， D， G， t4和 t5組成 。在此與 /或圖中， t1， t2， t3， t4， t5為終止節(jié)點(diǎn) ； E， F是端節(jié)點(diǎn) ，其代價(jià)均為 ∞ ；邊上的數(shù)字是該邊的代價(jià) 。 圖 724 含代價(jià)的與 /或圖 基本概念 狀態(tài)空間的搜索策略 與 /或圖的搜索策略 博弈樹(shù)搜索216。 啟發(fā)式與 /或圖搜索 110第七章 搜索策略由 右邊的解樹(shù) 可得：按 和代價(jià) ： g（ A） = 11 ， g（ S0） = 13 。按 最大代價(jià) ： g（ A） = 6 ， g（ S0 ） = 8 。由 左邊的解樹(shù) 可得：按 和代價(jià) ： g（ G） = 3 ， g（ D） = 4 ， g（ B） = 6 ， g（ S0 ） = 8 。按 最大代價(jià) ： g（ G） = 2 ， g（ D） = 3 ， g（ B） = 5 ， g（ S0 ） = 7 ?；靖拍?狀態(tài)空間的搜索策略 與 /或圖的搜索策略 博弈樹(shù)搜索216。 啟發(fā)式與 /或圖搜索 111第七章 搜索策略　　顯然，若 按和代價(jià) 計(jì)算， 左邊的解樹(shù)是最優(yōu)解樹(shù) ，其代價(jià)是 8；若 按最大代價(jià) 計(jì)算， 左邊的解樹(shù)仍然是最優(yōu)解 樹(shù)，其代價(jià)是 7?！　〉袝r(shí) 用不同的計(jì)算代價(jià)方法得到的最優(yōu)解樹(shù)不相同 。 基本概念 狀態(tài)空間的搜索策略 與 /或圖的搜索策略 博弈樹(shù)搜索216。 啟發(fā)式與 /或圖搜索 112第七章 搜索策略希望樹(shù)1）節(jié)點(diǎn) x的代價(jià) g（ x）　　　無(wú)論是用 和代價(jià)法 還是 最大代價(jià)法 ，當(dāng)要 計(jì)算任意節(jié)點(diǎn) x的代價(jià) g（ x） 時(shí)，都要求已知其子節(jié)點(diǎn) yi的代價(jià) g（ yi） 。但是， 搜索是自上而下 進(jìn)行的，即先有父節(jié)點(diǎn)，后有子節(jié)點(diǎn)，除非節(jié)點(diǎn) x的全部子節(jié)點(diǎn)都是不可擴(kuò)展節(jié)點(diǎn)，否則子節(jié)點(diǎn)的代價(jià)是不知道的。 基本概念 狀態(tài)空間的搜索策略 與 /或圖的搜索策略 博弈樹(shù)搜索216。 啟發(fā)式與 /或圖搜索 113第七章 搜索策略 節(jié)點(diǎn) x的代價(jià) g（ x） 的計(jì)算① 根據(jù)問(wèn)題本身 提供的啟發(fā)性信息定義一個(gè)啟發(fā)函數(shù) ，由啟發(fā)函數(shù) 估算出子節(jié)點(diǎn) yi的代價(jià) g（ yi ）。② 再 按和代價(jià) 或 最大代價(jià) 計(jì)算出節(jié)點(diǎn) x的代價(jià)值 g（ x） 。③ 節(jié)點(diǎn) x的父節(jié)點(diǎn)、祖父節(jié)點(diǎn)以及直到初始節(jié)點(diǎn) S0的各先輩節(jié)點(diǎn)的 代價(jià) g都可自下而上地逐層推算出來(lái) ?；靖拍?狀態(tài)空間的搜索策略 與 /或圖的搜索策略 博弈樹(shù)搜索216。 啟發(fā)式與 /或圖搜索 114第七章 搜索策略　　 當(dāng) 節(jié)點(diǎn) yi被擴(kuò)展 后，也是 先用啟發(fā)函數(shù)估算出其子節(jié)點(diǎn)的代價(jià) ，然后 再算出 g(yi)。 此時(shí)算出的 g(yi)可能與原先估算出的 g(yi)不相同 ，這時(shí)應(yīng)該 用后算出的g( yi)取代原先估算出的 g(yi)，并且 按 此 g(yi)自下而上地重新計(jì)算各先輩節(jié)點(diǎn)的 g值 。 當(dāng)節(jié)點(diǎn) yi的子節(jié)點(diǎn)又被擴(kuò)展時(shí)，上述過(guò)程又要重復(fù)進(jìn)行一遍?；靖拍?狀態(tài)空間的搜索策略 與 /或圖的搜索策略 博弈樹(shù)搜索216。 啟發(fā)式與 /或圖搜索 115第七章 搜索策略　　 總之， 每當(dāng)有新的一代節(jié)點(diǎn)生成時(shí) ，都要 自下而上地重新計(jì)算其先輩節(jié)點(diǎn)的代價(jià) g，這是一個(gè) 自上而下地生成新節(jié)點(diǎn) ，又 自下而上 地計(jì)算代價(jià) g的 反復(fù)進(jìn)行的過(guò)程 ?；靖拍?狀態(tài)空間的搜索策略 與 /或圖的搜索策略 博弈樹(shù)搜索216。 啟發(fā)式與 /或圖搜索 116第七章 搜索策略2）希望樹(shù)的定義　　有序搜索的目的是求出最優(yōu)解樹(shù)，即要求 搜索過(guò)程中任意時(shí)刻求出的部分解樹(shù)其代價(jià)都應(yīng)是最小的 。為此，每次選擇 欲擴(kuò)展的節(jié)點(diǎn)時(shí) 都應(yīng)挑選 有希望成為最優(yōu)解樹(shù)一部分的節(jié)點(diǎn) 進(jìn)行擴(kuò)展?！　∮捎谶@些 節(jié)點(diǎn)及其先輩節(jié)點(diǎn)（包括初始節(jié)點(diǎn) S0）所構(gòu)成的與 /或圖有可能 成為最優(yōu)解樹(shù)的一部分，因此稱(chēng)它為 “ 希望樹(shù) ” ?；靖拍?狀態(tài)空間的搜索策略 與 /或圖的搜索策略 博弈樹(shù)搜索216。 啟發(fā)式與 /或圖搜索 117第七章 搜索策略　　在搜索過(guò)程中， 隨著新節(jié)點(diǎn)的不斷生成 ，節(jié)點(diǎn)的代價(jià)值是在不斷變化的，因此 希望樹(shù)也在不斷變化 。在某一時(shí)刻，這一部分節(jié)點(diǎn)構(gòu)成希望樹(shù)，但到另一時(shí)刻，可能是另一些節(jié)點(diǎn)構(gòu)成希望樹(shù)?！　〉还苋绾巫兓?任一時(shí)刻的希望樹(shù)都必須包含初始節(jié)點(diǎn) S0，而且希望樹(shù)總是對(duì)最優(yōu)解樹(shù)近根部分的某種估計(jì) 。 基本概念 狀態(tài)空間的搜索策略 與 /或圖的搜索策略 博弈樹(shù)搜索216。 啟發(fā)式與 /或圖搜索 118第七章 搜索策略希望樹(shù)的定義：⑴ 初始節(jié)點(diǎn) S0在希望樹(shù) T中。⑵ 如果 節(jié)點(diǎn) x在希望樹(shù) T中，則一定有：　 ① 如果 x是具有子節(jié)點(diǎn) y1， y2， …， yn的 “ 或 ” 節(jié)點(diǎn) ，則具有 值的那個(gè)子節(jié)點(diǎn) yi也應(yīng)在 T中?！?② 如果 x是 “ 與 ” 節(jié)點(diǎn) ，則它的全部子節(jié)點(diǎn)都應(yīng)在 T中。基本概念 狀態(tài)空間的搜索策略 與 /或圖的搜索策略 博弈樹(shù)搜索216。 啟發(fā)式與 /或圖搜索 119第七章 搜索策略與 /或圖的有序搜索過(guò)程　 　 與 /或圖的 有序搜索過(guò)程 是一個(gè) 不斷選擇、修正希望樹(shù)的過(guò)程 。如果問(wèn)題有解，則經(jīng)有序搜索 將找到最優(yōu)解樹(shù) ?！　∑渌阉鬟^(guò)程如下：　 ⑴ 把 初始節(jié)點(diǎn) S0放入 OPEN表 中；　 ⑵ 求出希望樹(shù) T，即根據(jù)當(dāng)前搜索樹(shù)中節(jié)點(diǎn)的代價(jià) g求出以S0為根的希望樹(shù) T；　 ⑶ 依次 把 OPEN表中 T的端節(jié)點(diǎn) N選出放入 CLOSED表 中；基本概念 狀態(tài)空間的搜索策略 與 /或圖的搜索策略 博弈樹(shù)搜索216。 啟發(fā)式與 /或圖搜索 120第七章 搜索策略⑷ 如果 節(jié)點(diǎn) N是終止節(jié)點(diǎn) ，則做下列工作：　 ① 標(biāo)示 N為可解節(jié)點(diǎn) ；　 ② 對(duì) T應(yīng)用可解標(biāo)示過(guò)程 ，把 N的先輩節(jié)點(diǎn)中的可解節(jié)點(diǎn) 都標(biāo)示為可解節(jié)點(diǎn) ；　 ③ 若 初始節(jié)點(diǎn) S0能被標(biāo)示為可解節(jié)點(diǎn) ，則 T就是最優(yōu)解樹(shù)， 成功并退出 ?！?④ 否則， 從 OPEN表中刪去具有可解先輩的所有節(jié)點(diǎn) ；基本概念 狀態(tài)空間的搜索策略 與 /或圖的搜索策略 博弈樹(shù)搜索216。 啟發(fā)式與 /或圖搜索 121第七章 搜索策略⑸ 如果 節(jié)點(diǎn) N不是終止節(jié)點(diǎn) ，且 它不可擴(kuò)展 ，則做下列工作：　 ① 標(biāo)示 N為不可解節(jié)點(diǎn) ；　 ② 對(duì) T應(yīng)用不可解節(jié)點(diǎn)標(biāo)示過(guò)程 ，把 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) ；基本概念 狀態(tài)空間的搜索策略 與 /或圖的搜索策略 博弈樹(shù)搜索216。 啟發(fā)式與 /或圖搜索 122第七章 搜索策略⑹ 如果 節(jié)點(diǎn) N不是終止節(jié)點(diǎn) ，但 它可擴(kuò)展 ，則可做下列工作：　 ① 擴(kuò)展節(jié)點(diǎn) N，產(chǎn)生 N的所有子節(jié)點(diǎn) ；　 ② 把這些 子節(jié)點(diǎn)都放入 OPEN表 中，并為每一個(gè)子節(jié)點(diǎn)配置指向父節(jié)點(diǎn)（節(jié)點(diǎn) N）的指針；　 ③ 計(jì)算這些子節(jié)點(diǎn)的 g值及其先輩節(jié)點(diǎn)的 g值 ；⑺ 轉(zhuǎn)第 ⑵ 步。基本概念 狀態(tài)空間的搜索策略 與 /或圖的搜索策略 博弈樹(shù)搜索216。 啟發(fā)式與 /或圖搜索 123第七章 搜索策略例 設(shè)初始節(jié)點(diǎn)為 S0，每次擴(kuò)展兩層，并設(shè) S0經(jīng)擴(kuò)展后得到如圖 725（ a）（下頁(yè)）所示的與 /或圖，其中子節(jié)點(diǎn) B， C， E，F(xiàn)用啟發(fā)函數(shù)估算出的 g值分別是 g（ B） = 3 ， g（ C） = 3 ， g（ E） = 3 ， g（ F）= 2 。若按和代價(jià)計(jì)算，則得到 g（ A） = 8 ， g（ D） = 7 ， g（ S0） = 8 。（注：這里把邊代價(jià)一律按 1計(jì)算，下同） 此時(shí)， S0的右子樹(shù)是希望樹(shù) ?；靖拍?狀態(tài)空間的搜索策略 與 /或圖的搜索策略 博弈樹(shù)搜索216。 啟發(fā)式與 /或圖搜索 124第七章 搜索策略　基本概念 狀態(tài)空間的搜索策略 與 /或圖的搜索策略 博弈樹(shù)搜索216。 啟發(fā)式與 /或圖搜索 圖 725 與 /或圖有序搜索 125第七章 搜索策略　　下面將 對(duì)此希望樹(shù)的節(jié)點(diǎn)進(jìn)行擴(kuò)展 ?！　≡O(shè) 對(duì)節(jié)點(diǎn) E擴(kuò)展兩層 后得到如圖 725（ b）所示的與 /或圖， 節(jié)點(diǎn)旁的數(shù)字為用啟發(fā)函數(shù)估算出的 g值 。則 按和代價(jià)法 計(jì)算得到 g（ G） = 7 ， g（ H） = 6 ， g（ E） = 7 ， g（ D） = 11 ?！　〈藭r(shí)，由 S0的右子樹(shù)算出的 g（ S0 ） = 12 。但是，由 左子樹(shù)算出的 g（ S0 ） = 9 ?！　★@然， 左子樹(shù)的代價(jià)小 ，所以現(xiàn)在改取 左子樹(shù)作為當(dāng)前的希望樹(shù) 。基本概念 狀態(tài)空間的搜索策略 與 /或圖的搜索策略 博弈樹(shù)搜索216。 啟發(fā)式與 /或圖搜索 126第七章 搜索策略　　 假設(shè)對(duì)節(jié)點(diǎn) B擴(kuò)展兩層后得到如圖 725（ c）所示的與 /或圖，節(jié)點(diǎn)旁的數(shù)字是對(duì)相應(yīng)節(jié)點(diǎn)的估算值，節(jié)點(diǎn) L的兩個(gè)子節(jié)點(diǎn)是終止節(jié)點(diǎn)，則 按和代價(jià)法 計(jì)算得到 g（ L） = 2 ， g（ M） = 6 ， g（ B） = 3 ， g（ A） = 8 ?！　∮纱丝赏茢喑?g（ S0） = 9 。這時(shí)， 左子樹(shù)仍然是希望樹(shù) ，繼續(xù)對(duì)其擴(kuò)展。該擴(kuò)展節(jié)點(diǎn) C?！　〖僭O(shè)對(duì)節(jié)點(diǎn) C擴(kuò)展兩層后得到如圖 725（ d）所示的與 /或圖，節(jié)點(diǎn)旁的數(shù)字是相應(yīng)節(jié)點(diǎn)的估算值，節(jié)點(diǎn) N的兩個(gè)子節(jié)點(diǎn)是終止節(jié)點(diǎn)