人工智能導(dǎo)論-第1章

第一章搜索問(wèn)題內(nèi)容： 狀態(tài)空間的搜索問(wèn)題。搜索方式：盲目搜索啟發(fā)式搜索關(guān)鍵問(wèn)題： 如何利用知識(shí)，盡可能有效地找到問(wèn)題的解（最佳解）。1搜索問(wèn)題（續(xù)1）S0Sg2搜索問(wèn)題（續(xù)2）討論的問(wèn)題：有哪些常用的搜索算法。問(wèn)題有解時(shí)能否找到解。找到的解是最佳的嗎？什么情況下可以找到最佳解？求解的效率如何。31.1回溯策略例：皇后問(wèn)題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é)點(diǎn)，CLOSED表用于存放將要擴(kuò)展或者已經(jīng)擴(kuò)展的節(jié)點(diǎn)。狀態(tài)節(jié)點(diǎn)父節(jié)點(diǎn)編號(hào)狀態(tài)節(jié)點(diǎn)父節(jié)點(diǎn)18一般回溯搜索算法1. 把初始節(jié)點(diǎn)S0放入OPEN表，并建立目前只包含S0的圖，記為G;2. 檢查OPEN表是否為空，若為空則問(wèn)題無(wú)解，退出;3. 把OPEN表的第一個(gè)節(jié)點(diǎn)取出放入CLOSED表，并記該節(jié)點(diǎn)為節(jié)點(diǎn)n;4.考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)，若是，則求得了問(wèn)題的解，退出;5. 擴(kuò)展節(jié)點(diǎn)n，生成一組子節(jié)點(diǎn)。把其中不是節(jié)點(diǎn)n先輩的那些子節(jié)點(diǎn)記作集合M，并把這些子節(jié)點(diǎn)作為節(jié)點(diǎn)n的子節(jié)點(diǎn)加入G中;6. 針對(duì)M中子節(jié)點(diǎn)的不同情況，分別進(jìn)行如下處理：19一般回溯搜索算法（續(xù)）6.1對(duì)于那些未曾在G中出現(xiàn)過(guò)的M成員設(shè)置一個(gè)指向父節(jié)點(diǎn)（即節(jié)點(diǎn)n）的指針，并把它們放入OPEN表。6.2對(duì)于那些先前已經(jīng)在G中出現(xiàn)過(guò)的M成員，確定是否需要修改它指向父節(jié)點(diǎn)的指針。6.3對(duì)于那些先前已經(jīng)在G中出現(xiàn)并且已經(jīng)擴(kuò)展了的M成員，確定是否需要修改其后繼節(jié)點(diǎn)指向父節(jié)點(diǎn)的指針。7.按某種搜索策略對(duì)OPEN表中的節(jié)點(diǎn)進(jìn)行排序。8.轉(zhuǎn)第2步。20存在問(wèn)題及解決辦法解決辦法：對(duì)搜索深度加以限制記錄從初始狀態(tài)到當(dāng)前狀態(tài)的路徑當(dāng)前狀態(tài)問(wèn)題：深度問(wèn)題死循環(huán)問(wèn)題21一些深入的問(wèn)題失敗原因分析、多步回溯QQ22一些深入問(wèn)題（續(xù)）回溯搜索中知識(shí)的利用 基本思想(以皇后問(wèn)題為例)： 盡可能選取劃去對(duì)角線上位置數(shù)最少的。QQQQ3223231.2圖搜索策略問(wèn)題的引出回溯搜索：只保留從初始狀態(tài)到當(dāng)前狀態(tài)的一條路徑。圖搜索：保留所有已經(jīng)搜索過(guò)的路徑。

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

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

51238476

53728314765231847652831476528314765283164750542283164752831647528163754

283167542831675428163754

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

283641752831675412384765283167542816375483264175283641752831457628315746

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

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

f(n)=g(n)+h(n) f(n)：評(píng)價(jià)函數(shù)

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

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

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

283164751238476555h計(jì)算舉例 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)目標(biāo)123456572最佳圖搜索算法A*（A*算法）如果使一般搜索過(guò)程滿(mǎn)足如下條件，則它成為A*算法：1.把OPEN表中的節(jié)點(diǎn)按估價(jià)函數(shù)：f(x)=g(x)+h(x)

的值從小到大進(jìn)行排序（一般搜索過(guò)程的第7步）2.g(x)是對(duì)g*(x)的估計(jì)，g(x)>0.3.h(x)是對(duì)h*(x)的下界，即對(duì)所有的x均有：

