人工智能

ArtificialIntelligence主講：楊利英西安電子科技大學計算機學院E_mail：yangliying1208@163.com第五章 搜索策略5.1基本概念5.2狀態空間的搜索策略5.3與/或樹的搜索策略5.4搜索的完備性與效率5.1基本概念

采用某種策略，在知識庫中尋找可利用的知識，從而構造一條代價較小的推理路線，使問題得到解決的過程稱為搜索。5.1.1什么是搜索5.1.1什么是搜索搜索分為盲目搜索和啟發式搜索。

盲目搜索是按照預定的控制策略進行搜索，在搜索過程中獲得的中間信息不用來改進控制策略。啟發式搜索是在搜索中加入了與問題有關的啟發性信息，用以指導搜索朝著最有希望的方向前進，加速問題的求解過程并找到最優解。5.1.2狀態空間表示法狀態空間用“狀態”和“算符”來表示問題。狀態 狀態用以描述問題在求解過程中不同時刻的狀態，一般用向量表示算符 使問題從一個狀態轉變為另一個狀態的操作稱為算符。狀態空間由所有可能出現的狀態及一切可用算符所構成的集合稱為問題的狀態空間。回顧狀態空間示例：十五數碼難題119151341275861321014119415131275861321014119151341275861321014119415131275861321014119151341275861321014119415131275861321014119415138127561321014119415131275861321014回顧5.1.3與/或樹表示法對于一個復雜問題，直接求解往往比較困難。此時可通過下述方法進行簡化：（1）分解（2）等價變換回顧5.1.3與/或樹表示法（1）分解

