人工智能-5搜索策略

1人工智能

ArtificialIntelligence主講：鮑軍鵬博士西安交通大學電信學院計算機系電子郵箱：dr.baojp@版本：2.02010年1月第五章 搜索策略5.1概述5.2狀態(tài)空間搜索5.3與或樹搜索25.1概述5.1.1什么是搜索根據(jù)問題的實際情況不斷尋找可利用的知識，從而構造一條代價較少的推理路線，使問題得到圓滿解決的過程稱為搜索。在人工智能中即使對于結構性能較好，理論上有算法可依的問題，由于問題本身的復雜性以及計算機在時間、空間上的局限性，往往也需要通過搜索來求解。3搜索的分類搜索分為盲目搜索和啟發(fā)式搜索。盲目搜索是按照預定的控制策略進行搜索，在搜索過程中獲得的中間信息不用來改進控制策略。啟發(fā)式搜索是在搜索中加入了與問題有關的啟發(fā)性信息，用以指導搜索朝著最有希望的方向前進，加速問題的求解過程并找到最優(yōu)解。45.1.2狀態(tài)空間表示法問題求解過程可以看作一個搜索過程。狀態(tài)空間表示法是用來表示問題及其搜索過程的一種方法。它是人工智能中最基本的一種形式化方法。狀態(tài)空間用“狀態(tài)”和“算符”來表示問題。狀態(tài) 狀態(tài)用以描述問題求解過程中不同時刻的狀況，是一個數(shù)據(jù)結構，一般用一組變量的有序組合表示：SK=(Sk0,Sk1,…)當每一個分量的值確定時，就得到了一個具體的狀態(tài)。算符 引起狀態(tài)中某些分量發(fā)生變化，從而使問題從一個狀態(tài)變?yōu)榱硪粋€狀態(tài)的操作稱為算符。在產(chǎn)生式系統(tǒng)中，一條產(chǎn)生式規(guī)則就是一個算符。狀態(tài)空間由問題的全部狀態(tài)及一切可用算符所構成的集合稱為問題的狀態(tài)空間，一般用一個三元組表示：(S,F,G)其中S是問題所有初始狀態(tài)的集合；F是算符的集合；G是目標狀態(tài)的集合。狀態(tài)空間的圖示形式稱為狀態(tài)空間圖。5狀態(tài)空間示例——二階梵塔問題 設用SK=(Sk0,Sk1)表示問題的狀態(tài)，SK0表示金片A所在的柱號，Sk1表示金片B所在的柱號，全部可能的狀態(tài)有九種：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)

問題的初始狀態(tài)集合為S={S0},目標狀態(tài)集合為G={S4,S8}。 算符分別用A(i,j)及B(i,j)。A(i,j)表示把A金片從第i號柱移到第j號柱。

