第03章搜索推理技術(shù)

三、搜索推理技術(shù)1.搜索的概念和種類2.圖搜索策略3.盲目搜索4.啟發(fā)式搜索

概述搜索是人工智能的一個(gè)基本問題，是推理不可分割的一部分；搜索是求解問題的一種方法；為了利用搜索的方法求解問題，首先必須將被求解的問題用某種形式表示出來

3.1.搜索的概念和種類

搜索根據(jù)問題的實(shí)際情況，按照一定的策略或規(guī)則，從知識庫中尋找可利用的知識，從而構(gòu)造出一條使問題獲得解決的推理路線的過程。含義從初始事實(shí)到問題答案的一條推理路線；找到的這條路線是時(shí)間和空間復(fù)雜度最小的求解路線。搜索的概念

盲目搜索（無信息搜索）：在搜索過程中，只按照預(yù)定的搜索控制策略進(jìn)行搜索，而沒有任何中間信息來改變這些控制策略。搜索帶有盲目性，效率不高，如果遇到比較復(fù)雜的問題，其求解的效率可能就相當(dāng)?shù)?。用于解決比較簡單的問題。搜索的種類

啟發(fā)式搜索（有信息搜索）：在搜索求解過程中，根據(jù)問題本身的特性或搜索過程中產(chǎn)生的一些信息來不斷地改變或調(diào)整搜索的方向，使搜索朝著最有希望的方向前進(jìn)，加速問題的求解，并找到最優(yōu)解。雖然啟發(fā)式搜索由于考慮到問題本身的特性并利用這些特性，從而使搜索求解的效率更高，更易于求解復(fù)雜的問題，然而并不是對所有的問題都能方便地抽取問題的有關(guān)特性和信息，因此盡管啟發(fā)式搜索好于盲目搜索，但盲目搜索也會在很多問題的求解中得到應(yīng)用。搜索的種類

3.2.圖搜索策略

什么是狀態(tài)空間圖？使用圖示的方式用狀態(tài)空間圖對一個(gè)問題進(jìn)行描述的方法。狀態(tài)空間圖是一個(gè)有向圖。當(dāng)把一個(gè)待求解的問題表示為狀態(tài)空間以后，就可以通過對狀態(tài)空間的搜索，實(shí)現(xiàn)對問題的求解。如果從狀態(tài)空間的角度來看，則對問題的求解就相當(dāng)于在有向圖上尋找一條從某一節(jié)點(diǎn)（初始狀態(tài)節(jié)點(diǎn)）到另一節(jié)點(diǎn)（目標(biāo)節(jié)點(diǎn)）的路徑。3.2.圖搜索策略（1）

若要把表示問題的整個(gè)狀態(tài)空間都存入計(jì)算機(jī)，往往需要占據(jù)巨大的存儲空間，尤其對比較復(fù)雜的問題，這幾乎是不能實(shí)現(xiàn)的。并且一般也無這種必要。因?yàn)閷τ谝粋€(gè)具體的問題，其解往往只與狀態(tài)空間的一部分相關(guān)，只要計(jì)算機(jī)生成并存儲與問題有關(guān)的解狀態(tài)空間部分，即可將問題解決。如何來生成并存儲與問題有關(guān)的部分狀態(tài)空間？

3.2.圖搜索策略（2）

求解的基本思想（1）將問題的初始狀態(tài)（狀態(tài)空間圖中的初始節(jié)點(diǎn)）當(dāng)作當(dāng)前節(jié)點(diǎn)，選擇一適當(dāng)?shù)乃惴饔糜诋?dāng)前狀態(tài)，生成一組后繼狀態(tài)（或后繼節(jié)點(diǎn)）。（2）檢查這組后繼狀態(tài)中有沒有目標(biāo)狀態(tài)，如果有，則說明搜索成功，從初始狀態(tài)到目標(biāo)狀態(tài)的一系列算符即是問題的解。（3）若沒有，則按照某種控制策略從已生成的狀態(tài)中再選擇一個(gè)狀態(tài)作為當(dāng)前狀態(tài)。（4）重復(fù)上述過程，直到目標(biāo)狀態(tài)出現(xiàn)或不再有可供操作的狀態(tài)及算符時(shí)為止。3.2.圖搜索策略（3）