把一個復雜問題分解為若干個較為簡單的子問題，每個子問題又可繼續分解。重復此過程，直到不需要再分解或者不能再分解為止。如此形成“與”樹。（2）等價變換 利用同構或同態的等價變換，把原問題變換為若干個較為容易求解的新問題。如此形成“或”樹。回顧與/或樹分解與等價變換可以結合起來使用，這樣形成的圖稱為“與/或樹”回顧由可解節點所構成，并且由這些可解節點可推出初始節點為可解節點的子樹稱為解樹(t表示終止節點)。解樹中一定包含初始節點。（它對應于原始問題）解樹回顧5.2狀態空間的搜索策略5.2狀態空間的搜索策略盲目搜索搜索按規定的路線進行，不使用與問題有關的啟發性信息；適用于其狀態空間圖是樹狀結構的一類問題。啟發式搜索使用與問題有關的啟發性信息，并以這些啟發性信息指導搜索過程，可以高效地求解結構復雜的問題。5.2.1狀態空間的一般搜索過程一個復雜問題的狀態空間一般都是十分龐大的。如64階梵塔問題共有3的64次方個不同的狀態。把問題的所有狀態空間都進行存儲有時候是不可能的。把問題的所有狀態空間都進行存儲也是不必要的。因為與解題有關的狀態空間往往只是整個狀態空間的一部分，只要能生產并存儲這部分狀態空間就可以求出問題的解。5.2.1狀態空間的一般搜索過程如何產生問題需要的狀態空間從而實現對問題的求解呢？答案就是搜索技術。搜索技術基本思想：把問題的初始狀態作為當前狀態，選擇適用的算符對其操作，生產一組子狀態，然后檢查目標狀態是否在其中出現。若出現，則搜索成功，找到了問題的解，否則按某種搜索策略從已生成的狀態中再選擇一個作為當前狀態。重復上述過程，直到目標狀態出現或者不再有可供操作的狀態及算符為止。5.2.1狀態空間的一般搜索過程OPEN表和CLOSE表OPEN表用于存放剛生成的節點。對于不同的搜索策略，節點在OPEN表中的排列順序是不同的。CLOSE表用于存放將要擴展的節點。對一個節點的擴展是指：用所有可適用的算符對該節點進行操作，生成一組子節點 OPEN表 狀態節點父節點編號狀態節點父節點CLOSE表搜索的一般過程把初始節點S0放入OPEN表，并建立目前只包含S0的圖，記為G；檢查OPEN表是否為空，若為空則問題無解，退出；把OPEN表的第一個節點取出放入CLOSE表，并計該節點為n；考察節點n是否為目標節點。若是，則求得了問題的解，退出；擴展節點n，生成一組子節點。把其中不是節點n先輩的那些子節點記做集合M，并把這些子節點作為節點n的子節點加入G中；針對M中子節點的不同情況，分別進行如下處理：對于那些未曾在G中出現過的M成員設置一個指向父節點（即節點n）的指針，并把它們放入OPEN表；（不在OPEN表）對于那些先前已經在G中出現過的M成員，確定是否需要修改它指向父節點的指針；（在OPEN表中）對于那些先前已在G中出現并且已經擴展了的M成員，確定是否需要修改其后繼節點指向父節點的指針；（在CLOSE表中）按某種搜索策略對OPEN表中的節點進行排序；轉第2步。搜索的一般過程對一般搜索過程的一些說明一個節點經一個算符操作后一般只生成一個子節點。但適用于一個節點的算符可能有多個，此時就會生成一組子節點。這些子節點中可能有些是當前擴展節點的父節點、祖父節點等，此時不能把這些先輩節點作為當前擴展節點的子節點。對一般搜索過程的一些說明一個新生成的節點，它可能是第一次被生成的節點，也可能是先前已作為其它節點的子節點被生成過，當前又作為另一個節點的子節點被再次生成。此時，它究竟應選擇哪個節點作為父節點？一般由原始節點到該節點的代價來決定，處于代價小的路途上的那個節點就作為該節點的父節點。對一般搜索過程的一些說明在搜索過程中，一旦某個被考察的節點是目標節點就得到了一個解。該解是由從初始節點到該目標節點路徑上的算符構成。如果在搜索中一直找不到目標節點，而且OPEN表中不再有可供擴展的節點，則搜索失敗。對一般搜索過程的一些說明通過搜索得到的圖稱為搜索圖，搜索圖是狀態空間圖的一個子集。由搜索圖中的所有節點及反向指針所構成的集合是一棵樹，稱為搜索樹。根據搜索樹可給出問題的解。5.2.2廣度（寬度）優先搜索基本思想： 從初始節點S0開始，逐層地對節點進行擴展并考察它是否為目標節點。在第n層的節點沒有全部擴展并考察之前，不對第n＋1層的節點進行擴展。OPEN表中節點總是按進入的先后順序排列，先進入的節點排在前面，后進入的排在后面。廣度優先搜索過程把初始節點S0放入OPEN表。如果OPEN表為空，則問題無解，退出。把OPEN表的第一個節點（記為節點n）取出放入CLOSE表。考察節點n是否為目標節點。若是，則求得了問題的解，退出。若節點n不可擴展，則轉第2步。擴展節點n，將其子節點放入OPEN表的尾部，并為每一個子節點都配置指向父節點的指針，然后轉第2步。重排九宮的廣度優先搜索

操作符：空格左移、上移、右移、下移小插曲－關于九宮問題射雕英雄傳

瑛姑的問題：將一至九這九個數字排成三列，不論縱橫斜角，每三字相加都是十五，如何排法？

黃蓉的回答：九宮之義，法以靈龜，二四為肩，六八為足，左三右七，戴九履一，五居中央。幻方問題中國人首先發現了幻方

洛水神龜獻奇圖關于三階幻方的奧秘南宋楊輝研究幻方第一人