h(x)≤h*(x)

其中g(shù)*(x)是從初始節(jié)點(diǎn)S0到節(jié)點(diǎn)x的最小代價(jià)；h*(x)是從節(jié)點(diǎn)x到目標(biāo)節(jié)點(diǎn)的最小代價(jià)，若有多個(gè)目標(biāo)節(jié)點(diǎn)，則為其中的最小值。58A*條件舉例8數(shù)碼問(wèn)題h1(n)=“不在位”的將牌數(shù)h2(n)=將牌“不在位”的距離和2

831

64751234576

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

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

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

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

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

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

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

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

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

擴(kuò)展時(shí)引理的結(jié)論是正確的，現(xiàn)在證明在節(jié)點(diǎn)(m+1)擴(kuò)展時(shí)引理是正確的。63A*算法的性質(zhì)（續(xù)4）設(shè)n是m個(gè)節(jié)點(diǎn)擴(kuò)展后，A*發(fā)現(xiàn)的一個(gè)最佳路徑上的假設(shè)節(jié)點(diǎn)，它在OPEN上。如果在第（m+1）步，n沒(méi)有被選擇擴(kuò)展，n的屬性和以前相同，因此證明了歸納步驟。如果n被選為擴(kuò)展點(diǎn)，它的所有后繼將被放在OPEN上，他們中至少有一個(gè)np，將會(huì)在到達(dá)目標(biāo)的最優(yōu)路徑上（因?yàn)橛捎诩俣ㄒ粋€(gè)最優(yōu)路徑通過(guò)n，它必須通過(guò)它的一個(gè)后繼）。故A*找到了到達(dá)np的一條最佳路徑，因?yàn)槿绻械竭_(dá)np的一條更好路徑，那么這條路徑也是到達(dá)目標(biāo)的更好路徑（這和我們的假設(shè)沒(méi)有比通過(guò)n到達(dá)目標(biāo)的路徑更好的路徑相矛盾）。這樣，我們讓np稱(chēng)為第m+1步新的n。現(xiàn)在證明f(np)f*(s).

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

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

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

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

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

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

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

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

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

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

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

或

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

則稱(chēng)h服從一致性條件。h(ni)ninjh(nj)c(ni,nj)74h單調(diào)的性質(zhì)一致性條件的性質(zhì)：設(shè)ni和nj是由A*在搜索樹(shù)上產(chǎn)生的兩個(gè)節(jié)點(diǎn)，nj是ni的后繼。如果滿(mǎn)足一致性條件，就有f(nj)f(ni)。證明：因?yàn)閔(nj)h(ni)-c(ni,nj)，所以h(nj)+g(nj)h(ni)+g(nj)-c(ni,nj)。但是g(nj)=g(ni)+c(ni,nj)（我們可能會(huì)擔(dān)心g(nj)會(huì)比這個(gè)值小，因?yàn)槲覀兛赡軙?huì)順著其它的比通過(guò)ni點(diǎn)代價(jià)更低的路徑到達(dá)nj。但這樣一來(lái)，在搜索樹(shù)上nj就不是ni的后繼了）。因此，f(nj)f(ni)。因?yàn)檫@個(gè)原因，一致性條件（對(duì)h）也常稱(chēng)為單調(diào)條件（對(duì)f）。75定理1.5： 若h(n)是滿(mǎn)足一致性條件，則A*擴(kuò)展了節(jié)點(diǎn)n之后，就已經(jīng)找到了到達(dá)節(jié)點(diǎn)n的最佳路徑。 即：當(dāng)A*選n擴(kuò)展時(shí)，有g(shù)(n)=g*(n)。76定理1.5的證明證明：假設(shè)A*在隱式圖G中正在搜索從開(kāi)始節(jié)點(diǎn)n0到目標(biāo)節(jié)點(diǎn)的一條最佳路徑，它準(zhǔn)備擴(kuò)展一個(gè)打開(kāi)的節(jié)點(diǎn)n。設(shè)＝(n0,n1,…,nm,nm+1,…,n=nk)是圖G中從n0到n的一條最佳路徑的節(jié)點(diǎn)序列，nm是被A*擴(kuò)展的最后一個(gè)節(jié)點(diǎn)（注意中一定存在這樣的節(jié)點(diǎn)，至少n0就是在中）。因?yàn)閚m是上最后一個(gè)沒(méi)打開(kāi)的節(jié)點(diǎn)，因此nm+1在OPEN上是一個(gè)擴(kuò)展候選者