狀態(tài)空間圖是由節(jié)點(diǎn)和分支構(gòu)成的集合。節(jié)點(diǎn)數(shù)目有限的狀態(tài)空間圖被稱為有限節(jié)點(diǎn)圖。一個(gè)分支連接兩個(gè)節(jié)點(diǎn)，其中有方向的分支稱為有向分支，沒有方向的稱為無向分支。當(dāng)存在從節(jié)點(diǎn)N1到節(jié)點(diǎn)N2的路徑時(shí)，節(jié)點(diǎn)N1被稱為節(jié)點(diǎn)N2的父節(jié)點(diǎn)；節(jié)點(diǎn)N2被稱為節(jié)點(diǎn)N1的子節(jié)點(diǎn)。如果從N1到N2的路徑只有一條的時(shí)候，而且兩端的節(jié)點(diǎn)相同，則這種路徑稱為閉路。3.2.圖搜索策略（4）

3.2.圖搜索策略（5）

已擴(kuò)展節(jié)點(diǎn)用適合的算符對某個(gè)節(jié)點(diǎn)進(jìn)行操作生成一組后繼節(jié)點(diǎn)，擴(kuò)展過程實(shí)際上就是求后繼節(jié)點(diǎn)的過程。所以，對狀態(tài)空間圖的某個(gè)節(jié)點(diǎn)，如果求出了它的后繼節(jié)點(diǎn)，則此節(jié)點(diǎn)為已擴(kuò)展的節(jié)點(diǎn)，而尚未求出它的后繼節(jié)點(diǎn)的節(jié)點(diǎn)稱為未擴(kuò)展節(jié)點(diǎn)。狀態(tài)節(jié)點(diǎn)父節(jié)點(diǎn)未擴(kuò)展OPEN表編號狀態(tài)節(jié)點(diǎn)父節(jié)點(diǎn)擴(kuò)展CLOSED表

3.2.圖搜索策略（6）

狀態(tài)空間的搜索算法如下：（1）建立一個(gè)只含有初始節(jié)點(diǎn)S的搜索圖G,把S放入OPEN表中。（2）建立CLOSED表，且置為空表。（3）LOOP:若OPEN表是空表，則失敗退出。（4）選擇OPEN表上的第一個(gè)節(jié)點(diǎn)，把它從OPEN表移出并放進(jìn)CLOSED表中，稱此節(jié)點(diǎn)為節(jié)點(diǎn)n。（5）若n為一目標(biāo)節(jié)點(diǎn)，則有解并成功退出，此解是追蹤圖G中沿著指針從n到S這條路徑而得到的。（6）擴(kuò)展節(jié)點(diǎn)n，同時(shí)生成不是n的祖先的那些后繼節(jié)點(diǎn)的集合M。把M的這些成員作為n的后繼節(jié)點(diǎn)添入圖G中。（7）對那些未曾在G中出現(xiàn)過的，M成員設(shè)置一個(gè)通向n的指針，把M的這些成員加進(jìn)OPEN表。對已經(jīng)在OPEN或CLOSED表上的每一個(gè)M成員，確定是否需要更改通到n的指針方向。對已在CLOSED表上的每個(gè)M成員，確定是否需要更改圖G中通向它的每個(gè)后裔節(jié)點(diǎn)的指針方向。（8）按某一任意方式或按某個(gè)試探值，重排OPEN表。（9）GOLOOP

3.2.圖搜索策略（7）開始節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)失敗退出YN根據(jù)后入先出或先入先出的原則從Open表中選擇一個(gè)節(jié)點(diǎn)，并置為n將n的子節(jié)點(diǎn)中未包含在Closed表中的節(jié)點(diǎn)加入Open表中Open表是否空成功退出YN將初始節(jié)點(diǎn)加入Open表Closed表置空

3.2.圖搜索策略（8）

各種搜索策略的主要區(qū)別第（8）步對OPEN表中的節(jié)點(diǎn)排序的算法不同。在（8）中對OPEN表中的節(jié)點(diǎn)排序時(shí)，主要希望從未擴(kuò)展的節(jié)點(diǎn)中選出一個(gè)最有希望的節(jié)點(diǎn)作為第（4）不擴(kuò)展來用。若這時(shí)的排序是任意的或者盲目的，則搜索即為盲目搜索，按照某種啟發(fā)信息或準(zhǔn)則進(jìn)行排序，則其就是啟發(fā)式搜索。在搜索過程中，生成一個(gè)圖G，它是問題狀態(tài)空間圖的一部分，稱為搜索圖。