B(i,j)與之同理。算符共有12個。 在狀態(tài)空間圖中，從初始節(jié)點(1,1)到目標節(jié)點(2,2)或(3,3)的任何一條通路都是問題的一個解。其中最短的路徑長度是3，它由3個算符組成。例如:A(1,3),B(1,2),A(3,2)6狀態(tài)空間用狀態(tài)空間方法表示問題，首先必須定義狀態(tài)的描述形式，把問題的一切狀態(tài)都表示出來。其次要定義一組算符。問題的求解過程是一個不斷把算符作用于狀態(tài)的過程。如果在使用某個算符后得到的新狀態(tài)是目標狀態(tài)，就得到了問題的一個解。這個解是從初始狀態(tài)到目標狀態(tài)所用算符構成的序列。算符的一次使用，就使問題由一種狀態(tài)轉(zhuǎn)變?yōu)榱硪环N狀態(tài)。使用算符最少的解或者總代價最少的解稱為最優(yōu)解。對任何一個狀態(tài)，可使用的算符可能不止一個。這樣由一個狀態(tài)所生成的后繼狀態(tài)就可能有多個。此時首先對哪一個狀態(tài)進行操作，就取決于搜索策略。75.1.3與或樹表示法與或樹是用于表示問題及其求解過程的又一種形式化方法，通常用于表示比較復雜問題的求解。對于一個復雜問題，直接求解往往比較困難。此時可通過下述方法進行簡化：分解 把一個復雜問題分解為若干個較為簡單的子問題，每個子問題又可繼續(xù)分解。重復此過程，直到不需要或者不能再分解為止。如此形成“與”樹。等價變換 利用同構或同態(tài)的等價變換，把原問題變換為若干個較為容易求解的新問題。如此形成“或”樹。8與或樹9與或樹的基本概念本原問題不能再分解或變換，而且直接可解的子問題。端節(jié)點與終止節(jié)點在與/或樹中，沒有子節(jié)點的節(jié)點統(tǒng)稱為端節(jié)點；本原問題所對應的節(jié)點稱為終止節(jié)點?？山夤?jié)點在與/或樹中，滿足下列條件之一者，稱為可解節(jié)點：它是一個終止節(jié)點；它是一個“或”節(jié)點，且其子節(jié)點中至少有一個是可解節(jié)點；它是一個“與”節(jié)點，且其子節(jié)點全部是可解節(jié)點。不可解節(jié)點關于可解節(jié)點的三個條件全部不滿足的節(jié)點10解樹 由可解節(jié)點所構成，并且由這些可解節(jié)點可推出初始節(jié)點為可解節(jié)點的子樹稱為解樹。11三階梵塔問題的與或樹125.2狀態(tài)空間搜索13盲目搜索的特點：搜索按規(guī)定的路線進行，不使用與問題有關的啟發(fā)性信息；適用于其狀態(tài)空間圖是樹狀結構的一類問題。啟發(fā)式搜索要使用與問題有關的啟發(fā)性信息，并以這些啟發(fā)性信息指導搜索過程，可以高效地求解結構復雜的問題。搜索的原則廣度優(yōu)先搜索按照“先擴展出的節(jié)點先被考察”的原則進行搜索；深度優(yōu)先搜索按照“后擴展出的節(jié)點先被考察”的原則進行搜索；有界深度優(yōu)先搜索的原則與深度優(yōu)先搜索相同，但是它規(guī)定了深度限界，使搜索不得無限制地向縱深方向發(fā)展；代價樹的廣度優(yōu)先搜索按照“哪個節(jié)點到根節(jié)點的代價小就先考察哪個節(jié)點”的原則進行搜索；代價樹的深度優(yōu)先搜索按照“當前節(jié)點的哪個子節(jié)點到其父節(jié)點的代價小就先考察哪個子節(jié)點”的原則進行搜索；局部擇優(yōu)搜索按照“當前節(jié)點的哪個子節(jié)點到目標節(jié)點的估計代價小就先考察哪個子節(jié)點”的原則進行搜索；全局擇優(yōu)搜索按照“哪個節(jié)點到目標節(jié)點的估計代價小就先考察哪個節(jié)點”的原則進行搜索；145.2.1狀態(tài)空間的一般搜索過程OPEN表和CLOSE表OPEN表用于存放剛生成的節(jié)點。對于不同的搜索策略，節(jié)點在OPEN表中的排列順序是不同的。CLOSE表用于存放將要擴展或者已經(jīng)擴展的節(jié)點。

