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

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

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

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

51238476

53728314765231847652831476528314765283164750542283164752831647528163754

283167542831675428163754

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

283641752831675412384765283167542816375483264175283641752831457628315746

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

2836417528316754813247658321476528371465283746151238476535876910111220191817161514132322212424廣度(寬度)優(yōu)先搜索44寬度優(yōu)先搜索的性質(zhì)當(dāng)問題有解時，一定能找到解當(dāng)問題為單位耗散值，且問題有解時，一定能找到最優(yōu)解方法與問題無關(guān)，具有通用性效率較低屬于圖搜索方法451.4啟發(fā)式圖搜索利用知識來引導(dǎo)搜索，達(dá)到減少搜索范圍，降低問題復(fù)雜度的目的。啟發(fā)信息的強(qiáng)度強(qiáng)：降低搜索工作量，但可能導(dǎo)致找不到最 優(yōu)解弱：一般導(dǎo)致工作量加大，極限情況下變?yōu)?盲目搜索，但可能可以找到最優(yōu)解46希望：引入啟發(fā)知識，在保證找到最佳解的情況下，盡可能減少搜索范圍，提高搜索效率。47基本思想定義一個評價函數(shù)f，對當(dāng)前的搜索狀態(tài)進(jìn)行評估，找出一個最有希望的節(jié)點來擴(kuò)展。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經(jīng)過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是否為目標(biāo)節(jié)點，若是，則求得了問題的解，退出;5,若節(jié)點n不可擴(kuò)展，則轉(zhuǎn)第2步;6,擴(kuò)展節(jié)點n，用估價函數(shù)f(x)計算每個子節(jié)點的估價值，并按估價值從小到大的順序依次放到OPEN表的首部，為每個子節(jié)點配置指向父節(jié)點的指針，然后轉(zhuǎn)第2步。51局部擇優(yōu)搜索與深度優(yōu)先搜索的關(guān)系深度優(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是否為目標(biāo)節(jié)點，若是，則求得了問題的解，退出;5,若節(jié)點n不可擴(kuò)展，則轉(zhuǎn)第2步;6,擴(kuò)展節(jié)點n，用估價函數(shù)f(x)計算每個子節(jié)點的估價值，并為每個子節(jié)點配置指向父節(jié)點的指針，把這些子節(jié)點都送入OPEN表中，然后對OPEN表中的全部節(jié)點按估價值從小到大的順序進(jìn)行排序7,轉(zhuǎn)第2步。53全局擇優(yōu)搜索與廣度優(yōu)先搜索的關(guān)系在全局擇優(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é)點到當(dāng)前節(jié)點的耗散值

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

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

h(x)≤h*(x)

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

831

64751234576

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

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

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

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

證明：對任意節(jié)點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： 對有限圖，如果從初始節(jié)點s到目標(biāo)節(jié)點t有路徑存在，則算法A一定成功結(jié)束。61A*算法的性質(zhì)（續(xù)2）引理1.1

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

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

因為對在一條最佳路徑上的節(jié)點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： 對無限圖，若從初始節(jié)點s到目標(biāo)節(jié)點t有路徑存在，則A*一定成功結(jié)束。證明：由引理1.1，則OPEN中所有的n有f(n)>f*(s)。由引理1.2，在A*結(jié)束前OPEN表中必存在節(jié)點n，使得f(n)f*(s)。所以如果不結(jié)束，將導(dǎo)致矛盾。65A*算法的性質(zhì)（續(xù)6）推論1.1：

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

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

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

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

設(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è)對同一個問題定義了兩個A*算法A1和A2，若A2比A1有較多的啟發(fā)信息，即對所有非目標(biāo)節(jié)點有h2(n)>h1(n)，則在具有一條從s到t的路徑的隱含圖上，搜索結(jié)束時，由A2所擴(kuò)展的每一個節(jié)點，也必定由A1所擴(kuò)展，即A1擴(kuò)展的節(jié)點數(shù)至少和A2一樣多。簡寫：如果h2(n)>h1(n)(目標(biāo)節(jié)點除外)，則A1擴(kuò)展的節(jié)點數(shù)≥A2擴(kuò)展的節(jié)點數(shù)70A*算法的性質(zhì)（續(xù)11）注意：

在定理1.4中，評價指標(biāo)是“擴(kuò)展的節(jié)點數(shù)”，也就是說，同一個節(jié)點無論被擴(kuò)展多少次，都只計算一次。71定理1.4的證明（續(xù)12）使用數(shù)學(xué)歸納法，對節(jié)點的深度進(jìn)行歸納（1）當(dāng)d(n)＝0時，即只有一個節(jié)點，顯然定理成立。（2）設(shè)d(n)≤k時定理成立。（歸納假設(shè)）（3）當(dāng)d(n)=k+1時，用反證法。設(shè)存在一個深度為k＋1的節(jié)點n，被A2擴(kuò)展，但沒有被A1擴(kuò)展。而由假設(shè)，A1擴(kuò)展了n的父節(jié)點，即n已經(jīng)被生成了。因此當(dāng)A1結(jié)束時，n將被保留在OPEN中。72定理1.4的證明（續(xù)1）因為A1沒有擴(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時，A2擴(kuò)展的節(jié)點A1一定擴(kuò)展，有

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