3.3盲目搜索

無信息搜索或盲目搜索無需重新安排OPEN表的搜索。（1）寬度優(yōu)先搜索(breadth-firstsearch)；（2）深度優(yōu)先搜索(depth-firstsearch)；（3）等代價(jià)搜索(equal-costsearch)。3.3盲目搜索（1）

寬度優(yōu)先搜索如果搜索是以接近起始節(jié)點(diǎn)的程度來依次擴(kuò)展節(jié)點(diǎn)。3.3盲目搜索（2）SOLMQRPV

搜索是逐層進(jìn)行的，在對下一層的任意節(jié)點(diǎn)進(jìn)行搜索之前，必須搜索完本層的所有節(jié)點(diǎn)。

3.3寬度優(yōu)先搜索（3）

寬度優(yōu)先搜索算法如下：（1）把初始節(jié)點(diǎn)放到OPEN表中（如果起始節(jié)點(diǎn)為一目標(biāo)節(jié)點(diǎn)，則求得一個(gè)解答）。（2）如果OPEN是一個(gè)空表，則沒有解，失敗退出；否則繼續(xù)。（3）把第一個(gè)節(jié)點(diǎn)從OPEN表移出，并放進(jìn)CLOSED表中，稱此節(jié)點(diǎn)為節(jié)點(diǎn)n。（4）擴(kuò)展節(jié)點(diǎn)n。如果沒有后繼節(jié)點(diǎn)，則轉(zhuǎn)向步驟(2)。（5）把n的所有后繼節(jié)點(diǎn)放到OPEN表的末端，并提供從這些后繼節(jié)點(diǎn)回到n的指針。（6）如果n的任意節(jié)點(diǎn)是個(gè)目標(biāo)節(jié)點(diǎn)，則找到一個(gè)解答，成功退出；否則轉(zhuǎn)向步驟(2)。

3.3寬度優(yōu)先搜索（4）開始是否有任何后繼節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn)失敗退出YN把第一個(gè)節(jié)點(diǎn)n從OPEN表中移出，并把它放入CLOSED表中擴(kuò)展n，把它的后繼節(jié)點(diǎn)放到OPEN表的末端，提供回到n的指針Open表是否空成功退出YN把S放入OPEN表

例：八數(shù)碼難題：設(shè)在33的一個(gè)方格模盤上，擺放著8個(gè)數(shù)碼1、2、3、4、5、6、7、8，有一個(gè)方格是空格，其初始狀態(tài)和目標(biāo)狀態(tài)如圖，要求對空格執(zhí)行下列的操作（或算符）：空格左移，空格上移，空格右移，空格下移。要求尋找從初始狀態(tài)到目標(biāo)狀態(tài)的路徑。3.3寬度優(yōu)先搜索（5）834765初始狀態(tài)S012384765目標(biāo)狀態(tài)Sg2831407655283147651S02831647054283014765220318476532837140657083214765623018476590231847658283164750112831640751028014376512283145760132837146051580321476514234180765171230847651628316075419283064175182081437652028314570621813204765238302147652228371465025283704615241238047652712378406526Sg

深度優(yōu)先搜索3.3盲目搜索（7）SOLMNQPR

先擴(kuò)展最新產(chǎn)生的節(jié)點(diǎn)，深度相等的節(jié)點(diǎn)可以任意排列。為了避免考慮太長的路徑，往往給出一個(gè)節(jié)點(diǎn)擴(kuò)展的最大深度——深度界限。達(dá)到深度界限，認(rèn)為沒有后繼節(jié)點(diǎn)。

4.3盲目搜索（8）

深度有界的深度優(yōu)先搜索算法如下：（1）把初始節(jié)點(diǎn)放到OPEN表中（如果起始節(jié)點(diǎn)為一目標(biāo)節(jié)點(diǎn)，則求得一個(gè)解答）。（2）如果OPEN是一個(gè)空表，則沒有解，失敗退出；否則繼續(xù)。（3）把第一個(gè)節(jié)點(diǎn)（節(jié)點(diǎn)n）從OPEN表移到CLOSED表中。（4）如果節(jié)點(diǎn)n的深度等于最大深度，則轉(zhuǎn)向步驟(2)。（5）擴(kuò)展節(jié)點(diǎn)n，產(chǎn)生其全部后裔，并把它們放入到OPEN表的前頭。如果沒有后裔，則轉(zhuǎn)向步驟(2)。（6）如果n的任意節(jié)點(diǎn)是個(gè)目標(biāo)節(jié)點(diǎn)，則找到一個(gè)解答，成功退出；否則轉(zhuǎn)向步驟(2)。

