人工智能導論-第1章

第一章搜索問題內容： 狀態(tài)空間的搜索問題。搜索方式：盲目搜索啟發(fā)式搜索關鍵問題： 如何利用知識，盡可能有效地找到問題的解（最佳解）。1搜索問題（續(xù)1）S0Sg2搜索問題（續(xù)2）討論的問題：有哪些常用的搜索算法。問題有解時能否找到解。找到的解是最佳的嗎？什么情況下可以找到最佳解？求解的效率如何。31.1回溯策略例：皇后問題4()5()Q((1,1))6()QQ((1,1))((1,1)(2,3))7()Q((1,1))((1,1)(2,3))8()QQ((1,1))((1,1)(2,3))((1,1)(2,4))9()QQ((1,1))((1,1)(2,3))((1,1)(2,4))Q((1,1)(2,4)(3.2))10()QQ((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))11()Q((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))12()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))13()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))14()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))Q((1,2)(2,4))15()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))Q((1,2)(2,4))Q((1,2)(2,4)(3,1))16()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))Q((1,2)(2,4))Q((1,2)(2,4)(3,1))Q((1,2)(2,4)(3,1)(4,3))17回溯搜索算法

OPEN表CLOSED表

OPEN表用于存放剛生成的節(jié)點，CLOSED表用于存放將要擴展或者已經擴展的節(jié)點。狀態(tài)節(jié)點父節(jié)點編號狀態(tài)節(jié)點父節(jié)點18一般回溯搜索算法1. 把初始節(jié)點S0放入OPEN表，并建立目前只包含S0的圖，記為G;2. 檢查OPEN表是否為空，若為空則問題無解，退出;3. 把OPEN表的第一個節(jié)點取出放入CLOSED表，并記該節(jié)點為節(jié)點n;4.考察節(jié)點n是否為目標節(jié)點，若是，則求得了問題的解，退出;5. 擴展節(jié)點n，生成一組子節(jié)點。把其中不是節(jié)點n先輩的那些子節(jié)點記作集合M，并把這些子節(jié)點作為節(jié)點n的子節(jié)點加入G中;6. 針對M中子節(jié)點的不同情況，分別進行如下處理：19一般回溯搜索算法（續(xù)）6.1對于那些未曾在G中出現(xiàn)過的M成員設置一個指向父節(jié)點（即節(jié)點n）的指針，并把它們放入OPEN表。6.2對于那些先前已經在G中出現(xiàn)過的M成員，確定是否需要修改它指向父節(jié)點的指針。6.3對于那些先前已經在G中出現(xiàn)并且已經擴展了的M成員，確定是否需要修改其后繼節(jié)點指向父節(jié)點的指針。7.按某種搜索策略對OPEN表中的節(jié)點進行排序。8.轉第2步。20存在問題及解決辦法解決辦法：對搜索深度加以限制記錄從初始狀態(tài)到當前狀態(tài)的路徑當前狀態(tài)問題：深度問題死循環(huán)問題21一些深入的問題失敗原因分析、多步回溯QQ22一些深入問題（續(xù)）回溯搜索中知識的利用 基本思想(以皇后問題為例)： 盡可能選取劃去對角線上位置數(shù)最少的。QQQQ3223231.2圖搜索策略問題的引出回溯搜索：只保留從初始狀態(tài)到當前狀態(tài)的一條路徑。圖搜索：保留所有已經搜索過的路徑。

24一些基本概念節(jié)點深度： 根節(jié)點深度=0