幻方問題在我國古代稱為“縱橫圖”，又叫“九宮算圖”。南宋大數學家楊輝在1275年所著的《續古摘奇算法》兩卷中，除了給出洛書中3階幻方的構造方法外，還給出了4階至10階的幻方。楊輝對3階幻方的解釋29435761816594211714310615138121三階幻方(15)四階幻方(34)歐美的幻方熱德國畫家和文藝理論家丟勒在1514年創作的一幅銅版雕刻畫《憂傷》中就有一個4階幻方。名畫《憂傷》現在珍藏于大英博物館。富蘭克林也投入了很大精力研究幻方。名畫《憂傷》廣度優先算法中需要注意的問題1、對于任意一個可擴展的節點，總是按照固定的操作符的順序對其進行擴展（如前面重排九宮例子中的空格左移、上移、右移、下移）。2、在對任一節點進行擴展的時候，如果所得的某個子節點（狀態）前面已經出現過，則立即將其放棄，不再重復畫出（不送入OPEN表）。因此，廣度優先搜索的本質是：以初始節點為根節點，在狀態空間圖中按照廣度優先的原則，生成一棵搜索樹。廣度優先搜索的特點優點： 只要問題有解，用廣度優先搜索總可以得到解，而且得到的是路徑最短的解。缺點： 廣度優先搜索盲目性較大，當目標節點距初始節點較遠時將會產生許多無用節點，搜索效率低。5.2.3深度優先搜索基本思想：從初始節點開始，在其子節點中選擇一個節點進行考察，若不是目標節點，則再在該子節點的子節點中選擇一個節點進行考察，一直如此向下搜索。當到達某個子節點，且該子節點既不是目標節點又不能繼續擴展時，才選擇其兄弟節點進行考察。深度優先搜索與廣度優先搜索的唯一區別：廣度優先搜索是將節點n的子節點放入到OPEN表的尾部，而深度優先搜索是把節點n的子節點放入到OPEN表的首部。深度優先搜索過程把初始節點S0放入OPEN表。如果OPEN表為空，則問題無解，退出。把OPEN表的第一個節點（記為節點n）取出放入CLOSE表。考察節點n是否為目標節點。若是，則求得了問題的解，退出。若節點n不可擴展，則轉第2步。擴展節點n，將其子節點放入OPEN表的首部，并為每一個子節點都配置指向父節點的指針，然后轉第2步。重排九宮的深度優先搜索操作符：空格左移、上移、右移、下移深度優先搜索的特點在深度優先搜索中，搜索一旦進入某個分支，就將沿著該分支一直向下搜索。如果目標節點恰好在此分支上，則可較快地得到解。但是，如果目標節點不在此分支上，而該分支又是一個無窮分支，則就不可能得到解。所以深度優先搜索是不完備的，即使問題有解，它也不一定能求得解。用深度優先求得的解，不一定是路徑最短的解。本質：以初始節點為根節點，在狀態空間圖中按照深度優先的原則，生成一棵搜索樹。5.2.4有界深度優先搜索基本思想：對深度優先搜索引入搜索深度界限（設為dm），當搜索深度達到了深度界限，而仍未出現目標節點時，就換一個分支進行搜索。“有界”是為了解決深度優先搜索不完備的問題，避免陷入無窮分支的死循環。有界深度優先搜索過程把初始節點S0放入OPEN表中，置S0的深度d(S0)=0。如果OPEN表為空，則問題無解，退出。把OPEN表的第一個節點（記為節點n）取出放入CLOSE表。考察節點n是否為目標節點。若是，則求得了問題的解，退出。若節點n的深度d(n)=dm，則轉第2步（此時節點n位于CLOSE表，但并未進行擴展）。若節點n不可擴展，則轉第2步。擴展節點n，將其子節點放入OPEN表的首部，為每一個子節點都配置指向父節點的指針，將每一個子節點的深度設置為d(n)+1，然后轉第2步。對有界深度優先搜索的說明如果問題有解，且其路徑長度≤dm，則上述搜索過程一定能求得解。但是，若解的路徑長度>dm,則上述搜索過程就得不到解。這說明在有界深度優先搜索中，深度界限的選擇是很重要的。要恰當地給出dm的值是比較困難的。即使能求出解，它也不一定是最優解。有界深度優先搜索的改進先任意設定一個較小的數作為dm，然后進行上述的有界深度優先搜索，當搜索達到了指定的深度界限dm仍未發現目標節點，并且CLOSE表中仍有待擴展節點時，就將這些節點送回OPEN表，同時增大深度界限dm，繼續向下搜索。如此不斷地增大dm，只要問題有解，就一定可以找到它。但此時找到的解不一定是最優解。有界深度優先搜索的改進2.為了找到最優解，可增設一個表R，每找到目標節點Sg后，就把它放入到R的前面，并令dm等于該目標節點所對應的路徑長度，然后繼續搜索。由于后求得的解的路徑長度不會超過先求得的解的路徑長度，所以最后求得的解一定是最優解。重排九宮的有界深度優先搜索設深度界限dm＝45.2.5代價樹的廣度優先搜索邊上標有代價(或費用)的樹稱為代價樹。用g(x)表示從初始節點S0到節點x的代價，用c(x1,x2)表示從父節點x1到子節點x2的代價，則有：g(x2)=g(x1)+c(x1,x2)5.2.5代價樹的廣度優先搜索每次從OPEN表中選擇節點往CLOSE表傳送時，總是選擇其中代價最小的節點。也就是說，OPEN表中的節點在任一時刻都是按其代價從小到大排序的。代價小的節點排在前面，代價大的節點排在后面。如果問題有解，代價樹的廣度優先搜索一定可以求得解，并且求出的是最優解。該算法應用的條件:該算法是針對代價樹的算法。為了采用該算法對圖進行搜索，必須先將圖轉換為代價樹。代價樹廣度優先搜索過程把初始節點S0放入OPEN表，令g(S0)=0。如果OPEN表為空，則問題無解，退出。把OPEN表的第一個節點（記為節點n）取出放入CLOSE表。考察節點n是否為目標節點。若是，則求得了問題的解，退出。若節點n不可擴展，則轉第2步。擴展節點n，為每一個子節點都配置指向父節點的指針，并將各子節點放入OPEN表中；計算各子節點的代價，按各節點的代價對OPEN表中的全部節點進行排序(按從小到大的順序)，然后轉第2步。代價樹示例圖到代價樹的轉換求A到E的最小費用交通路線代價樹的廣度優先搜索5.2.6代價樹的深度優先搜索在代價樹的廣度優先搜索中，每次都是從OPEN表的全體節點中選擇一個代價最小的節點送入CLOSE表進行考察在代價樹的深度優先搜索中，是從剛擴展出的子節點中選擇一個代價最小的節點送入CLOSE表進行考察代價樹的深度優先搜索過程把初始節點S0放入OPEN表，令g(S0)=0。如果OPEN表為空，則問題無解，退出。把OPEN表的第一個節點（記為節點n）取出放入CLOSE表。考察節點n是否為目標節點。若是，則求得了問題的解，退出。若節點n不可擴展，則轉第2步。擴展節點n，將其子節點按“邊”代價從小到大的順序放到OPEN表中的首部，并為每一個子節點都配置指向父節點的指針，然后轉第2步。代價樹的深度優先搜索是不完備的。