3.3盲目搜索（9）

代價(jià)樹的寬度優(yōu)先搜索在實(shí)際問題中，從一個(gè)狀態(tài)變換成另一個(gè)狀態(tài)所付出的操作代價(jià)是不一樣的。問題：采用何種搜索策略，以保證付出的代價(jià)（或費(fèi)用）是最小的。代價(jià)樹：有向邊上標(biāo)有代價(jià)的搜索樹。

3.3盲目搜索（10）

代價(jià)樹的寬度優(yōu)先搜索

記號：(1)起始節(jié)點(diǎn)記為S;(2)從節(jié)點(diǎn)i到它的后繼節(jié)點(diǎn)j的代價(jià)記為c(i,j);(3)從起始節(jié)點(diǎn)S到任一節(jié)點(diǎn)i的路徑代價(jià)記為g(i)。

3.3盲目搜索（10）例推銷員旅行問題假設(shè)A、B、C、D、E是五個(gè)城市，推銷員從城市A出發(fā)，到達(dá)城市E，走怎樣的路線費(fèi)用最??？ACBDE7657864.4啟發(fā)式搜索（1）盲目搜索的特點(diǎn)：搜索線路是事先決定好的，沒有利用被求解問題的任何信息。在決定要被擴(kuò)展的節(jié)點(diǎn)時(shí)，沒有考慮節(jié)點(diǎn)是否可能出現(xiàn)在解的路徑上。沒有考慮它是否有利于問題的求解以及所求的解是否為最優(yōu)解。3.4啟發(fā)式搜索（2）盲目搜索的缺點(diǎn)：搜索所需要擴(kuò)展的節(jié)點(diǎn)數(shù)目很大。產(chǎn)生的無用節(jié)點(diǎn)很多，效率很低。3.4啟發(fā)式搜索（3）啟發(fā)式搜索（有信息搜索）：找到一種方法用于排列待擴(kuò)展節(jié)點(diǎn)的順序，即選擇最有希望的節(jié)點(diǎn)加以擴(kuò)展，搜索效率將會大大提高。

heuristicallysearchinformedsearch3.4.1啟發(fā)信息與估價(jià)函數(shù)搜索的關(guān)鍵選擇下一個(gè)要被考察的節(jié)點(diǎn)，不同的選擇方法即是不同的搜索策略。啟發(fā)信息指導(dǎo)搜索過程且與具體問題求解有關(guān)的控制性信息。3.4.1啟發(fā)信息與估價(jià)函數(shù)（2）啟發(fā)信息的種類用于決定要擴(kuò)展的下一個(gè)節(jié)點(diǎn)，以免在寬度優(yōu)先或深度優(yōu)先那樣盲目擴(kuò)展。在擴(kuò)展節(jié)點(diǎn)的過程中，用于決定要生成哪一個(gè)或幾個(gè)后繼節(jié)點(diǎn)，以免盲目的同時(shí)生成所有可能的節(jié)點(diǎn)。用于確定某些應(yīng)該從搜索樹中拋棄或修剪的節(jié)點(diǎn)。3.4.1啟發(fā)信息與估價(jià)函數(shù)（3）估價(jià)函數(shù)構(gòu)造一個(gè)函數(shù)來表示節(jié)點(diǎn)的“希望”程度。估價(jià)函數(shù)的任務(wù)估計(jì)待搜索節(jié)點(diǎn)的重要程度，給它們排定次序。3.4.1啟發(fā)信息與估價(jià)函數(shù)（4）估價(jià)函數(shù)f(x)可以是節(jié)點(diǎn)x處于最佳路徑上的概率。節(jié)點(diǎn)x到目標(biāo)節(jié)點(diǎn)之間的距離。估價(jià)節(jié)點(diǎn)應(yīng)考慮的因素已經(jīng)付出的代價(jià)將要付出的代價(jià)3.4.1啟發(fā)信息與估價(jià)函數(shù)（5）估價(jià)函數(shù)f(x)定義為從初始節(jié)點(diǎn)經(jīng)過節(jié)點(diǎn)x到達(dá)目標(biāo)節(jié)點(diǎn)的最小代價(jià)路徑的代價(jià)估算值。一般形式