其它節(jié)點深度=父節(jié)點深度+1012325一些基本概念（續(xù)1）路徑 設一節(jié)點序列為(n0,n1,…,nk)，對于i=1,…,k，若節(jié)點ni-1具有一個后繼節(jié)點ni，則該序列稱為從n0到nk的路徑。路徑的耗散值 一條路徑的耗散值等于連接這條路徑各節(jié)點間所有耗散值的總和。用C(ni,nj)表示從ni到nj的路徑的耗散值。26一些基本概念（續(xù)1）擴展一個節(jié)點 生成出該節(jié)點的所有后繼節(jié)點，并給出它們之間的耗散值。這一過程稱為“擴展一個節(jié)點”。27修改指針舉例123456s28修改指針舉例（續(xù)1）123456s29123456修改指針舉例（續(xù)2）s30123456修改指針舉例（續(xù)3）s311.3無信息圖搜索過程深度優(yōu)先搜索寬度優(yōu)先搜索32深度優(yōu)先搜索1,把初始節(jié)點S0放入OPEN表;2,如果OPEN表為空，則問題無解，退出;3,把OPEN表的第一個節(jié)點（記為節(jié)點n）取出放入CLOSED表;4,考察節(jié)點n是否為目標節(jié)點，若是，則求得了問題的解，退出;5,若節(jié)點n不可擴展，則轉第2步;6,擴展節(jié)點n，將其子節(jié)點放入到OPEN表的首部，并為其配置指向父節(jié)點的指針，然后轉第2步;33有界深度優(yōu)先搜索1,把初始節(jié)點S0放入OPEN表中，置S0的深度d(S0)=0;2,如果OPEN表為空，則問題無解，退出;3,把OPEN表的第一個節(jié)點（記為節(jié)點n）取出放入CLOSED表;4,考察節(jié)點n是否為目標節(jié)點，若是，則求得了問題的解，退出;5,如果節(jié)點n的深度d(節(jié)點n)=dm，則轉第2步；6,若節(jié)點n不可擴展，則轉第2步;7,擴展節(jié)點n，將其子節(jié)點放入到OPEN表的首部，并為其配置指向父節(jié)點的指針，然后轉第2步;34代價樹（圖）在上面的討論中，都沒有考慮搜索的代價問題，當時假設圖中各邊的代價都相同，且都為一個單位量。邊上標有代價（或費用）的樹（圖）稱為代價樹（圖）。在代價樹中，若用g(x)表示從初始節(jié)點S0到節(jié)點x的代價，用c(x1,x2)表示從父節(jié)點x1到節(jié)點x2的代價，則有：g(x2)=g(x1)+c(x1,x2)35代價樹的深度優(yōu)先搜索1,把初始節(jié)點S0放入OPEN表;2,如果OPEN表為空，則問題無解，退出;3,把OPEN表的第一個節(jié)點（記為節(jié)點n）取出放入CLOSED表;4,考察節(jié)點n是否為目標節(jié)點，若是，則求得了問題的解，退出;5,若節(jié)點n不可擴展，則轉第2步;6,擴展節(jié)點n，將其子節(jié)點按邊代價從小到大的順序放到OPEN表的首部，并為各子節(jié)點配置指向父節(jié)點的指針，然后轉第2步;36重排九宮問題2831476

51238476

53728314765231847652831476528314765283164750542283164752831647528163754

283167542831675428163754

31深度優(yōu)先搜索38283147652318476528314765283147652831647502318321476528371465231847652318476528314576281437652831647528316475832147652837146512384765234187652814376528314576

283641752831675412384765283167542816375483264175283641752831457628315746