OPEN表 CLOSE表15狀態(tài)節(jié)點父節(jié)點編號狀態(tài)節(jié)點父節(jié)點搜索的一般過程把初始節(jié)點S0放入OPEN表，并建立目前只包含S0的圖，記為G；檢查OPEN表是否為空，若為空則問題無解，退出；把OPEN表的第一個節(jié)點取出放入CLOSE表，并計該節(jié)點為n；考察節(jié)點n是否為目標節(jié)點。若是，則求得了問題的解，退出；擴展節(jié)點n，生成一組子節(jié)點。把其中不是節(jié)點n先輩的那些子節(jié)點記做集合M，并把這些子節(jié)點作為節(jié)點n的子節(jié)點加入G中；針對M中子節(jié)點的不同情況，分別進行如下處理：對于那些未曾在G中出現(xiàn)過的M成員設置一個指向父節(jié)點（即節(jié)點n）的指針，并把它們放入OPEN表；對于那些先前已經(jīng)在G中出現(xiàn)過的M成員，確定是否需要修改它指向父節(jié)點的指針；對于那些先前已在G中出現(xiàn)并且已經(jīng)擴展了的M成員，確定是否需要修改其后繼節(jié)點指向父節(jié)點的指針；按某種搜索策略對OPEN表中的節(jié)點進行排序；轉(zhuǎn)第2步。16一些說明上述是一個通用過程，各種搜索策略的主要區(qū)別是對OPEN表中節(jié)點排序的準則不同。一個節(jié)點經(jīng)一個算符操作后一般只生成一個子節(jié)點。但適用于一個節(jié)點的算符可能有多個，此時就會生成一組子節(jié)點。這些子節(jié)點中可能有些是當前擴展節(jié)點的父節(jié)點、祖父節(jié)點等，此時不能把這些先輩節(jié)點作為當前擴展節(jié)點的子節(jié)點。一個新生成的節(jié)點，它可能是第一次被生成的節(jié)點，也可能是先前已作為其它節(jié)點的后繼節(jié)點被生成過，當前又作為另一個節(jié)點的后繼節(jié)點被再次生成。此時，它究竟應作為哪個節(jié)點的不后繼節(jié)點？一般由原始節(jié)點到該節(jié)點的代價來決定，代價小的相應節(jié)點就作為父節(jié)點。在搜索過程中，一旦某個被考察的節(jié)點是目標節(jié)點就得到了一個解。該解是由從初始節(jié)點到該目標節(jié)點路徑上的算符構成。如果在搜索中一直找不到目標節(jié)點，而且OPEN表中不再有可供擴展的節(jié)點，則搜索失敗。175.2.2廣度優(yōu)先搜索基本思想： 從初始節(jié)點S0開始，逐層地對節(jié)點進行擴展并考察它是否為目標節(jié)點。在第n層的節(jié)點沒有全部擴展并考察之前，不對第n＋1層的節(jié)點進行擴展。OPEN表中節(jié)點總是按進入的先后順序排列，先進入的節(jié)點排在前面，后進入的排在后面。18廣度優(yōu)先搜索過程把初始節(jié)點S0放入OPEN表。如果OPEN表為空，則問題無解，退出。把OPEN表的第一個節(jié)點（記為節(jié)點n）取出放入CLOSE表?？疾旃?jié)點n是否為目標節(jié)點。若是，則求得了問題的解，退出。若節(jié)點n不可擴展，則轉(zhuǎn)第2步。擴展節(jié)點n，將其子節(jié)點放入OPEN表的尾部，并為每一個子節(jié)點都配置指向父節(jié)點的指針，然后轉(zhuǎn)第2步。19重排九宮的廣度優(yōu)先搜索20廣度優(yōu)先搜索的特點優(yōu)點： 只要問題有解，用廣度優(yōu)先搜索總可以得到解，而且得到的是路徑最短的解。缺點： 廣度優(yōu)先搜索盲目性較大，當目標節(jié)點距初始節(jié)點較遠時將會產(chǎn)生許多無用節(jié)點，搜索效率低。215.2.3深度優(yōu)先搜索基本思想： 從初始節(jié)點S0開始，在其子節(jié)點中選擇一個節(jié)點進行考察。若不是目標節(jié)點，則再在該子節(jié)點的子節(jié)點中選擇一個節(jié)點進行考察，一直如此向下搜索。當達到某個子節(jié)點，且該子節(jié)點既不是目標節(jié)點，又不能繼續(xù)擴展時，才選擇其兄弟節(jié)點進行考察。深度優(yōu)先搜索與廣度優(yōu)先搜索的唯一區(qū)別是：廣度優(yōu)先搜索是將節(jié)點n的子節(jié)點放入到OPEN表的尾部，而深度優(yōu)先搜索是把節(jié)點n的子節(jié)點放入到OPEN表的首部。22深度優(yōu)先搜索過程把初始節(jié)點S0放入OPEN表。如果OPEN表為空，則問題無解，退出。把OPEN表的第一個節(jié)點（記為節(jié)點n）取出放入CLOSE表?？疾旃?jié)點n是否為目標節(jié)點。若是，則求得了問題的解，退出。若節(jié)點n不可擴展，則轉(zhuǎn)第2步。擴展節(jié)點n，將其子節(jié)點放入OPEN表的首部，并為每一個子節(jié)點都配置指向父節(jié)點的指針，然后轉(zhuǎn)第2步。23重排九宮的深度優(yōu)先搜索24深度優(yōu)先搜索的特點在深度優(yōu)先搜索中，搜索一旦進入某個分支，就將沿著該分支一直向下搜索。如果目標節(jié)點恰好在此分支上，則可較快地得到解。但是，如果目標節(jié)點不在此分支上，而該分支又是一個無窮分支，則就不可能得到解。所以深度優(yōu)先搜索是不完備的，即使問題有解，它也不一定能求得解。用深度優(yōu)先求得的解，不一定是路徑最短的解。255.2.4有界深度優(yōu)先搜索基本思想：對深度優(yōu)先搜索引入搜索深度的界限（設為dm），當搜索深度達到了深度界限，而尚未出現(xiàn)目標節(jié)點時，就換一個分支進行搜索。搜索過程：把初始節(jié)點S0放入OPEN表中，置S0的深度d(S0)=0。如果OPEN表為空，則問題無解，退出。把OPEN表的第一個節(jié)點（記為節(jié)點n）取出放入CLOSE表。考察節(jié)點n是否為目標節(jié)點。若是，則求得了問題的解，退出。若節(jié)點n的深度d(節(jié)點n)=dm，則轉(zhuǎn)第2步。若節(jié)點n不可擴展，則轉(zhuǎn)第2步。擴展節(jié)點n，將其子節(jié)點放入OPEN表的首部，并為每一個子節(jié)點都配置指向父節(jié)點的指針，然后轉(zhuǎn)第2步。26如果問題有解，且其路徑長度≤dm，則上述搜索過程一定能求得解。但是，若解的路徑長度>dm,則上述搜索過程就得不到解。這說明在有界深度優(yōu)先搜索中，深度界限的選擇是很重要的。要恰當?shù)亟o出dm的值是比較困難的。即使能求出解，它也不一定是最優(yōu)解。27有界深度優(yōu)先搜索的一些改進方法先任意設定一個較小的數(shù)作為dm，然后進行上述的有界深度優(yōu)先搜索，當搜索達到了指定的深度界限dm仍未發(fā)現(xiàn)目標節(jié)點，并且CLOSE表中仍有待擴展節(jié)點時，就將這些節(jié)點送回OPEN表，同時增大深度界限dm，繼續(xù)向下搜索。如此不斷地增大dm，只要問題有解，就一定可以找到它。但此時找到的解不一定是最優(yōu)解。為了找到最優(yōu)解，可增設一個表R，每找到遠程目標節(jié)點Sg后，就把它放入到R的前面，并令dm等于該目標節(jié)點所對應的路徑長度，然后繼續(xù)搜索。由于后求得的解的路徑長度不會超過先求得的解的路徑長度，所以后求得的解一定是最優(yōu)解。28重排九宮的有界深度優(yōu)先搜索設深度界限dm＝4295.2.5啟發(fā)式搜索盲目搜索具有較大的盲目性，產(chǎn)生的無用節(jié)點較多，搜索空間較大，效率不高。啟發(fā)式搜索要用到問題自身的某些特性信息，以指導搜索朝著最有希望的方向前進。由于這種搜索針對性較強，因而原則上只需要搜索問題的部分狀態(tài)空間，效率較高。30啟發(fā)性信息與估價函數(shù)可用于指導搜索過程，且與具體問題求解有關的控制性信息稱為啟發(fā)性信息。用于估價節(jié)點重要性的函數(shù)稱為估價函數(shù)。其一般形式為：f(x)=g(x)+h(x)其中g(x)為從初始節(jié)點S0到節(jié)點x已經(jīng)實際付出的代價；h(x)是從節(jié)點x到目標節(jié)點Sg的最優(yōu)路徑的估計代價，它體現(xiàn)了問題的啟發(fā)性信息，其形式要根據(jù)問題的特性確定。例如它可以是節(jié)點x到目標節(jié)點的距離，或者節(jié)點x處于最優(yōu)路徑上的概率等等。h(x)稱為啟發(fā)函數(shù)。g(x)指出了搜索的橫向趨勢。它有利于搜索的完備性，但影響搜索的效率。如果我們只關心到達目標節(jié)點的路徑，并且希望有較高的搜索效率，則g(x)可以忽略，但此時會影響搜索的完備性。31估價函數(shù)示例設有如下結構的移動牌游戲：該游戲規(guī)則：當一個牌移入相鄰的空位置時，費用為一個單位。一個牌至多可跳過兩個牌進入空位置，其費用等于跳過的牌數(shù)加1。要求把所有的B都移至W的右邊，請設計估價函數(shù)中的h(x)。解：根據(jù)要求可知，W左邊的B越少越接近目標，因此可用W左邊B的個數(shù)作為h(x),即h(x)=3×(每個W左邊B個數(shù)的總和)這里乘以系數(shù)3是為了擴大h(x)在f(x)中的比重。32BBBWWWE局部擇優(yōu)搜索基本思想： 當一個節(jié)點被擴展以后，按f(x)對每一個子節(jié)點計算估價值，并選擇最小者作為下一個要考察的節(jié)點。搜索過程：把初始節(jié)點S0放入OPEN表，令g(S0)=0。如果OPEN表為空，則問題無解，退出。把OPEN表的第一個節(jié)點（記為節(jié)點n）取出放入CLOSE表。考察節(jié)點n是否為目標節(jié)點。若是，則求得了問題的解，退出。若節(jié)點n不可擴展，則轉(zhuǎn)第2步。擴展節(jié)點n，用估價函數(shù)f(x)計算每個子節(jié)點的估價值，并按估價值從小到大的順序放到OPEN表中的首部，并為每一個子節(jié)點都配置指向父節(jié)點的指針，然后轉(zhuǎn)第2步。深度優(yōu)先搜索、代價樹的深度優(yōu)先搜索以及局部擇優(yōu)搜索都是以子節(jié)點作為考察范圍的。但是前二者可以看作局部擇優(yōu)搜索的特例。33代價樹的深度優(yōu)先搜索基本思想： 在代價樹的廣度優(yōu)先搜索中，每次都是從OPEN表的全體節(jié)點中選擇一個代價最小的節(jié)點送入CLOSE表進行考察。而代價樹的深度優(yōu)先搜索是從剛擴展出的子節(jié)點中選一個代價最小的節(jié)點送入CLOSE表進行考察。搜索過程：把初始節(jié)點S0放入OPEN表，令g(S0)=0。如果OPEN表為空，則問題無解，退出。把OPEN表的第一個節(jié)點（記為節(jié)點n）取出放入CLOSE表。考察節(jié)點n是否為目標節(jié)點。若是，則求得了問題的解，退出。若節(jié)點n不可擴展，則轉(zhuǎn)第2步。擴展節(jié)點n，將其子節(jié)點按代價從小到大的順序放到OPEN表中的首部，并為每一個子節(jié)點都配置指向父節(jié)點的指針，然后轉(zhuǎn)第2步。代價樹的深度有限搜索是不完備的。34全局擇優(yōu)搜索35基本思想： 每當要選擇一個節(jié)點進行考察時，局部擇優(yōu)搜索只是從剛生成的子節(jié)點中進行選擇，選擇的范圍比較狹窄。全局擇優(yōu)搜索每次總是從OPEN表的全體節(jié)點中選擇一個估價值最小的節(jié)點。搜索過程：把初始節(jié)點S0放入OPEN表，計算f(S0)。如果OPEN表為空，則問題無解，退出。把OPEN表的第一個節(jié)點（記為節(jié)點n）取出放入CLOSE表?？疾旃?jié)點n是否為目標節(jié)點。若是，則求得了問題的解，退出。若節(jié)點n不可擴展，則轉(zhuǎn)第2步。擴展節(jié)點n，用估價函數(shù)f(x)計算每個子節(jié)點的估價值，并為每一個子節(jié)點都配置指向父節(jié)點的指針。把這些子節(jié)點都送入OPEN表中，然后對OPEN表中的全部節(jié)點按估價值從小至大的順序進行排序，然后轉(zhuǎn)第2步。廣度優(yōu)先搜索、代價樹的廣度優(yōu)先搜索以及全局擇優(yōu)搜索都是以當前所有節(jié)點作為考察范圍的。但是前二者可以看作全局擇優(yōu)搜索的特例。重排九宮問題的全局擇優(yōu)搜索樹設估價函數(shù)為f(x)=d(x)+h(x)其中，d(x)表示節(jié)點x的深度，h(x)表示節(jié)點x的格局與目標節(jié)點格局不相同的牌數(shù)。36代價樹的廣度優(yōu)先搜索邊上標有代價(或費用)的樹稱為代價樹。用g(x)表示從初始節(jié)點S0到節(jié)點x的代價，用c(x1,x2)表示從父節(jié)點x1到子節(jié)點x2的代價則有：g(x2)=g(x1)+c(x1,x2)基本思想： 每次從OPEN表中選擇節(jié)點往CLOSE表傳送時，總是選擇其代價最小的節(jié)點。也就是說，OPEN表中的節(jié)點在任一時刻都是按其代價從小到大排序的。代價小的節(jié)點排在前面，代價大的節(jié)點排在后面，而不管節(jié)點在代價樹中處于什么位置。如果問題有解，代價樹的廣度優(yōu)先搜索一定可以求得解，并且求出的是最優(yōu)解。37代價樹廣度優(yōu)先搜索過程把初始節(jié)點S0放入OPEN表，令g(S0)=0。如果OPEN表為空，則問題無解，退出。把OPEN表的第一個節(jié)點（記為節(jié)點n）取出放入CLOSE表?？疾旃?jié)點n是否為目標節(jié)點。若是，則求得了問題的解，退出。若節(jié)點n不可擴展，則轉(zhuǎn)第2步。擴展節(jié)點n，將其子節(jié)點放入OPEN表中，并為每一個子節(jié)點都配置指向父節(jié)點的指針。計算各子節(jié)點的代價，并按各節(jié)點的代價對OPEN表中的全部節(jié)點進行排序(按從小到大的順序)，然后轉(zhuǎn)第2步。38代價樹廣度優(yōu)先搜索示例395.2.6A*算法如果使一般搜索過程滿足如下限制，則它就稱為A*算法：1、把OPEN表中的節(jié)點按估價函數(shù)f(x)=g(x)+h(x)