f(x)=g(x)+h(x)g(x)從初始節(jié)點(diǎn)S0到節(jié)點(diǎn)x已實(shí)際付出的代價(jià)；h(x)從節(jié)點(diǎn)x到目標(biāo)節(jié)點(diǎn)Sg的最優(yōu)路徑的估價(jià)代價(jià)。3.4.1啟發(fā)信息與估價(jià)函數(shù)（6）啟發(fā)函數(shù)h(x)

搜索的啟發(fā)信息主要由h(x)來體現(xiàn)，g(x)可以根據(jù)已生成的搜索樹計(jì)算得出，而h(x)要依賴于某種經(jīng)驗(yàn)估計(jì)。在f(x)中，g(x)的比重越大，搜索方向傾向于廣度優(yōu)先搜索；

h(x)的比重越大，越傾向于深度優(yōu)先搜索。3.4.1啟發(fā)信息與估價(jià)函數(shù)（7）

搜索的啟發(fā)信息主要由h(x)來體現(xiàn)，g(x)可以根據(jù)已生成的搜索樹計(jì)算得出，而h(x)要依賴于某種經(jīng)驗(yàn)估計(jì)。在f(x)中，g(x)的比重越大，搜索方向傾向于廣度優(yōu)先搜索；h(x)的比重越大，越傾向于深度優(yōu)先搜索。

g(x)<<h(x)時(shí)，可忽略g(x)。這時(shí)，f(x)=h(x)，這會有利于搜索效率的提高，但影響搜索算法的完備性，即有可能找不到問題的解。3.4.2最佳優(yōu)先搜索（1）最佳優(yōu)先搜索（有序搜索、擇優(yōu)搜索）

它總是選擇最有希望的節(jié)點(diǎn)作為下一個(gè)要擴(kuò)展的節(jié)點(diǎn)，而這種最有希望的節(jié)點(diǎn)是按估價(jià)函數(shù)f(x)的值來挑選的，一般估價(jià)函數(shù)的值越小，它的希望程度就越大。分為兩種局部優(yōu)先搜索全局優(yōu)先搜索3.4.2最佳優(yōu)先搜索（2）局部最佳優(yōu)先搜索

類似于深度優(yōu)先搜索法，但由于使用了與問題特性相關(guān)的估價(jià)函數(shù)確定下一個(gè)待擴(kuò)展的節(jié)點(diǎn)，所以它是一種啟發(fā)式搜索方法?；舅枷氘?dāng)對某個(gè)節(jié)點(diǎn)擴(kuò)展之后，對它的每一個(gè)后繼節(jié)點(diǎn)計(jì)算估價(jià)函數(shù)f(x)的值。由于它每次只是在后繼節(jié)點(diǎn)范圍內(nèi)，選擇一個(gè)f(x)的值最小的節(jié)點(diǎn)，作為下一個(gè)要考察的節(jié)點(diǎn)，范圍較小。3.4.2最佳優(yōu)先搜索（3）局部最佳優(yōu)先搜索算法(1)把初始節(jié)點(diǎn)S0放入OPEN表中，并計(jì)算估價(jià)函數(shù)f(S0).(2)如果OPEN為空，則問題無解，退出；否則轉(zhuǎn)(3).(3)從OPEN表中選取第一個(gè)節(jié)點(diǎn)（記為n,其估價(jià)函數(shù)最?。┺D(zhuǎn)入CLOSED表。(4)考察節(jié)點(diǎn)n是否目標(biāo)節(jié)點(diǎn)，若是則求得問題的解，退出；否則轉(zhuǎn)(5)。(5)如果節(jié)點(diǎn)n可擴(kuò)展，轉(zhuǎn)(6)；否則轉(zhuǎn)(2)(6)對節(jié)點(diǎn)n進(jìn)行擴(kuò)展，對它的所有后繼節(jié)點(diǎn)計(jì)算估價(jià)函數(shù)f(x)的值，并按估價(jià)函數(shù)f(x)從小到大的順序依次放入OPEN表的前端。(7)為每個(gè)后繼節(jié)點(diǎn)設(shè)置指向n的指針。(8)轉(zhuǎn)(2)。3.4.2最佳優(yōu)先搜索（4）全局最佳優(yōu)先搜索