2814376524813765234187652341857612378465547698101211141316151817201922212325242726有界深度優(yōu)先搜索39深度優(yōu)先搜索的性質一般不能保證找到最優(yōu)解當深度限制不合理時，可能找不到解，可以將算法改為可變深度限制最壞情況時，搜索空間等同于窮舉與回溯法的差別：圖搜索是一個通用的與問題無關的方法40漸進式深度優(yōu)先搜索方法目的解決寬度優(yōu)先方法的空間問題和回溯方法不能找到最優(yōu)解的問題。思想 首先給回溯法一個比較小的深度限制，然后逐漸增加深度限制，直到找到解或找遍所以分支為止。41寬度優(yōu)先搜索1,把初始節(jié)點S0放入OPEN表;2,如果OPEN表為空，則問題無解，退出;3,把OPEN表的第一個節(jié)點（記為節(jié)點n）取出放入CLOSED表中;4,考察節(jié)點n是否為目標節(jié)點，若是，則求得了問題的解，退出;5,若節(jié)點n不可擴展，則轉第2步;6,擴展節(jié)點n，將其子節(jié)點放入OPEN表的尾部，并為每一個子節(jié)點都配置父節(jié)點的指針，然后轉第2步。42代價樹的寬度優(yōu)先搜索1,把初始節(jié)點S0放入OPEN表，令g(S0)=0;2,如果OPEN表為空，則問題無解，退出;3,把OPEN表的第一個節(jié)點（記為節(jié)點n）取出放入CLOSED表中;4,考察節(jié)點n是否為目標節(jié)點，若是，則求得了問題的解，退出;5,若節(jié)點n不可擴展，則轉第2步;6,擴展節(jié)點n，將其子節(jié)點放入OPEN表中，并為其配置父節(jié)點的指針；計算各子節(jié)點的代價，并按各節(jié)點的代價對OPEN表中的全部節(jié)點進行排序（按從小到大的順序），然后轉第2步。43目標283147652318476528314765283147652831647502148321476528371465231847652318476528314576281437652831647528316475832147652837146512384765234187652814376528314576

2836417528316754813247658321476528371465283746151238476535876910111220191817161514132322212424廣度(寬度)優(yōu)先搜索44寬度優(yōu)先搜索的性質當問題有解時，一定能找到解當問題為單位耗散值，且問題有解時，一定能找到最優(yōu)解方法與問題無關，具有通用性效率較低屬于圖搜索方法451.4啟發(fā)式圖搜索利用知識來引導搜索，達到減少搜索范圍，降低問題復雜度的目的。啟發(fā)信息的強度強：降低搜索工作量，但可能導致找不到最 優(yōu)解弱：一般導致工作量加大，極限情況下變?yōu)?盲目搜索，但可能可以找到最優(yōu)解46希望：引入啟發(fā)知識，在保證找到最佳解的情況下，盡可能減少搜索范圍，提高搜索效率。47基本思想定義一個評價函數(shù)f，對當前的搜索狀態(tài)進行評估，找出一個最有希望的節(jié)點來擴展。481，啟發(fā)式搜索算法A（A算法）評價函數(shù)的格式：

f(n)=g(n)+h(n) f(n)：評價函數(shù)

