




版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
一個智能系統搜索策略的優劣直接影響到系統的性能語推理效率。
本章主要內容:搜索的基本概念;狀態空間的盲目搜索;狀態空間的啟發式搜索;與或樹的盲目搜索;與或樹的啟發式搜索;博奕樹的啟發式搜索;第5章搜索測略1一個智能系統搜索策略的優劣直接影響到系5.1搜索策略的基本概念
5.1.1搜索的含義1.搜索定義:根據問題的實際情況,不斷尋找可利用的知識,從而構造一條代價最小的推理路線,使問題得以解決的過程稱為搜索。2.組合爆炸問題:結構良好,理論上有算法可依的問題,如果問題或算法的復雜性較高(按指數形式增長),由于受計算機在時間和空間上的限制,無法付諸實用。25.1搜索策略的基本概念5.1.1搜索的含義25.1搜索策略的基本概念3.搜索類型:(1)根據是否使用啟發信息分類:盲目搜索:按預定的控制策略進行,在搜索過程中獲得的中間信息不改變控制策略。啟發式搜索:在搜索過程中加入了與問題有關的啟發性信息,用于指導搜索朝著最有希望的方向前進,加速問題的求解過程并找到最優解。35.1搜索策略的基本概念3.搜索類型:35.1搜索策略的基本概念(2)根據問題的表示方式分類:狀態空間搜索:用狀態空間法來求解問題所進行的搜索。與/或樹搜索:用問題歸約法來求解問題時所進行的搜索。45.1搜索策略的基本概念(2)根據問題的表示方式分類:45.1搜索策略的基本概念5.1.2狀態空間法1.狀態空間表示法(1)狀態(state):表示問題求解過程中每一步問題狀況的數據結構,形式的表示為:
Sk={Sk0,Sk1,…)當對每一個分量都予以確定的值時,就得到了一個具體的狀態。55.1搜索策略的基本概念5.1.2狀態空間法55.1搜索策略的基本概念(2)操作(operator)(算符)把問題從一種狀態轉換為另一種狀態的手段。可以是一個機械步驟、一個運算、一條規則或一個過程。可理解為狀態集合上的一個函數,描述了狀態之間的關系。65.1搜索策略的基本概念(2)操作(operator)(算符5.1搜索策略的基本概念(3)狀態空間(statespace)描述一個問題的全部狀態以及這些狀態之間的相互關系。常用三元組表示:(S,F,G)S:為問題所有初始狀態的集合。
F:為操作的集合。
G:為目標狀態的集合。75.1搜索策略的基本概念(3)狀態空間(statespac5.1搜索策略的基本概念狀態空間圖:賦值的有向圖。節點表示問題的狀態,有向邊表示操作.2.狀態空間問題求解任何以狀態和操作為基礎的問題求解方法都稱為狀態空間問題求解。簡稱為狀態空間法。狀態空間法的基本過程為:(1)為問題選擇適當的“狀態”及“操作”的形式化描述方法。85.1搜索策略的基本概念狀態空間圖:賦值的有向圖。節點表示5.1搜索策略的基本概念(2)從某個初始狀態出發,每次使用一個“操作”,遞增地建立起操作序列,直到達到目標狀態為止。(3)從初始狀態到目標狀態所使用的算符序列就是問題的一個解。95.1搜索策略的基本概念(2)從某個初始狀態出發,每次使用一5.1搜索策略的基本概念3.狀態空間的例子例5.1:二階梵塔問題:設有三根鋼針,它們的編號分別是1,2,3。在初始情況下,1號鋼針上穿有A、B兩個金片,A比B小,A位于B的上面。要求把這兩個金片全部移到另一根鋼針上,而且規定每次只能移動一個金片,任何時刻都不能使大片位于小片的上面。105.1搜索策略的基本概念3.狀態空間的例子105.1搜索策略的基本概念解:設用Sk={Sk0,Sk1}表示問題的狀態,其中,Sk0表示金片A所在的鋼針號,Sk1表示金片B所在的鋼針號。全部可能的問題狀態共有以下9種:S0=(1,1)S1=(1,2)S2=(1,3)S3=(2,1)S4=(2,2)S5=(2,3)S6=(3,1)S7=(3,2)S8=(3,3)其中S0為初始狀態,S4和S8為目標狀態。115.1搜索策略的基本概念解:設用Sk={Sk0,Sk1}表5.1搜索策略的基本概念任何以狀態和操作為基礎的問題求解方法都稱為狀態空間問題求解。簡稱為狀態空間法。狀態空間法的基本過程為:(1)為問題選擇適當的“狀態”及“操作”的形式化描述方法。(2)從某個初始狀態出發,每次使用一個“操作”,遞增地建立起操作序列,直到達到目標狀態為止。(3)從初始狀態到目標狀態所使用的算符序列就是問題的一個解。125.1搜索策略的基本概念任何以狀態和操5.1搜索策略的基本概念例5.2修道士和野人問題.首先選取描述問題狀態的方法。用一個三元組表示狀態:S=(m,c,b)其中:m表示左岸的修道士數;c表示左岸的野人數;b表示左岸的船數;135.1搜索策略的基本概念例5.2修道士和野人問題.135.1搜索策略的基本概念右岸的狀態由下式確定:右岸的修道士數m’=3-m;右岸的野人數c’=3-c;
右岸的船數b’=1-b;
m和c的取值分別為0,1,2,3之一;b的取值分別為0,1;
共有4x4x2=32種狀態。145.1搜索策略的基本概念右岸的狀態由下式確定:145.1搜索策略的基本概念3,32,12,31,21,3A(3,2)2,23,23,11,1B(1,2)A(1,3)二階樊塔狀態空間圖155.1搜索策略的基本概念3,32,12,31,21,3A(35.1搜索策略的基本概念除去不合法的狀態和修道士被野人吃掉的狀態,余下的狀態由16種:S0=(3,3,1),S1=(3,2,1),S2=(3,1,1),S3=(2,2,1),S4=(1,1,1),S5=(0,3,1),S6=(0,2,1),S7=(0,1,1),S8=(3,2,0),S9=(3,1,0),S10=(3,0,0),S11=(2,2,0),S12=(1,1,0),S13=(0,2,0),S14=(0,1,0),S15=(0,0,0),165.1搜索策略的基本概念除去不合法的狀態和修道士被野人吃掉的5.1搜索策略的基本概念需要考慮的操作有:(1)船至少有一個人(m或c)操作,離開岸邊的m和c的減少數目應該等于到達岸邊的m和c的增加數目;(2)每次操作船上的人數不得超過2個;(3)操作應保證不產生非法狀態。操作由兩部分組成:條件部分和動作部分。175.1搜索策略的基本概念需要考慮的操作有:175.1搜索策略的基本概念用Qij表示從右岸到左岸的運人操作,可供選擇的操作由10種,操作集為:F={P01,P10,P11,P02,P20,Q01,Q10,Q11,Q02,Q20,}以P01和Q01為例說明操作的條件和動作:操作符號條件動作P01b=1,m=0或3,c≥1b=0,c=c-1Q01b=1,m=0或3,c≤2b=1,c=c+1185.1搜索策略的基本概念用Qij表示從5.1搜索策略的基本概念例5.3猴子摘香蕉問題.
首先選取描述問題狀態的方法。用一個四元組表示狀態:S=(w,x,y,z)
其中:w表示猴子的水平位置;x表示箱子的水平位置;
y表示猴子是否在箱子上,當猴子在箱子上時y=1否則y=0;
z表示猴子是否拿到香蕉,當拿到香蕉時z=1否則z=0;195.1搜索策略的基本概念例5.3猴子摘香蕉問題.195.1搜索策略的基本概念所有可能的狀態有:S0=(a,b,0,0),初始狀態S1=(b,b,0,0),S2=(c,c,1,0),S3=(c,c,1,1),目標狀態205.1搜索策略的基本概念所有可能的狀態有:205.1搜索策略的基本概念允許的操作為:Goto(u):猴子走到位置u,即:(w,x,0,0)→(u,x,0,0)Pushbox(v):猴子推著箱子到水平位置v,即:(x,x,0,0)→(v,v,0,0)Climbbox:猴子爬上箱子,即:(x,x,0,0)→(x,x,1,0)Grasp:猴子拿到香蕉,即:(c,c,1,0)→(c,c,1,1)215.1搜索策略的基本概念允許的操作為:215.1搜索策略的基本概念問題的狀態空間圖見書P172,圖5-3.由初始狀態變為目標狀態的操作序列為:{Goto(b),Pushbox?,Climbbox,Grasp}225.1搜索策略的基本概念問題的狀態空間圖見書P172,圖5-5.1搜索策略的基本概念5.1.3問題歸約
問題是不同于狀態空間方法的另外一種形式化方法,基本思想是對問題進行分解或變換。當一個問題比較復雜時,直接求解比較困難,可以通過分解或變換,將其轉化為一系列較簡單的問題,然后通過對較簡單的球接來實現對原問題的求解。1.問題的分解與等價變換
當把一個問題歸約為子問題時,可采用對原問題的分解或變換方法。235.1搜索策略的基本概念5.1.3問題歸約235.1搜索策略的基本概念(1)分解如果一個問題P可以歸約為一組子問題P1,P2,…,Pn,并且只有當所有子問題Pi(I=1,2,…,n)都有解時,原問題P才有解,任何一個子問題Pi(I=1,2,…,n)無解都會導致原問題P無解。稱這種歸約為問題的分解。分解所得到的子問題的“與”與原問題P等價。245.1搜索策略的基本概念(1)分解245.1搜索策略的基本概念(2)等價變換如果一個問題P可以歸約為一組子問題P1,P2,…,Pn,并且這些子問題Pi(I=1,2,…,n)中只要有一個有解則原問題P就有解,只有當所有的子問題都無解時,原問題P才無解,稱這種歸約為問題的等價變換。簡稱變換。即變換所得的子問題的“或”與原問題P等價。255.1搜索策略的基本概念(2)等價變換255.1搜索策略的基本概念在實際問題的歸約過程中,有可能需要同時采用變換和分解的方法。無論是分解還是變換,都是要將原問題歸約為一系列本原問題。所謂本原問題是指那種不能分解(或不需要分解)或變換,且可以直接解答的子問題。本原問題可以作為終止歸約的限制條件。265.1搜索策略的基本概念在實際問題的歸5.1搜索策略的基本概念2.問題歸約的“與或樹”表示
當把一個原問題歸約為一系列本原問題的過程可以很方便的用一個“與或樹”來表示。(1)與樹(2)或樹275.1搜索策略的基本概念2.問題歸約的“與或樹”表示275.1搜索策略的基本概念(3)與/或樹285.1搜索策略的基本概念(3)與/或樹285.1搜索策略的基本概念(4)端節點與終止節點端節點:沒有子節點的節點。終止節點:本原問題所對應的節點。(5)可解節點與不可解節點滿足以下三個條件的為可解節點:任何終止節點都是可解節點;對“或”節點,當其子節點中至少有一個可解節點時,則該或節點就是可解節點;對“與”節點,只有當其子節點全部為可解節點時,則該與節點才是可解節點。295.1搜索策略的基本概念(4)端節點與終止節點295.1搜索策略的基本概念滿足以下三個條件的為不可解節點:不為終止節點的端節點是不可解節點;對“或”節點,若其全部子節點中為不可解節點時,則該或節點就是不可解節點;對“與”節點,只要其子節點中有一個為不可解節點時,則該與節點才是不可解節點。305.1搜索策略的基本概念滿足以下三個條件的為不可解節點:305.1搜索策略的基本概念(6)解樹由可解節點構成,并且由這些可解節點可以推出初始節點(對應著原始問題)為可解節點的子樹為解樹。在解樹中一定包含初始節點。315.1搜索策略的基本概念(6)解樹315.1搜索策略的基本概念325.1搜索策略的基本概念325.1搜索策略的基本概念3.問題歸約的例子例5.4:三階梵塔問題:設有三根鋼針,它們的編號分別是1,2,3。在初始情況下,1號鋼針上穿有A、B、C三個金片,自上而下,有小到大,。要求把這兩個金片全部移到另一根鋼針上,而且規定每次只能移動一個金片,任何時刻都不能使大片位于小片的上面。用歸約法求解。335.1搜索策略的基本概念3.問題歸約的例子335.1搜索策略的基本概念解:為了能夠解決這一問題,首先需要定義該問題的形式化表示方法。用三元組(i,j,k)表示問題任何時刻的狀態;用“→”表示狀態的轉換;i表示金片C的針號;j表示金片B的針號;k表示金片A的針號;345.1搜索策略的基本概念解:為了能夠解決這一問題,首先需要定5.1搜索策略的基本概念利用問題歸約方法,原問題可分解為以下三個子問題:(1)把金片A及B移到2號鋼針上的雙金片移動問題:(1,1,1)→(1,2,2)(2)把金片C移到3號鋼針上的單金片移動問題:(1,2,2)→(3,2,2)(1)把金片A及B移到3號鋼針上的雙金片移動問題:(3,2,2)→(3,3,3)355.1搜索策略的基本概念利用問題歸約方法,原問題可分解為以下5.1搜索策略的基本概念(1,1,1)→(3,3,3)(1,1,1)→(1,2,2)(3,2,2)→(3,3,3)(1,2,2)→(3,2,2)(3,3,1)→(3,3,3)(3,2,1)→(3,3,1)(3,2,2)→(3,2,1)(1,2,3)→(1,2,2)(1,1,3)→(1,2,3)(1,1,1)→(1,1,3)365.1搜索策略的基本概念(1,1,1)→(3,3,3)(15.1搜索策略的基本概念原始問題的解:(1,1,1)→(1,1,3)(1,1,3)→(1,2,3)(1,2,3)→(1,2,2)(1,2,2)→(3,2,2)
(3,2,2)→(3,2,1)(3,2,1)→(3,3,1)(3,3,1)→(3,3,3)375.1搜索策略的基本概念原始問題的解:375.2狀態空間的盲目搜索狀態空間的搜索策略可分為盲目搜索和啟發式搜索。啟發式搜索需要抽取與問題本身有關的特征信息,而信息抽取比較困難,所以盲目搜索仍不失為一種有效的搜索策略。385.2狀態空間的盲目搜索狀態空間的搜索策略可分為盲目搜5.2狀態空間的盲目搜索5.2.1一般圖搜索過程當用狀態空間法解決問題時,需要考慮:(1)對于很大問題,計算機無法保存其全部狀態空間;(2)對于具體問題,與解有關的狀態空間一般僅是全部狀態空間的一部分。因此在問題求解過程中,沒有必要生成和保存該問題的全部狀態空間,只要能夠生成和保存與解有關的那部分狀態空間即可。解決問題的方法是采用狀態空間搜索技術。395.2狀態空間的盲目搜索5.2.1一般圖搜索過程395.2狀態空間的盲目搜索對狀態空間的搜索,由于問題的狀態空間可用一個有向圖來表示,因此狀態空間搜索實際上就是對有向圖的搜索。405.2狀態空間的盲目搜索對狀態空間的搜5.2狀態空間的盲目搜索狀態空間搜索的基本思想是:先把問題的初始狀態作為當前擴展節點對其進行擴展,生成一組子節點,然后檢查問題的目標狀態是否出現在這些子節點中。若出現,則搜索成功,找到了問題的解;若沒有出現,則按照某種搜索策略從已生成的子節點中選擇一個節點作為擴展節點,重復上述過程,指導目標狀態出現在子節點中或者沒有可供擴展的節點為止。415.2狀態空間的盲目搜索狀態空間搜索的基本思想是:415.2狀態空間的盲目搜索狀態空間算法:需要設立數據結構Open和Closed表。Open表(未擴展節點表):用于存放剛生成沒有擴展的節點;Closed表(已擴展節點表):用于存放已經擴展或將要擴展的節點。425.2狀態空間的盲目搜索狀態空間算法:425.2狀態空間的盲目搜索狀態空間的一般圖搜索過程為:(1)把初始節點S0放入Open表并建立目前僅包含S0的圖G;(2)檢查Open表是否為空,若為空,則問題無解,失敗退出;(3)把Open表的第一個節點取出放入Closed表,并記該節點為節點n;(4)考察節點n是否為目標節點。若是則得到了問題的解,成功退出;435.2狀態空間的盲目搜索狀態空間的一般圖搜索過程為:435.2狀態空間的盲目搜索(5)擴展節點n,生成一組子節點。把這些子節點中不是節點n先輩的那部分子節點記入集合M,并把這些子節點作為節點n的子節點加入G中。(6)針對M中子節點的不同情況,分別作如下處理:對那些沒有在G中出現過的M成員設置一個指向其父節點(即節點n)的指針,并把它放入Open表;對那些原來已在G中出現過,但還沒有被擴展的M成員,確定是否需要修改它指向父節點的指針;445.2狀態空間的盲目搜索(5)擴展節點n,生成一組子節點。把5.2狀態空間的盲目搜索對于先前已在G中出現過,并已經擴展了的M成員,確定是否需要修改其后繼節點指向父節點的指針。(7)按某種策略對Open表中的節點進行排序;(8)轉(2)步。455.2狀態空間的盲目搜索對于先前已在G中出現過,并已經擴展了5.2狀態空間的盲目搜索搜索過程說明:(1)狀態空間圖搜索算法具有通用性,其它的各種狀態空間搜索策略都是上述的一個特例。各種搜索策略的主要區別在于對Open表中節點的排列順序不同。如廣度優先搜索把先生成的子節點排在前面;深度優先搜索把后生成的子節點排在前面。465.2狀態空間的盲目搜索搜索過程說明:465.2狀態空間的盲目搜索(2)在第(5)步對節點n擴展后,生成并記入M的子節點有以下三種情況:該子節點從未被任何節點生成過,由n第一次生成;該子節點原來被其它節點生成過,但還沒有被擴展,這一次又被n再次生成;該子節點原來被其它節點生成過,并且已經被擴展過,這一次又被n再次生成。475.2狀態空間的盲目搜索(2)在第(5)步對節點n擴展后,生5.2狀態空間的盲目搜索對于一般圖搜索算法,具有以上三種情況;對于盲目搜索,由于其狀態空間是樹狀結構,因此不會出現后兩種情況,每個節點擴展后生成的子節點都是第一次出現的節點,不必檢查并修改指向父節點的指針。(3)在第(6)步針對M中子節點的不同情況進行處理時,如果發生上面第2種情況,一般是由原時節點到該節點路徑上所付出的代價來決定。485.2狀態空間的盲目搜索對于一般圖搜索5.2狀態空間的盲目搜索例題見書P1775.2.2廣度優先搜索廣度優先搜索也成為寬度優先搜索,是一種先生成的節點限擴展的策略。
495.2狀態空間的盲目搜索例題見書P177495.2狀態空間的盲目搜索廣度優先搜索策略搜索過程為:從初始節點S0開始逐層向下擴展,在第n曾節點還沒有全部搜索完之前,不進入第n+1層節點的搜索。Open表中的節點總是按進入的先后排序,先進入Open表的節點排在前面,后進入的節點排在后面。505.2狀態空間的盲目搜索廣度優先搜索策略搜索過程為:5.2狀態空間的盲目搜索廣度優先搜索算法如下:(1)把初始節點S0放入Open表中;(2)如果Open表為空,則問題無解,失敗退出。(3)把Open表的第一個節點取出放入Closed表,并記該節點為節點n;(4)考察節點n是否為目標節點。若是則得到了問題的解,成功退出;(5)若節點n不可擴展,則轉第(2)步。515.2狀態空間的盲目搜索廣度優先搜索算法如下:515.2狀態空間的盲目搜索(6)擴展節點n,將其子節點放入Open表的尾部。并為每個子節點設置指向父節點指針,然后轉第(2)步。例5.5八數碼難題。見書P178525.2狀態空間的盲目搜索(6)擴展節點n,將其子節點放入Op5.2狀態空間的盲目搜索5.2.3深度優先搜索深度優先搜索是一種后生成的節點先擴展的策略。深度優先搜索策略搜索過程為:從初始節點S0開始,在其子節點中選擇一個最新生成的節點進行考察,如果該子解不是目標節點而且可以擴展,則擴展該子節點,然后再在此子節點的子節點中選擇一個最新生成的節點進行考察,依次向下搜索,直到某個子節點即不是目標節點,又不能繼續擴展時,才選擇其兄弟節點進行考察。535.2狀態空間的盲目搜索5.2.3深度優先搜索535.2狀態空間的盲目搜索Open表示一種棧結構,最先進入的節點排在最后面,最后進入的節點排在最前面。
深度優先搜索算法如下:(1)把初始節點S0放入Open表中;(2)如果Open表為空,則問題無解,失敗退出。(3)把Open表的第一個節點取出放入Closed表,并記該節點為節點n;545.2狀態空間的盲目搜索Open表示一5.2狀態空間的盲目搜索(4)考察節點n是否為目標節點。若是則得到了問題的解,成功退出;(5)若節點n不可擴展,則轉第(2)步。(6)擴展節點n,將其子節點放入Open表的首部。并為每個子節點設置指向父節點指針,然后轉第(2)步。例5.6八數碼難題。見書P179555.2狀態空間的盲目搜索(4)考察節點n是否為目標節點。若是5.2狀態空間的盲目搜索5.2.4有界深度優先搜索深度優先搜索如果目標不在搜索的分支上,且該分支又是一個無限分支,則搜索過程就不可能找到解。即使能夠找到節,按深度優先找到的解也不一定是最優解。有界深度優先搜索過程總體上按深度優先策略進行,但對搜索深度需要給出一個深度限制dm,當搜索深度達到了dm,但還沒有找到目標時,就停止該分支的搜索,換到另外一個分支進行搜索。565.2狀態空間的盲目搜索5.2.4有界深度優先搜索565.2狀態空間的盲目搜索有界深度優先搜索算法如下:(1)把初始節點S0放入Open表中;(2)如果Open表為空,則問題無解,失敗退出。(3)把Open表的第一個節點取出放入Closed表,并記該節點為節點n;(4)考察節點n是否為目標節點。若是則得到了問題的解,成功退出;575.2狀態空間的盲目搜索有界深度優先搜索算法如下:575.2狀態空間的盲目搜索(5)若節點n的深度d(n)=dm,則轉第(2)步。(6)若節點n不可擴展,則轉第(2)步。(7)擴展節點n,將其子節點放入Open表的首部。并為每個子節點設置指向父節點指針,然后轉第(2)步。例5.7八數碼難題。見書P180585.2狀態空間的盲目搜索(5)若節點n的深度d(n)=dm,5.2狀態空間的盲目搜索5.2.5代價樹搜索需要在搜索樹的每條邊標上其代價。這種有代價的樹稱為代價樹。在代價樹中,用g(n)表示從初始節點S0到節點n的代價,用c(n1,n2)表從父節點n1到其子節點n2的代價,對節點n2的代價有:
g(n2)=g(n1)+c(n1,n2)595.2狀態空間的盲目搜索5.2.5代價樹搜索595.2狀態空間的盲目搜索在代價樹中,最小代價的路徑和最短路徑(即路徑長度最短)是有可能的。最短路徑不一定是代價最小的路徑;代價最小的路徑不一定是最短路徑。1.代價樹的廣度優先搜索代價樹的廣度優先搜索也稱為分枝界限法。每次從Open表中選擇節點或往closed表中存放節點時,總是選擇代價小的節點排在前面,代價大的排在后面,與節點在樹中的位置無關。605.2狀態空間的盲目搜索在代價樹中,最5.2狀態空間的盲目搜索代價樹的廣度優先搜索算法如下:(1)把初始節點S0放入Open表中,置S0的代價g(s0)=0;(2)如果Open表為空,則問題無解,失敗退出。(3)把Open表的第一個節點取出放入Closed表,并記該節點為節點n;(4)考察節點n是否為目標節點。若是則得到了問題的解,成功退出;615.2狀態空間的盲目搜索代價樹的廣度優先搜索算法如下:615.2狀態空間的盲目搜索(5)若節點n不可擴展,則轉第(2)步。(6)擴展節點n,生成子節點ni(I=1,2,…),將這些子節點放入Open表中,并為每個子節點設置指向父節點指針;按如下公式:
g(ni)=g(n)+c(n,ni)(i=1,2,…)計算各自節點的代價,并根據各節點的代價對Open表中的全部按照從小到大順序重新進行排序,然后轉第(2)步。625.2狀態空間的盲目搜索(5)若節點n不可擴展,則轉第(5.2狀態空間的盲目搜索代價樹的廣度優先搜索是完備的,如果問題有解,上述算法一定能夠找到,并且找到的是最優解。例5.8城市交通問題。P181635.2狀態空間的盲目搜索代價樹的廣度5.2狀態空間的盲目搜索2.代價樹的深度優先搜索代價樹的深度優先搜索每次從Open表中選擇節點或往closed表中存放節點時,總是從剛擴展的子節點中選擇一個代價最小的節點。645.2狀態空間的盲目搜索2.代價樹的深度優先搜索645.2狀態空間的盲目搜索代價樹的深度優先搜索算法如下:(1)把初始節點S0放入Open表中,置S0的代價g(s0)=0;(2)如果Open表為空,則問題無解,失敗退出。(3)把Open表的第一個節點取出放入Closed表,并記該節點為節點n;(4)考察節點n是否為目標節點。若是則得到了問題的解,成功退出;655.2狀態空間的盲目搜索代價樹的深度優先搜索算法如下:655.2狀態空間的盲目搜索(5)若節點n不可擴展,則轉第(2)步。(6)擴展節點n,生成子節點ni(I=1,2,…),將這些子節點按邊代價由小到大放入Open表的首部,并為每個子節點設置指向父節點指針。然后轉第(2)步。例5.8城市交通問題。665.2狀態空間的盲目搜索(5)若節點n不可擴展,則轉第(5.3狀態空間的啟發式搜索5.3.1啟發性信息和估價函數啟發式搜索方法所依據的是問題自身的啟發性信息,啟發性信息又是通過估價函數作用到搜索過程中。1.啟發性信息啟發性信息是至于具體問題求解過程無關的,并可指導搜索過程朝著最有希望方向前進的控制信息。675.3狀態空間的啟發式搜索5.3.1啟發性信息和估價函數5.3狀態空間的啟發式搜索啟發性信息一般有三種:(1)有效地幫助確定擴展節點的信息。(2)有效地幫助決定哪些后繼節點應被生成的信息。(3)能決定在擴展一個節點時哪些節點應從搜索樹上刪除的信息。搜索過程的啟發性信息的啟發能力越強,擴展的無用節點就越少。685.3狀態空間的啟發式搜索啟發性信息一般有三種:685.3狀態空間的啟發式搜索2.估價函數用來估計節點重要性的函數稱為估價函數。估價函數f(n)被定義為從初始節點S0出發到,約束經過節點n到達目標節點Sg的所有路徑中最小路徑代價的估計值。其一般形式為:
F(n)=g(n)+h(n)其中:g(n)是從初始節點S0到節點n的實際代價;h(n)是從節點n到目標節點Sg的最優路徑的估計代價。695.3狀態空間的啟發式搜索2.估價函數695.3狀態空間的啟發式搜索例5.9八數碼難題P1835.3.2A算法在圖搜索算法中,如果能在搜索的每一步都利用估價函數F(n)=g(n)+h(n)對Open表中的節點進行排序,則該搜索算法為A算法,由于估價函數中帶有自身的啟發性信息,A算法又稱為啟發式搜索算法。705.3狀態空間的啟發式搜索例5.9八數碼難題P183705.3狀態空間的啟發式搜索1.全局擇優搜索在全局擇優搜索中,每當需要擴展節點時總是從Open表的所有節點中選擇一個估計函數值最小的節點進行擴展,其搜索過程可描述如下:(1)把初始節點S0放入Open表中,f(S0)=g(S0)+h(S0);(2)如果Open表為空,則問題無解,失敗退出。715.3狀態空間的啟發式搜索1.全局擇優搜索715.3狀態空間的啟發式搜索(3)把Open表的第一個節點取出放入Closed表,并記該節點為節點n;(4)考察節點n是否為目標節點。若是則得到了問題的解,成功退出;(5)若節點n不可擴展,則轉第(2)步。(6)擴展節點n,生成子節點ni(i=1,2,…),計算每一個子節點的估價值f(ni)(I=1,2,…),并為每個子節點設置指向父節點指針。然后將這些子節點放入Open表中。
725.3狀態空間的啟發式搜索(3)把Open表的第一個節點取5.3狀態空間的啟發式搜索(7)根據各節點的估價函數值,對Open表中的全部節點按從小到大的順序重新進行排序。(8)轉第(2)步。如果估價函數F(n)=g(n),則退化為代價樹的廣度優先搜索;如果估價函數F(n)=d(n),則退化為廣度優先搜索;可見,廣度優先搜索和代價樹的廣度優先搜索是全局擇優搜索的兩個特例。例5.10八數碼難題P184735.3狀態空間的啟發式搜索(7)根據各節點的估價函數值,對5.3狀態空間的啟發式搜索2.局部擇優搜索在局部擇優搜索中,每當需要擴展節點時總是從剛生成的子節點中選擇一個估價函數值最小的節點進行擴展。其搜索過程可描述如下:(1)把初始節點S0放入Open表中,f(S0)=g(S0)+h(S0);(2)如果Open表為空,則問題無解,失敗退出。745.3狀態空間的啟發式搜索2.局部擇優搜索745.3狀態空間的啟發式搜索(3)把Open表的第一個節點取出放入Closed表,并記該節點為節點n;(4)考察節點n是否為目標節點。若是則得到了問題的解,成功退出;(5)若節點n不可擴展,則轉第(2)步。(6)擴展節點n,生成子節點ni(i=1,2,…),計算每一個子節點的估價值f(ni)(i=1,2,…),并按股價值從小到大的順序依次放入Open表的首部,并為每個子節點設置指向父節點指針。然后轉(2)步。755.3狀態空間的啟發式搜索(3)把Open表的第一個節點取5.3狀態空間的啟發式搜索可見,深度優先搜索和代價樹的深度優先搜索是局部擇優搜索的兩個特例。5.3.3A*算法在啟發式搜索中沒有對估價函數f(n)做任何限制。實際上,估價函數對搜索過程是十分重要的,如果選擇不當,則有可能找不到問題的界,為此,需要對估價函數進行適當的限制。A*算嘎就是對估價寒暑加上一些先之后的到的一種啟發式搜索算法。765.3狀態空間的啟發式搜索可見,深度5.3狀態空間的啟發式搜索1.A*算法的可納性2.A*算法的最優性3.h(n)的單調限制5.3.4A*算法應用舉例例5.11八樹碼難題P190例5.12修道士和野人問題P190775.3狀態空間的啟發式搜索1.A*算法的可納性775.4與/或樹的盲目搜索5.4.1與/或樹的一般搜索
與/或樹的搜索過程實際上是一個不斷搜索尋找解樹的過程,其一般搜索過程為:(1)(2)(3)(4)見書P191785.4與/或樹的盲目搜索5.4.1與/或樹的一般搜索785.4與/或樹的盲目搜索5.4.2與/或樹的廣度優先搜索P1925.4.3與/或樹的深度優先搜索P193795.4與/或樹的盲目搜索5.4.2與/或樹的廣度優先搜索5.5與/或樹的啟發式搜索5.5.1解樹的代價與希望樹5.5.2與或樹的啟發式搜索過程805.5與/或樹的啟發式搜索5.5.1解樹的代價與希望樹85.6博奕樹的啟發式搜索5.6.1概述5.5.2極大極小過程815.6博奕樹的啟發式搜索5.6.1概述81本章小結:82本章小結:82謝謝!83謝謝!83一個智能系統搜索策略的優劣直接影響到系統的性能語推理效率。
本章主要內容:搜索的基本概念;狀態空間的盲目搜索;狀態空間的啟發式搜索;與或樹的盲目搜索;與或樹的啟發式搜索;博奕樹的啟發式搜索;第5章搜索測略84一個智能系統搜索策略的優劣直接影響到系5.1搜索策略的基本概念
5.1.1搜索的含義1.搜索定義:根據問題的實際情況,不斷尋找可利用的知識,從而構造一條代價最小的推理路線,使問題得以解決的過程稱為搜索。2.組合爆炸問題:結構良好,理論上有算法可依的問題,如果問題或算法的復雜性較高(按指數形式增長),由于受計算機在時間和空間上的限制,無法付諸實用。855.1搜索策略的基本概念5.1.1搜索的含義25.1搜索策略的基本概念3.搜索類型:(1)根據是否使用啟發信息分類:盲目搜索:按預定的控制策略進行,在搜索過程中獲得的中間信息不改變控制策略。啟發式搜索:在搜索過程中加入了與問題有關的啟發性信息,用于指導搜索朝著最有希望的方向前進,加速問題的求解過程并找到最優解。865.1搜索策略的基本概念3.搜索類型:35.1搜索策略的基本概念(2)根據問題的表示方式分類:狀態空間搜索:用狀態空間法來求解問題所進行的搜索。與/或樹搜索:用問題歸約法來求解問題時所進行的搜索。875.1搜索策略的基本概念(2)根據問題的表示方式分類:45.1搜索策略的基本概念5.1.2狀態空間法1.狀態空間表示法(1)狀態(state):表示問題求解過程中每一步問題狀況的數據結構,形式的表示為:
Sk={Sk0,Sk1,…)當對每一個分量都予以確定的值時,就得到了一個具體的狀態。885.1搜索策略的基本概念5.1.2狀態空間法55.1搜索策略的基本概念(2)操作(operator)(算符)把問題從一種狀態轉換為另一種狀態的手段。可以是一個機械步驟、一個運算、一條規則或一個過程。可理解為狀態集合上的一個函數,描述了狀態之間的關系。895.1搜索策略的基本概念(2)操作(operator)(算符5.1搜索策略的基本概念(3)狀態空間(statespace)描述一個問題的全部狀態以及這些狀態之間的相互關系。常用三元組表示:(S,F,G)S:為問題所有初始狀態的集合。
F:為操作的集合。
G:為目標狀態的集合。905.1搜索策略的基本概念(3)狀態空間(statespac5.1搜索策略的基本概念狀態空間圖:賦值的有向圖。節點表示問題的狀態,有向邊表示操作.2.狀態空間問題求解任何以狀態和操作為基礎的問題求解方法都稱為狀態空間問題求解。簡稱為狀態空間法。狀態空間法的基本過程為:(1)為問題選擇適當的“狀態”及“操作”的形式化描述方法。915.1搜索策略的基本概念狀態空間圖:賦值的有向圖。節點表示5.1搜索策略的基本概念(2)從某個初始狀態出發,每次使用一個“操作”,遞增地建立起操作序列,直到達到目標狀態為止。(3)從初始狀態到目標狀態所使用的算符序列就是問題的一個解。925.1搜索策略的基本概念(2)從某個初始狀態出發,每次使用一5.1搜索策略的基本概念3.狀態空間的例子例5.1:二階梵塔問題:設有三根鋼針,它們的編號分別是1,2,3。在初始情況下,1號鋼針上穿有A、B兩個金片,A比B小,A位于B的上面。要求把這兩個金片全部移到另一根鋼針上,而且規定每次只能移動一個金片,任何時刻都不能使大片位于小片的上面。935.1搜索策略的基本概念3.狀態空間的例子105.1搜索策略的基本概念解:設用Sk={Sk0,Sk1}表示問題的狀態,其中,Sk0表示金片A所在的鋼針號,Sk1表示金片B所在的鋼針號。全部可能的問題狀態共有以下9種:S0=(1,1)S1=(1,2)S2=(1,3)S3=(2,1)S4=(2,2)S5=(2,3)S6=(3,1)S7=(3,2)S8=(3,3)其中S0為初始狀態,S4和S8為目標狀態。945.1搜索策略的基本概念解:設用Sk={Sk0,Sk1}表5.1搜索策略的基本概念任何以狀態和操作為基礎的問題求解方法都稱為狀態空間問題求解。簡稱為狀態空間法。狀態空間法的基本過程為:(1)為問題選擇適當的“狀態”及“操作”的形式化描述方法。(2)從某個初始狀態出發,每次使用一個“操作”,遞增地建立起操作序列,直到達到目標狀態為止。(3)從初始狀態到目標狀態所使用的算符序列就是問題的一個解。955.1搜索策略的基本概念任何以狀態和操5.1搜索策略的基本概念例5.2修道士和野人問題.首先選取描述問題狀態的方法。用一個三元組表示狀態:S=(m,c,b)其中:m表示左岸的修道士數;c表示左岸的野人數;b表示左岸的船數;965.1搜索策略的基本概念例5.2修道士和野人問題.135.1搜索策略的基本概念右岸的狀態由下式確定:右岸的修道士數m’=3-m;右岸的野人數c’=3-c;
右岸的船數b’=1-b;
m和c的取值分別為0,1,2,3之一;b的取值分別為0,1;
共有4x4x2=32種狀態。975.1搜索策略的基本概念右岸的狀態由下式確定:145.1搜索策略的基本概念3,32,12,31,21,3A(3,2)2,23,23,11,1B(1,2)A(1,3)二階樊塔狀態空間圖985.1搜索策略的基本概念3,32,12,31,21,3A(35.1搜索策略的基本概念除去不合法的狀態和修道士被野人吃掉的狀態,余下的狀態由16種:S0=(3,3,1),S1=(3,2,1),S2=(3,1,1),S3=(2,2,1),S4=(1,1,1),S5=(0,3,1),S6=(0,2,1),S7=(0,1,1),S8=(3,2,0),S9=(3,1,0),S10=(3,0,0),S11=(2,2,0),S12=(1,1,0),S13=(0,2,0),S14=(0,1,0),S15=(0,0,0),995.1搜索策略的基本概念除去不合法的狀態和修道士被野人吃掉的5.1搜索策略的基本概念需要考慮的操作有:(1)船至少有一個人(m或c)操作,離開岸邊的m和c的減少數目應該等于到達岸邊的m和c的增加數目;(2)每次操作船上的人數不得超過2個;(3)操作應保證不產生非法狀態。操作由兩部分組成:條件部分和動作部分。1005.1搜索策略的基本概念需要考慮的操作有:175.1搜索策略的基本概念用Qij表示從右岸到左岸的運人操作,可供選擇的操作由10種,操作集為:F={P01,P10,P11,P02,P20,Q01,Q10,Q11,Q02,Q20,}以P01和Q01為例說明操作的條件和動作:操作符號條件動作P01b=1,m=0或3,c≥1b=0,c=c-1Q01b=1,m=0或3,c≤2b=1,c=c+11015.1搜索策略的基本概念用Qij表示從5.1搜索策略的基本概念例5.3猴子摘香蕉問題.
首先選取描述問題狀態的方法。用一個四元組表示狀態:S=(w,x,y,z)
其中:w表示猴子的水平位置;x表示箱子的水平位置;
y表示猴子是否在箱子上,當猴子在箱子上時y=1否則y=0;
z表示猴子是否拿到香蕉,當拿到香蕉時z=1否則z=0;1025.1搜索策略的基本概念例5.3猴子摘香蕉問題.195.1搜索策略的基本概念所有可能的狀態有:S0=(a,b,0,0),初始狀態S1=(b,b,0,0),S2=(c,c,1,0),S3=(c,c,1,1),目標狀態1035.1搜索策略的基本概念所有可能的狀態有:205.1搜索策略的基本概念允許的操作為:Goto(u):猴子走到位置u,即:(w,x,0,0)→(u,x,0,0)Pushbox(v):猴子推著箱子到水平位置v,即:(x,x,0,0)→(v,v,0,0)Climbbox:猴子爬上箱子,即:(x,x,0,0)→(x,x,1,0)Grasp:猴子拿到香蕉,即:(c,c,1,0)→(c,c,1,1)1045.1搜索策略的基本概念允許的操作為:215.1搜索策略的基本概念問題的狀態空間圖見書P172,圖5-3.由初始狀態變為目標狀態的操作序列為:{Goto(b),Pushbox?,Climbbox,Grasp}1055.1搜索策略的基本概念問題的狀態空間圖見書P172,圖5-5.1搜索策略的基本概念5.1.3問題歸約
問題是不同于狀態空間方法的另外一種形式化方法,基本思想是對問題進行分解或變換。當一個問題比較復雜時,直接求解比較困難,可以通過分解或變換,將其轉化為一系列較簡單的問題,然后通過對較簡單的球接來實現對原問題的求解。1.問題的分解與等價變換
當把一個問題歸約為子問題時,可采用對原問題的分解或變換方法。1065.1搜索策略的基本概念5.1.3問題歸約235.1搜索策略的基本概念(1)分解如果一個問題P可以歸約為一組子問題P1,P2,…,Pn,并且只有當所有子問題Pi(I=1,2,…,n)都有解時,原問題P才有解,任何一個子問題Pi(I=1,2,…,n)無解都會導致原問題P無解。稱這種歸約為問題的分解。分解所得到的子問題的“與”與原問題P等價。1075.1搜索策略的基本概念(1)分解245.1搜索策略的基本概念(2)等價變換如果一個問題P可以歸約為一組子問題P1,P2,…,Pn,并且這些子問題Pi(I=1,2,…,n)中只要有一個有解則原問題P就有解,只有當所有的子問題都無解時,原問題P才無解,稱這種歸約為問題的等價變換。簡稱變換。即變換所得的子問題的“或”與原問題P等價。1085.1搜索策略的基本概念(2)等價變換255.1搜索策略的基本概念在實際問題的歸約過程中,有可能需要同時采用變換和分解的方法。無論是分解還是變換,都是要將原問題歸約為一系列本原問題。所謂本原問題是指那種不能分解(或不需要分解)或變換,且可以直接解答的子問題。本原問題可以作為終止歸約的限制條件。1095.1搜索策略的基本概念在實際問題的歸5.1搜索策略的基本概念2.問題歸約的“與或樹”表示
當把一個原問題歸約為一系列本原問題的過程可以很方便的用一個“與或樹”來表示。(1)與樹(2)或樹1105.1搜索策略的基本概念2.問題歸約的“與或樹”表示275.1搜索策略的基本概念(3)與/或樹1115.1搜索策略的基本概念(3)與/或樹285.1搜索策略的基本概念(4)端節點與終止節點端節點:沒有子節點的節點。終止節點:本原問題所對應的節點。(5)可解節點與不可解節點滿足以下三個條件的為可解節點:任何終止節點都是可解節點;對“或”節點,當其子節點中至少有一個可解節點時,則該或節點就是可解節點;對“與”節點,只有當其子節點全部為可解節點時,則該與節點才是可解節點。1125.1搜索策略的基本概念(4)端節點與終止節點295.1搜索策略的基本概念滿足以下三個條件的為不可解節點:不為終止節點的端節點是不可解節點;對“或”節點,若其全部子節點中為不可解節點時,則該或節點就是不可解節點;對“與”節點,只要其子節點中有一個為不可解節點時,則該與節點才是不可解節點。1135.1搜索策略的基本概念滿足以下三個條件的為不可解節點:305.1搜索策略的基本概念(6)解樹由可解節點構成,并且由這些可解節點可以推出初始節點(對應著原始問題)為可解節點的子樹為解樹。在解樹中一定包含初始節點。1145.1搜索策略的基本概念(6)解樹315.1搜索策略的基本概念1155.1搜索策略的基本概念325.1搜索策略的基本概念3.問題歸約的例子例5.4:三階梵塔問題:設有三根鋼針,它們的編號分別是1,2,3。在初始情況下,1號鋼針上穿有A、B、C三個金片,自上而下,有小到大,。要求把這兩個金片全部移到另一根鋼針上,而且規定每次只能移動一個金片,任何時刻都不能使大片位于小片的上面。用歸約法求解。1165.1搜索策略的基本概念3.問題歸約的例子335.1搜索策略的基本概念解:為了能夠解決這一問題,首先需要定義該問題的形式化表示方法。用三元組(i,j,k)表示問題任何時刻的狀態;用“→”表示狀態的轉換;i表示金片C的針號;j表示金片B的針號;k表示金片A的針號;1175.1搜索策略的基本概念解:為了能夠解決這一問題,首先需要定5.1搜索策略的基本概念利用問題歸約方法,原問題可分解為以下三個子問題:(1)把金片A及B移到2號鋼針上的雙金片移動問題:(1,1,1)→(1,2,2)(2)把金片C移到3號鋼針上的單金片移動問題:(1,2,2)→(3,2,2)(1)把金片A及B移到3號鋼針上的雙金片移動問題:(3,2,2)→(3,3,3)1185.1搜索策略的基本概念利用問題歸約方法,原問題可分解為以下5.1搜索策略的基本概念(1,1,1)→(3,3,3)(1,1,1)→(1,2,2)(3,2,2)→(3,3,3)(1,2,2)→(3,2,2)(3,3,1)→(3,3,3)(3,2,1)→(3,3,1)(3,2,2)→(3,2,1)(1,2,3)→(1,2,2)(1,1,3)→(1,2,3)(1,1,1)→(1,1,3)1195.1搜索策略的基本概念(1,1,1)→(3,3,3)(15.1搜索策略的基本概念原始問題的解:(1,1,1)→(1,1,3)(1,1,3)→(1,2,3)(1,2,3)→(1,2,2)(1,2,2)→(3,2,2)
(3,2,2)→(3,2,1)(3,2,1)→(3,3,1)(3,3,1)→(3,3,3)1205.1搜索策略的基本概念原始問題的解:375.2狀態空間的盲目搜索狀態空間的搜索策略可分為盲目搜索和啟發式搜索。啟發式搜索需要抽取與問題本身有關的特征信息,而信息抽取比較困難,所以盲目搜索仍不失為一種有效的搜索策略。1215.2狀態空間的盲目搜索狀態空間的搜索策略可分為盲目搜5.2狀態空間的盲目搜索5.2.1一般圖搜索過程當用狀態空間法解決問題時,需要考慮:(1)對于很大問題,計算機無法保存其全部狀態空間;(2)對于具體問題,與解有關的狀態空間一般僅是全部狀態空間的一部分。因此在問題求解過程中,沒有必要生成和保存該問題的全部狀態空間,只要能夠生成和保存與解有關的那部分狀態空間即可。解決問題的方法是采用狀態空間搜索技術。1225.2狀態空間的盲目搜索5.2.1一般圖搜索過程395.2狀態空間的盲目搜索對狀態空間的搜索,由于問題的狀態空間可用一個有向圖來表示,因此狀態空間搜索實際上就是對有向圖的搜索。1235.2狀態空間的盲目搜索對狀態空間的搜5.2狀態空間的盲目搜索狀態空間搜索的基本思想是:先把問題的初始狀態作為當前擴展節點對其進行擴展,生成一組子節點,然后檢查問題的目標狀態是否出現在這些子節點中。若出現,則搜索成功,找到了問題的解;若沒有出現,則按照某種搜索策略從已生成的子節點中選擇一個節點作為擴展節點,重復上述過程,指導目標狀態出現在子節點中或者沒有可供擴展的節點為止。1245.2狀態空間的盲目搜索狀態空間搜索的基本思想是:415.2狀態空間的盲目搜索狀態空間算法:需要設立數據結構Open和Closed表。Open表(未擴展節點表):用于存放剛生成沒有擴展的節點;Closed表(已擴展節點表):用于存放已經擴展或將要擴展的節點。1255.2狀態空間的盲目搜索狀態空間算法:425.2狀態空間的盲目搜索狀態空間的一般圖搜索過程為:(1)把初始節點S0放入Open表并建立目前僅包含S0的圖G;(2)檢查Open表是否為空,若為空,則問題無解,失敗退出;(3)把Open表的第一個節點取出放入Closed表,并記該節點為節點n;(4)考察節點n是否為目標節點。若是則得到了問題的解,成功退出;1265.2狀態空間的盲目搜索狀態空間的一般圖搜索過程為:435.2狀態空間的盲目搜索(5)擴展節點n,生成一組子節點。把這些子節點中不是節點n先輩的那部分子節點記入集合M,并把這些子節點作為節點n的子節點加入G中。(6)針對M中子節點的不同情況,分別作如下處理:對那些沒有在G中出現過的M成員設置一個指向其父節點(即節點n)的指針,并把它放入Open表;對那些原來已在G中出現過,但還沒有被擴展的M成員,確定是否需要修改它指向父節點的指針;1275.2狀態空間的盲目搜索(5)擴展節點n,生成一組子節點。把5.2狀態空間的盲目搜索對于先前已在G中出現過,并已經擴展了的M成員,確定是否需要修改其后繼節點指向父節點的指針。(7)按某種策略對Open表中的節點進行排序;(8)轉(2)步。1285.2狀態空間的盲目搜索對于先前已在G中出現過,并已經擴展了5.2狀態空間的盲目搜索搜索過程說明:(1)狀態空間圖搜索算法具有通用性,其它的各種狀態空間搜索策略都是上述的一個特例。各種搜索策略的主要區別在于對Open表中節點的排列順序不同。如廣度優先搜索把先生成的子節點排在前面;深度優先搜索把后生成的子節點排在前面。1295.2狀態空間的盲目搜索搜索過程說明:465.2狀態空間的盲目搜索(2)在第(5)步對節點n擴展后,生成并記入M的子節點有以下三種情況:該子節點從未被任何節點生成過,由n第一次生成;該子節點原來被其它節點生成過,但還沒有被擴展,這一次又被n再次生成;該子節點原來被其它節點生成過,并且已經被擴展過,這一次又被n再次生成。1305.2狀態空間的盲目搜索(2)在第(5)步對節點n擴展后,生5.2狀態空間的盲目搜索對于一般圖搜索算法,具有以上三種情況;對于盲目搜索,由于其狀態空間是樹狀結構,因此不會出現后兩種情況,每個節點擴展后生成的子節點都是第一次出現的節點,不必檢查并修改指向父節點的指針。(3)在第(6)步針對M中子節點的不同情況進行處理時,如果發生上面第2種情況,一般是由原時節點到該節點路徑上所付出的代價來決定。1315.2狀態空間的盲目搜索對于一般圖搜索5.2狀態空間的盲目搜索例題見書P1775.2.2廣度優先搜索廣度優先搜索也成為寬度優先搜索,是一種先生成的節點限擴展的策略。
1325.2狀態空間的盲目搜索例題見書P177495.2狀態空間的盲目搜索廣度優先搜索策略搜索過程為:從初始節點S0開始逐層向下擴展,在第n曾節點還沒有全部搜索完之前,不進入第n+1層節點的搜索。Open表中的節點總是按進入的先后排序,先進入Open表的節點排在前面,后進入的節點排在后面。1335.2狀態空間的盲目搜索廣度優先搜索策略搜索過程為:5.2狀態空間的盲目搜索廣度優先搜索算法如下:(1)把初始節點S0放入Open表中;(2)如果Open表為空,則問題無解,失敗退出。(3)把Open表的第一個節點取出放入Closed表,并記該節點為節點n;(4)考察節點n是否為目標節點。若是則得到了問題的解,成功退出;(5)若節點n不可擴展,則轉第(2)步。1345.2狀態空間的盲目搜索廣度優先搜索算法如下:515.2狀態空間的盲目搜索(6)擴展節點n,將其子節點放入Open表的尾部。并為每個子節點設置指向父節點指針,然后轉第(2)步。例5.5八數碼難題。見書P1781355.2狀態空間的盲目搜索(6)擴展節點n,將其子節點放入Op5.2狀態空間的盲目搜索5.2.3深度優先搜索深度優先搜索是一種后生成的節點先擴展的策略。深度優先搜索策略搜索過程為:從初始節點S0開始,在其子節點中選擇一個最新生成的節點進行考察,如果該子解不是目標節點而且可以擴展,則擴展該子節點,然后再在此子節點的子節點中選擇一個最新生成的節點進行考察,依次向下搜索,直到某個子節點即不是目標節點,又不能繼續擴展時,才選擇其兄弟節點進行考察。1365.2狀態空間的盲目搜索5.2.3深度優先搜索535.2狀態空間的盲目搜索Open表示一種棧結構,最先進入的節點排在最后面,最后進入的節點排在最前面。
深度優先搜索算法如下:(1)把初始節點S0放入Open表中;(2)如果Open表為空,則問題無解,失敗退出。(3)把Open表的第一個節點取出放入Closed表,并記該節點為節點n;1375.2狀態空間的盲目搜索Open表示一5.2狀態空間的盲目搜索(4)考察節點n是否為目標節點。若是則得到了問題的解,成功退出;(5)若節點n不可擴展,則轉第(2)步。(6)擴展節點n,將其子節點放入Open表的首部。并為每個子節點設置指向父節點指針,然后轉第(2)步。例5.6八數碼難題。見書P1791385.2狀態空間的盲目搜索(4)考察節點n是否為目標節點。若是5.2狀態空間的盲目搜索5.2.4有界深度優先搜索深度優先搜索如果目標不在搜索的分支上,且該分支又是一個無限分支,則搜索過程就不可能找到解。即使能夠找到節,按深度優先找到的解也不一定是最優解。有界深度優先搜索過程總體上按深度優先策略進行,但對搜索深度需要給出一個深度限制dm,當搜索深度達到了dm,但還沒有找到目標時,就停止該分支的搜索,換到另外一個分支進行搜索。1395.2狀態空間的盲目搜索5.2.4有界深度優先搜索565.2狀態空間的盲目搜索有界深度優先搜索算法如下:(1)把初始節點S0放入Open表中;(2)如果Open表為空,則問題無解,失敗退出。(3)把Open表的第一個節點取出放入Closed表,并記該節點為節點n;(4)考察節點n是否為目標節點。若是則得到了問題的解,成功退出;1405.2狀態空間的盲目搜索有界深度優先搜索算法如下:575.2狀態空間的盲目搜索(5)若節點n的深度d(n)=dm,則轉第(2)步。(6)若節點n不可擴展,則轉第(2)步。(7)擴展節點n,將其子節點放入Open表的首部。并為每個子節點設置指向父節點指針,然后轉第(2)步。例5.7八數碼難題。見書P1801415.2狀態空間的盲目搜索(5)若節點n的深度d(n)=dm,5.2狀態空間的盲目搜索5.2.5代價樹搜索需要在搜索樹的每條邊標上其代價。這種有代價的樹稱為代價樹。在代價樹中,用g(n)表示從初始節點S0到節點n的代價,用c(n1,n2)表從父節點n1到其子節點n2的代價,對節點n2的代價有:
g(n2)=g(n1)+c(n1,n2)1425.2狀態空間的盲目搜索5.2.5代價樹搜索595.2狀態空間的盲目搜索在代價樹中,最小代價的路徑和最短路徑(即路徑長度最短)是有可能的。最短路徑不一定是代價最小的路徑;代價最小的路徑不一定是最短路徑。1.代價樹的廣度優先搜索代價樹的廣度優先搜索也稱為分枝界限法。每次從Open表中選擇節點或往closed表中存放節點時,總是選擇代價小的節點排在前面,代價大的排在后面,與節點在樹中的位置無關。1435.2狀態空間的盲目搜索在代價樹中,最5.2狀態空間的盲目搜索代價樹的廣度優先搜索算法如下:(1)把初始節點S0放入Open表中,置S0的代價g(s0)=0;(2)如果Open表為空,則問題無解,失敗退出。(3)把Open表的第一個節點取出放入Closed表,并記該節點為節點n;(4)考察節點n是否為目標節點。若是則得到了問題的解,成功退出;1445.2狀態空間的盲目搜索代價樹的廣度優先搜索算法如下:615.2狀態空間的盲目搜索(5)若節點n不可擴展,則轉第(2)步。(6)擴展節點n,生成子節點ni(I=1,2,…),將這些子節點放入Open表中,并為每個子節點設置指向父節點指針;按如下公式:
g(ni)=g(n)+c(n,ni)(i=1,2,…)計算各自節點的代價,并根據各節點的代價對Open表中的全部按照從小到大順序重新進行排序,然后轉第(2)步。1455.2狀態空間的盲目搜索(5)若節點n不可擴展,則轉第(5.2狀態空間的盲目搜索代價樹的廣度優先搜索是完備的,如果問題有解,上述算法一定能夠找到,并且找到的是最優解。例5.8城市交通問題。P1811465.2狀態空間的盲目搜索代價樹的廣度5.2狀態空間的盲目搜索2.代價樹的深度優先搜索代價樹的深度優先搜索每次從Open表中選擇節點或往closed表中存放節點時,總是從剛擴展的子節點中選擇一個代價最小的節點。1475.2狀態空間的盲目搜索2.代價樹的深度優先搜索645.2狀態空間的盲目搜索代價樹的深度優先搜索算法如下:(1)把初始節點S0放入Open表中,置S0的代價g(s0)=0;(2)如果Open表為空,則問題無解,失敗退出。(3)把Open表的第一個節點取出放入Closed表,并記該節點為節點n;(4)考察節點n是否為目標節點。若是則得到了問題的解,
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經權益所有人同意不得將文件中的內容挪作商業或盈利用途。
- 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 水庫進口段施工方案模板
- 礦產資源開發與區域經濟發展-石墨滑石考核試卷
- 木結構防火施工方案
- 糧食批發商市場規范化管理與監管策略研究考核試卷
- 解答證券從業資格證考試疑難試題及答案
- 2023年中國鐵路上海局集團有限公司招聘高等職業院校畢業生3163人(二)筆試參考題庫附帶答案詳解
- 2024項目管理考試復習要點試題及答案
- 硫酸銅在金屬腐蝕中的應用考核試卷
- 2023年中國能建陜西院智能配網公司招聘變電電氣設計崗位工作人員筆試參考題庫附帶答案詳解
- 2023年中國聯合網絡通信有限公司會昌分公司公開招聘工作人員筆試參考題庫附帶答案詳解
- 探究膜分離技術在水處理中的應用
- 洋流課件2024-2025學年高中地理人教版(2019)選擇性必修一
- 2024-2025學年中職數學拓展模塊一 (下冊)高教版(2021·十四五)教學設計合集
- 電梯維保工程施工組織設計方案
- 2024-2030年中國消防行業市場發展分析及發展趨勢與投資前景研究報告
- 外研版(2019) 必修第三冊 Unit 2 Making a Difference教案
- 醫院科研成果及知識產權管理規范
- DB32T-公路橋梁水下結構檢測評定標準
- 高職藥學專業《藥物制劑技術》說課課件
- 低碳環保管理制度
- 急診科提高出診車物品放置規范率PDCA項目
評論
0/150
提交評論