總結

1、上述各種搜索方法的本質是，以初始節點為根節點，按照既定的策略對狀態空間圖進行遍歷，并希望能夠盡早發現目標節點。2、由于對狀態空間圖遍歷的策略是既定的，因此這些方法統稱為盲目搜索方法。5.2.7啟發式搜索盲目搜索具有較大的盲目性，產生的無用節點較多，效率不高。啟發式搜索采用問題自身的特性信息，以指導搜索朝著最有希望的方向前進。這種搜索針對性較強，因而效率較高。1.啟發性信息與估價函數可用于指導搜索過程，且與具體問題有關的信息稱為啟發性信息。用于評估節點重要性的函數稱為估價函數。其一般形式為：f(x)=g(x)+h(x)其中g(x)表示從初始節點S0到節點x的代價；h(x)是從節點x到目標節點Sg的最優路徑的代價的估計，它體現了問題的啟發性信息，稱為啟發函數。f(x)決定節點在OPEN表中的次序。1.啟發性信息與估價函數g(x)指出了搜索的橫向趨勢，有利于搜索的完備性，但影響搜索的效率。h(x)指出了搜索的縱向趨勢，有利于提高搜索的效率，但影響搜索的完備性。確定f(x)時要使g(x)+h(x)各占適當比重。啟發函數示例設有如下結構的移動將牌游戲：游戲規則：當一個牌移入相鄰的空位置時，費用為一個單位。一個牌至多可跳過兩個牌進入空位置，其費用等于跳過的牌數加1。要求：把所有的B都移至W的右邊，請設計啟發函數h(x)。解：根據要求可知，W左邊的B越少越接近目標，因此可用W左邊B的個數作為h(x),即h(x)=3×(每個W左邊B的個數的總和)這里乘以系數3是為了擴大h(x)在f(x)中的比重。BBBWWWEBEBWWBW例如下面這一狀態：h(x)=3×(2+2+3)=212.局部擇優搜索局部擇優搜索是一種啟發式搜索方法，是對深度優先搜索方法的一種改進。基本思想：當一個節點被擴展以后，按f(x)對每一個子節點計算估價值，并選擇最小者作為下一個要考察的節點。局部擇優搜索過程把初始節點S0放入OPEN表，計算f(S0)。如果OPEN表為空，則問題無解，退出。把OPEN表的第一個節點（記為節點n）取出放入CLOSE表。考察節點n是否為目標節點。若是，則求得了問題的解，退出。若節點n不可擴展，則轉第2步。擴展節點n，用估價函數f(x)計算每個子節點的估價值，并按估價值從小到大的順序放到OPEN表中的首部，并為每一個子節點都配置指向父節點的指針，然后轉第2步。2.局部擇優搜索在局部擇優搜索中，若令f(x)=g(x)，則局部擇優搜索就成為代價樹的深度優先搜索。在局部擇優搜索中，若令f(x)=d(x)，這里d(x)表示節點x的深度，則局部擇優搜索就成為深度優先搜索。因此：深度優先搜索、代價樹的深度優先搜索均為局部擇優搜索的特例。3.全局擇優搜索每當要選擇下一個節點進行考察時，局部擇優搜索只是從剛生成的子節點中選擇一個估價值最小的節點。其選擇范圍比較窄。每當要選擇下一個節點進行考察時，全局擇優搜索每次總是從OPEN表的全體節點中選擇一個估價值最小的節點。全局擇優搜索過程把初始節點S0放入OPEN表，計算f(S0)。如果OPEN表為空，則問題無解，退出。把OPEN表的第一個節點（記為節點n）取出放入CLOSE表。考察節點n是否為目標節點。若是，則求得了問題的解，退出。若節點n不可擴展，則轉第2步。擴展節點n，用估價函數f(x)計算每個子節點的估價值，并為每一個子節點都配置指向父節點的指針。把這些子節點都送入OPEN表中，然后對OPEN表中的全部節點按估價值從小至大的順序進行排序，然后轉第2步。3.全局擇優搜索在全局擇優搜索中，若令f(x)=g(x)，則它就成為代價樹的廣度優先搜索。在全局擇優搜索中，若令f(x)=d(x)，這里d(x)表示節點x的深度，則它就成為廣度優先搜索。因此：廣度優先搜索、代價樹的廣度優先搜索是全局擇優搜索的兩個特例。重排九宮問題的全局擇優搜索樹設估價函數為f(x)=d(x)+h(x)，其中，d(x)表示節點x的深度，h(x)表示節點x的格局與目標節點格局不相同的牌數。5.3與/或樹的搜索策略5.3.1與/或樹的一般搜索過程5.3.2博弈樹的啟發式搜索5.3.3α–β剪枝技術5.3與/或樹的搜索策略5.3與/或樹的搜索策略用與/或樹方法求解問題時，首先要定義問題的描述方法及分解和變換問題的算符，然后就可以用它們通過搜索生成與/或樹，從而求得原始問題的解。在與/或樹中，由可解子節點來確定其父節點、祖父節點等為可解節點的過程稱為可解標示過程；由不可解子節點來確定其父節點、祖父節點等為不可解節點的過程稱為不可解標示過程；在與/或樹搜索過程中，將反復使用可解和不可解標示過程，直到初始節點被標示為可解或不可解節點為止。5.3.1與/或樹的一般搜索過程把原始問題作為初始節點S0，并把S0作為當前節點；應用分解或等價算法對當前節點進行擴展；為每個子節點設置指向父節點的指針；選擇合適的子節點作為當前節點，反復執行第2和第3步，期間將反復使用可解和不可解標示過程，直到初始節點被標示為可解或不可解節點為止。由這個搜索過程形成的節點和指針結構稱為搜索樹。與/或樹的廣度優先搜索把初始節點S0放入OPEN表。把OPEN表的第一個節點（記為節點n）取出放入CLOSE表。若節點n可擴展，則做如下工作。擴展節點n，將其子節點放入OPEN表的尾部，并為每個子節點配置指向父節點的指針，以備標示過程使用。考察這些子節點中是否有終止節點。如有，則標示這些終止節點為可解節點，并用可解標示過程對其先輩節點中的可解節點進行標示。如果初始節點S0也被標示為可解節點，則得到了解樹，搜索成功，退出；如果不能確定S0為可解節點，則從OPEN表中刪去具有可解先輩的節點。轉第2步。若節點n不可擴展，則做如下工作。標示節點n為不可解節點。用不可解標示過程對n的先輩節點中的不可解節點進行標示。如果初始節點S0也被標示為不可解節點，則搜索失敗，退出；如果不能確定S0為不可解節點，則從OPEN表中刪去具有不可解先輩的節點。轉第2步。與/或樹的（有界）深度優先搜索把初始節點S0放入OPEN表。把OPEN表的第個節一點（記為節點n）取出放入CLOSE表。若節點n的深度大于等于深度界限，則轉第5步中的第①。若節點n可擴展，則做如下工作。擴展節點n，將其子節點放入OPEN表的首部，并為每個子節點配置指向父節點的指針，以備標示過程使用。考察這些子節點中是否有終止節點。如有，則標示這些終止節點為可解節點，并用可解標示過程對其先輩節點中的可解節點進行標示。如果初始節點S0也被標示為可解節點，則得到了解樹，搜索成功，退出；如果不能確定S0為可解節點，則從OPEN表中刪去具有可解先輩的節點。轉第2步。若節點n不可擴展，則做如下工作。標示節點n為不可解節點。用不可解標示過程對n的先輩節點中的不可解節點進行標示。如果初始節點S0也被標示為不可解節點，則搜索失敗，退出；如果不能確定S0為不可解節點，則從OPEN表中刪去具有不可解先輩的節點。轉第2步。與/或樹的廣度和深度優先搜索舉例A廣度優先的擴展順序：.5深度優先的擴展順序（規定深度界限為4）：1.3.B.5.2.4A,B為不可解的端節點t1,t2,t3,t4為終止節點1t2t1t4t354B325.3.2博弈樹的啟發式搜索1.博弈樹的基本概念博弈：諸如下棋、打牌、戰爭等一類競爭性智能活動。“二人零和、全信息、非偶然”博弈（1）對壘的雙方A、B輪流采取行動，博弈的結果只有三種情況：A勝B敗，A敗B勝，平局。（2）對壘過程中，任何一方都了解當前的格局及過去的歷史。（3）雙方都是理智的決定自己的行動的。博弈樹描述博弈過程的與/或樹稱為博弈樹，它具有如下特點：（1）博弈的初始格局是初始節點。（2）在博弈樹中，或節點和與節點是交替出現的。己方擴展的節點之間是或關系，對方擴展的節點之間是與關系。雙方輪流擴展。（3）所有能使己方獲勝的終局都是可解節點，使對方獲勝的終局是不可解節點。博弈樹是始終站在一方的立場上得出的。2.極大極小分析法極大極小分析法是在二人博弈中，為了使己方獲勝而采用的分析方法。基本思想如下：（1）為博弈雙方中的一方尋找一個最優行動方案。（2）要考慮每一方案實施后對方可能采取的所有行動，并計算可能的得分。（3）為計算得分，需要定義一個估價函數，用來估算當前博弈樹端節點的得分（靜態估算值）。（4）由端節點的得分估算父節點的得分（倒推值）：對或節點，選子節點中最大的得分給父節點；對與節點，選子節點中最小的得分給父節點。（5）如果一個行動方案能獲得較大的倒推值，則它就是當前最好的方案。極大極小分析法面臨的問題試圖用完整的博弈樹來進行極大極小分析是困難的。可行的方法：生成一定深度的博弈樹，而后進行極大極小分析法，找出當前最好的方案。此后再在已經選定的分支上擴展一定深度，再選最好的方案。如此進行下去，直到取得勝敗的結果為止。5.3.3α–β剪枝技術在極大極小分析法中，總是先生成一定深度的博弈樹，對端節點進行估值，然后計算上層節點的倒推值。這樣做效率并不高。鑒于博弈樹具有或節點和與節點交替出現的特點，如果能夠邊生成節點邊估值，就有可能刪去一些不必要的節點。剪枝技術就是基于此提出的。通過邊生成節點邊計算估值，從而刪去某些分枝的技術稱為α–β剪枝技術。與節點取當前子節點中的最小倒推值最為它倒推值的上界，稱為β值；或節點取當前子節點中的最大倒推值最為它倒推值的下界，稱為α值。α–β剪枝技術53BS023S1S3S4S5S6S2例：圖中S6尚未計算估值則：由α–β剪枝技術可知，S6形成的分枝