的值從小至大進行排序（一般搜索過程的第7步）。2、g(x)是對g*(x)的估計，g(x)>0。3、h(x)是h*(x)的下界，即對所有的x均有：h(x)≤h*(x)其中，g*(x)是從初始節(jié)點S0到節(jié)點x的最小代價；h*(x)是從節(jié)點x到目標節(jié)點的最小代價，若有多個目標節(jié)點，則為其中最小的一個。40在A*算法中，g(x)實際上就是從初始節(jié)點S0到節(jié)點x的路徑代價，恒有g(x)≥g*(x)。而且在算法執(zhí)行過程中隨著更多搜索信息的獲得，g(x)的值呈下降的趨勢。 例如：H(x)的確定依賴于具體問題領域的啟發(fā)性信息，其中h(x)≤h*(x)的限制十分重要，它保證A*算法能找到最優(yōu)解。41A*算法的性質(zhì)可納性 對于可解狀態(tài)空間圖(即從初始節(jié)點到目標節(jié)點有路徑存在)來說，如果一個搜索算法能在有限步那終止，并且能找到最優(yōu)解，則稱該搜索算法是可納的。A*算法是可納的。A*算法的最優(yōu)性

A*算法的搜索效率在很大程度上取決于h(x)，在滿足h(x)≤h*(x)的前提下，h(x)的值越大越好。h(x)的值越大，表明它攜帶的啟發(fā)性信息越多，搜索時擴展的節(jié)點數(shù)越少，搜索的效率越高。h(x)的單調(diào)性限制 在A*算法中，每當要擴展一個節(jié)點時都要先檢查其子節(jié)點是否已在OPEN表或CLOSE表中，有時還要調(diào)整指向父節(jié)點的指針，這就增加了搜索的代價。如果對啟發(fā)函數(shù)h(x)加上單調(diào)性限制，就可減少檢查及調(diào)整的工作量，從而減少搜索代價。42h(x)的單調(diào)性所謂單調(diào)性限制是指h(x)滿足如下兩個條件：1、h(Sg)=0;2、設xj是節(jié)點xi的任意子節(jié)點，則有h(xi)-h(xj)≤c(xi,xj)，即h(xi)≤h(xj)+c(xi,xj)其中，Sg是目標節(jié)點；c(xi,xj)是