h(n)：啟發(fā)函數(shù)49符號的意義g*(n)：從s到n的最短路徑的耗散值h*(n)：從n到g的最短路徑的耗散值f*(n)=g*(n)+h*(n)：從s經過n到g的最短路徑的耗散值g(n)、h(n)、f(n)分別是g*(n)、h*(n)、f*(n)的估計值50局部擇優(yōu)搜索1,把初始節(jié)點S0放入OPEN表，計算f(S0);2,如果OPEN表為空，則問題無解，退出;3,把OPEN表的第一個節(jié)點（記為節(jié)點n）取出放入CLOSED表;4,考察節(jié)點n是否為目標節(jié)點，若是，則求得了問題的解，退出;5,若節(jié)點n不可擴展，則轉第2步;6,擴展節(jié)點n，用估價函數(shù)f(x)計算每個子節(jié)點的估價值，并按估價值從小到大的順序依次放到OPEN表的首部，為每個子節(jié)點配置指向父節(jié)點的指針，然后轉第2步。51局部擇優(yōu)搜索與深度優(yōu)先搜索的關系深度優(yōu)先搜索、代價樹的深度優(yōu)先搜索以及局部擇優(yōu)搜索都是以子節(jié)點作為考察范圍的。若令f(x)＝g(x)，則局部擇優(yōu)搜索就成為代價樹的深度優(yōu)先搜索；若令f(x)＝d(x)(這里d(x)表示節(jié)點x的深度），則局部擇優(yōu)搜索就成為深度優(yōu)先搜索。所以深度優(yōu)先搜索和代價樹的深度優(yōu)先搜索可看作局部擇優(yōu)搜索的兩個特例。52全局擇優(yōu)搜索1,把初始節(jié)點S0放入OPEN表，計算f(S0);2,如果OPEN表為空，則問題無解，退出;3,把OPEN表的第一個節(jié)點（記為節(jié)點n）取出放入CLOSED表;4,考察節(jié)點n是否為目標節(jié)點，若是，則求得了問題的解，退出;5,若節(jié)點n不可擴展，則轉第2步;6,擴展節(jié)點n，用估價函數(shù)f(x)計算每個子節(jié)點的估價值，并為每個子節(jié)點配置指向父節(jié)點的指針，把這些子節(jié)點都送入OPEN表中，然后對OPEN表中的全部節(jié)點按估價值從小到大的順序進行排序7,轉第2步。53全局擇優(yōu)搜索與廣度優(yōu)先搜索的關系在全局擇優(yōu)搜索中，若令f(x)＝g(x)，則全局擇優(yōu)搜索就成為代價樹的廣度優(yōu)先搜索；若令f(x)＝d(x)(這里d(x)表示節(jié)點x的深度），則全局擇優(yōu)搜索就成為廣度優(yōu)先搜索。所以廣度優(yōu)先搜索和代價樹的廣度優(yōu)先搜索可看作全局擇優(yōu)搜索的兩個特例。54一個A算法的例子定義評價函數(shù)：

f(n)=g(n)+h(n) g(n)為從初始節(jié)點到當前節(jié)點的耗散值

h(n)為當前節(jié)點“不在位”的將牌數(shù)

283164751238476555h計算舉例 h(n)=42

831

64751234576

8562831647528314765283164752831647523184765283147652831476528371465

83214765

2318476523184765123847651238476512378465s(4)A(6)B(4)C(6)D(5)E(5)F(6)G(6)H(7)I(5)J(7)K(5)L(5)M(7)目標123456572最佳圖搜索算法A*（A*算法）如果使一般搜索過程滿足如下條件，則它成為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é)點，則為其中的最小值。58A*條件舉例8數(shù)碼問題h1(n)=“不在位”的將牌數(shù)h2(n)=將牌“不在位”的距離和2

831

64751234576

8將牌1：1將牌2：1將牌6：1將牌8：259A*算法的性質A*算法的假設設ni、nj是任意兩個節(jié)點，有：C(ni,nj)>，其中為大于0的常數(shù)。幾個等式1.f*(s)=f*(t)=h*(s)=g*(t)=f*(n)

其中s是初始節(jié)點，t是目標節(jié)點，n是s到t的最佳路徑上的節(jié)點。2.對于最佳路徑（s,n1,n2,…,

ni,…,t）中的任一節(jié)點ni，均有 f(ni)=f*(s)。3.對于一條到達t的最佳路徑（s,n1,n2,…,

ni,ni+1,…,t），則針對任一節(jié)點ni，路徑（s,n1,n2,…,ni）也是從s到達ni的最佳路徑，即：g*(ni)=g(ni).

證明：對任意節(jié)點ni，若（s,n1,n2,…,

ni）不是到達ni的最佳路徑，即存在路徑（s,n1,n2,…,

ni），使得從s到達ni更近，那么顯然路徑（s,n1,n2,…,ni,ni+1,…,t）也是從s到達t的最佳路徑，這與（s,n1,n2,…,

ni,ni+1,…,t）是從s到達t的最佳路徑矛盾。60A*算法的性質（續(xù)1）定理1.1： 對有限圖，如果從初始節(jié)點s到目標節(jié)點t有路徑存在，則算法A一定成功結束。61A*算法的性質（續(xù)2）引理1.1

： 對無限圖，若有從初始節(jié)點s到目標節(jié)點t的路徑，則A*不結束時，在OPEN表中即使最小的一個f值也將增到任意大，或有f(n)>f*(s)。證明：假設A*不終止。設e是圖中各條邊的最小代價，d*(xn)是從S0到節(jié)點xn的最短路徑長度，則顯然有：g*(xn)d*(xn)×e，又因為g(xn)g*(xn)，所以有g(xn)d*(xn)×e。因為h(xn)0,f(xn)g(xn)，故得到f(xn)d*(xn)×e。由于A*算法不終止，隨著搜索的進行，d*(xn)會無限增大，從而使f(xn)也無限增大。最終使得f(n)>f*(s)。而f*(s)顯然應該是一個有限值，矛盾。62A*算法的性質（續(xù)3）引理1.2：在A*終止前的每一步，總是有一個節(jié)點n，它在OPEN表中，且存在以下屬性：n在最佳路徑上。A*已經發(fā)現(xiàn)了到達n的一條最佳路徑。f(n)≤f*(s)。證明：用歸納法。在搜索開始時，S在OPEN表中，它是到達目標的一條最佳路徑，A*已經發(fā)現(xiàn)了這條路徑，而且因為f(S)=h(S)h*(S)=f*(S).定理成立。假設在節(jié)點m(m0)

擴展時引理的結論是正確的，現(xiàn)在證明在節(jié)點(m+1)擴展時引理是正確的。63A*算法的性質（續(xù)4）設n是m個節(jié)點擴展后，A*發(fā)現(xiàn)的一個最佳路徑上的假設節(jié)點，它在OPEN上。如果在第（m+1）步，n沒有被選擇擴展，n的屬性和以前相同，因此證明了歸納步驟。如果n被選為擴展點，它的所有后繼將被放在OPEN上，他們中至少有一個np，將會在到達目標的最優(yōu)路徑上（因為由于假定一個最優(yōu)路徑通過n，它必須通過它的一個后繼）。故A*找到了到達np的一條最佳路徑，因為如果有到達np的一條更好路徑，那么這條路徑也是到達目標的更好路徑（這和我們的假設沒有比通過n到達目標的路徑更好的路徑相矛盾）。這樣，我們讓np稱為第m+1步新的n?，F(xiàn)在證明f(np)f*(s).

因為對在一條最佳路徑上的節(jié)點np，A*已經找到了到達np的一條最佳路徑，我們有：f(np)=g(np)+h(np)=g*(np)+h(np)≤g*(np)+h*(np)=f*(np)=f*(s)。64A*算法的性質（續(xù)5）定理1.2： 對無限圖，若從初始節(jié)點s到目標節(jié)點t有路徑存在，則A*一定成功結束。證明：由引理1.1，則OPEN中所有的n有f(n)>f*(s)。由引理1.2，在A*結束前OPEN表中必存在節(jié)點n，使得f(n)f*(s)。所以如果不結束，將導致矛盾。65A*算法的性質（續(xù)6）推論1.1：

OPEN表上任一具有f(n)<f*(s)的節(jié)點n，最終都將被A*選作擴展的節(jié)點。證明：由定理1.2知，A*一定結束，由A*的結束條件，OPEN表中f(t)最小時才結束。而f(t)f*(t)=f*(s)。所以，f(n)<f*(s)的n，均被擴展。66A*算法的性質（續(xù)7）定理1.3(可采納性定理)： 若存在從初始節(jié)點s到目標節(jié)點t的路徑，則A*必能找到最佳解結束。67可采納性的證明（續(xù)8）證明：由定理1.1，1.2知，A*一定會找到一個目標節(jié)點結束。設找到一個目標節(jié)點t結束，而s到t不是一條最佳路徑，即：f(t)=g(t)>f*(s).

而根據引理1.2知結束前OPEN表上一定存在有節(jié)點n，且處在最佳路徑上，并有f(n)f*(s)，所以f(n)f*(s)<f(t)。這時算法A*應選n作為當前節(jié)點擴展，不可能選t，從而也不會去測試目標節(jié)點t，即這與假定A*選t結束矛盾，所以A*只能結束在最佳路徑上。68A*算法的性質（續(xù)9）推論1.2：

A*選作擴展的任一節(jié)點n，有f(n)≤f*(s)。

證明：由引理1.2知，在A*結束前，OPEN中存在節(jié)點n，使得f(n)f*(s)。

設此時A*選擇n擴展。如果n=n，則f(n)f*(s)，得證。如果nn，由于A*選擇n擴展，而不是n，所以有f(n)f(n)f*(s)。得證。69A*算法的性質（續(xù)10）定理1.4：設對同一個問題定義了兩個A*算法A1和A2，若A2比A1有較多的啟發(fā)信息，即對所有非目標節(jié)點有h2(n)>h1(n)，則在具有一條從s到t的路徑的隱含圖上，搜索結束時，由A2所擴展的每一個節(jié)點，也必定由A1所擴展，即A1擴展的節(jié)點數(shù)至少和A2一樣多。簡寫：如果h2(n)>h1(n)(目標節(jié)點除外)，則A1擴展的節(jié)點數(shù)≥A2擴展的節(jié)點數(shù)70A*算法的性質（續(xù)11）注意：

在定理1.4中，評價指標是“擴展的節(jié)點數(shù)”，也就是說，同一個節(jié)點無論被擴展多少次，都只計算一次。71定理1.4的證明（續(xù)12）使用數(shù)學歸納法，對節(jié)點的深度進行歸納（1）當d(n)＝0時，即只有一個節(jié)點，顯然定理成立。（2）設d(n)≤k時定理成立。（歸納假設）（3）當d(n)=k+1時，用反證法。設存在一個深度為k＋1的節(jié)點n，被A2擴展，但沒有被A1擴展。而由假設，A1擴展了n的父節(jié)點，即n已經被生成了。因此當A1結束時，n將被保留在OPEN中。72定理1.4的證明（續(xù)1）因為A1沒有擴展n，所以有：f1(n)≥f*(s)(推論1.1)

即：g1(n)+h1(n)≥f*(s)所以：h1(n)≥f*(s)-g1(n)由于A2擴展了n，有f2(n)≤f*(s)（推論1.2）即：h2(n)≤f*(s)–g2(n)

(A)另一方面，由于d(n)=k時，A2擴展的節(jié)點A1一定擴展，有

g1(n)≤g2(n)(因為A2的路A1均走到了)所以：h1(n)≥f*(s)-g1(n)≥f*(s)–g2(n)(B)比較A、B兩式，有h1(n)≥h2(n)，與定理條件矛盾。故定理得證。73對h加以限制定義：一個啟發(fā)函數(shù)h，如果對所有節(jié)點ni和nj，其中nj是ni的子節(jié)點，滿足

h(ni)-h(nj)≤c(ni,nj) h(t)=0

或

h(ni)≤c(ni,nj)+h(nj) h(t)=0

則稱h服從一致性條件。h(ni)ninjh(nj)c(ni,nj)74h單調的性質一致性條件的性質：設ni和nj是由A*在搜索樹上產生的兩個節(jié)點，nj是ni的后繼。如果滿足一致性條件，就有f(nj)f(ni)。證明：因為h(nj)h(ni)-c(ni,nj)，所以h(nj)+g(nj)h(ni)+g(nj)-c(ni,nj)。但是g(nj)=g(ni)+c(ni,nj)（我們可能會擔心g(nj)會比這個值小，因為我們可能會順著其它的比通過ni點代價更低的路徑到達nj。但這樣一來，在搜索樹上nj就不是ni的后繼了）。因此，f(nj)f(ni)。因為這個原因，一致性條件（對h）也常稱為單調條件（對f）。75定理1.5： 若h(n)是滿足一致性條件，則A*擴展了節(jié)點n之后，就已經找到了到達節(jié)點n的最佳路徑。 即：當A*選n擴展時，有g(n)=g*(n)。76定理1.5的證明證明：假設A*在隱式圖G中正在搜索從開始節(jié)點n0到目標節(jié)點的一條最佳路徑，它準備擴展一個打開的節(jié)點n。設＝(n0,n1,…,nm,nm+1,…,n=nk)是圖G中從n0到n的一條最佳路徑的節(jié)點序列，nm是被A*擴展的最后一個節(jié)點（注意中一定存在這樣的節(jié)點，至少n0就是在中）。因為nm是上最后一個沒打開的節(jié)點，因此nm+1在OPEN上是一個擴展候選者