類似于寬度優(yōu)先搜索法，但由于使用了與問題特性相關(guān)的估價(jià)函數(shù)確定下一個(gè)待擴(kuò)展的節(jié)點(diǎn)，所以它是一種啟發(fā)式搜索方法?；舅枷氘?dāng)對某個(gè)節(jié)點(diǎn)擴(kuò)展之后，對它的每一個(gè)后繼節(jié)點(diǎn)計(jì)算估價(jià)函數(shù)f(x)的值。由于它每次在OPEN表的全部節(jié)點(diǎn)范圍內(nèi)，選擇一個(gè)f(x)的值最小的節(jié)點(diǎn)，作為下一個(gè)要考察的節(jié)點(diǎn)，范圍較小。3.4.2最佳優(yōu)先搜索（5）全局最佳優(yōu)先搜索算法(1)把初始節(jié)點(diǎn)S0放入OPEN表中，并計(jì)算估價(jià)函數(shù)f(S0).(2)如果OPEN為空，則問題無解，退出；否則轉(zhuǎn)(3).(3)從OPEN表中選取第一個(gè)節(jié)點(diǎn)（記為n,其估價(jià)函數(shù)最?。┺D(zhuǎn)入CLOSED表。(4)考察節(jié)點(diǎn)n是否目標(biāo)節(jié)點(diǎn)，若是則求得問題的解，退出；否則轉(zhuǎn)(5)。(5)如果節(jié)點(diǎn)n可擴(kuò)展，轉(zhuǎn)(6)；否則轉(zhuǎn)(2)(6)對節(jié)點(diǎn)n進(jìn)行擴(kuò)展，對它的所有后繼節(jié)點(diǎn)計(jì)算估價(jià)函數(shù)f(x)的值，為每個(gè)后繼節(jié)點(diǎn)設(shè)置指向n的指針。(7)把這些節(jié)點(diǎn)都送入OPEN表，然后對OPEN表中的全部節(jié)點(diǎn)按照估價(jià)值從小到大順序排序。(8)轉(zhuǎn)(2)。3.4.2最佳優(yōu)先搜索（6）例:用全局最佳優(yōu)先搜索方法求解八數(shù)碼難題。203184765S0123804765Sg3.4.3A*算法（1）A*算法的定義

它選用了一個(gè)比較特殊的估價(jià)函數(shù)。這時(shí)的估價(jià)函數(shù)是下列估價(jià)函數(shù)

f*(x)=g*(x)+h*(x)的一種估計(jì)或近似。f(x)是對f*(x)的一種估算；g(x)是對g*(x)的一種估算；h(x)是對h*(x)的一種估算.3.4.3A*算法（2）

f*(x):表示從節(jié)點(diǎn)S0到節(jié)點(diǎn)x的一條最佳路徑的實(shí)際代價(jià)加上從節(jié)點(diǎn)x到目標(biāo)節(jié)點(diǎn)的一條最佳路徑的代價(jià)之和。

g*(x)表示從節(jié)點(diǎn)S0到節(jié)點(diǎn)x的一條最佳路徑的實(shí)際代價(jià)。

h*(x)表示從節(jié)點(diǎn)x到目標(biāo)節(jié)點(diǎn)的一條最佳路徑的代價(jià)。3.4.3A*算法（3）A*算法定義

如果在一般狀態(tài)空間圖的搜索算法中的第8步，依據(jù)估價(jià)函數(shù)

f(x)=g(x)+h(x)對OPEN表中的節(jié)點(diǎn)進(jìn)行排序，并且要求啟發(fā)函數(shù)h(x)是h*(x)的一個(gè)下界，即h(x)<=h*(x).A算法：沒有限制。3.4.3A*算法（4）A*算法實(shí)例

假設(shè)某個(gè)人要從A點(diǎn)到達(dá)B點(diǎn)，而一堵墻把這兩個(gè)點(diǎn)隔開了，如下圖所示，綠色部分代表起點(diǎn)A，紅色部分代表終點(diǎn)B，藍(lán)色方塊部分代表之間的墻。3.4.3A*算法（5）A*算法實(shí)例

G＝從起點(diǎn)A沿著已生成的路徑到一個(gè)給定方格的移動(dòng)開銷。

H＝從給定方格到目的方格的估計(jì)移動(dòng)開銷。3.4.3A*算法（6）A*算法實(shí)例

3.4.3A*算法（7）A*算法實(shí)例

3.4.3A*算法（8）A*算法實(shí)例

3.4.3A*算法（9）A*算法

1.將