盲目搜索啟發(fā)式搜索

盲目搜索按預(yù)定的控制策略進(jìn)行搜索，在搜索過(guò)程中獲得的中間信息不用來(lái)改進(jìn)控制策略。效率低、主要用于簡(jiǎn)單問(wèn)題求解。啟發(fā)式搜索在搜索中加入了與問(wèn)題有關(guān)的啟發(fā)性信息，用以指導(dǎo)搜索朝著最有希望的方向前進(jìn)，加速問(wèn)題的求解過(guò)程并找到最優(yōu)解。搜索原理什么是搜索？根據(jù)問(wèn)題的實(shí)際情況不斷尋找可利用的知識(shí)，從而構(gòu)造一條代價(jià)較少的推理路線，使問(wèn)題得到圓滿解決的過(guò)程。1與圖有關(guān)的術(shù)語(yǔ)狀態(tài)空間圖——由節(jié)點(diǎn)(不一定是有限的節(jié)點(diǎn))及連接節(jié)點(diǎn)的分枝的集合構(gòu)成。有限節(jié)點(diǎn)圖——節(jié)點(diǎn)數(shù)目有限的圖稱為有限節(jié)點(diǎn)圖。有向圖——一對(duì)節(jié)點(diǎn)用分枝線連接起來(lái)，從一個(gè)節(jié)點(diǎn)指向另一個(gè)節(jié)點(diǎn)。這種圖叫做有向圖。始節(jié)點(diǎn)叫父節(jié)點(diǎn)或雙親節(jié)點(diǎn)，終節(jié)點(diǎn)叫子節(jié)點(diǎn)。擴(kuò)展——求解父節(jié)點(diǎn)的所有子節(jié)點(diǎn)，叫做擴(kuò)展。路徑——在一系列節(jié)點(diǎn)n1,n2,,nm中，從n1開始，ni總有分枝連接ni+1，稱從n1到nm之間的分枝集合是路徑。路徑中不包含兩個(gè)及以上相同的分枝，如果n1和nm是同一個(gè)節(jié)點(diǎn)，則稱這種路徑為閉路。不構(gòu)成閉路的稱為樹。在用狀態(tài)空間圖來(lái)表示問(wèn)題時(shí)，對(duì)問(wèn)題的求解就是求出從初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的路徑。圖搜索策略1.圖搜索的定義——一種計(jì)算機(jī)在狀態(tài)圖中尋找路徑的方法。2.CLOSED表的引入編號(hào)節(jié)點(diǎn)號(hào)父節(jié)點(diǎn)號(hào)CLOSED表(記錄擴(kuò)展過(guò)的節(jié)點(diǎn))OPEN表的引入節(jié)點(diǎn)號(hào)父節(jié)點(diǎn)號(hào)OPEN表(記錄待擴(kuò)展的節(jié)點(diǎn))舉例：八數(shù)碼魔方例子中OPEN表變化過(guò)程節(jié)點(diǎn)號(hào)父節(jié)點(diǎn)號(hào)S0空AS0BS0CS0DS0EAFACLOSED表變化過(guò)程編號(hào)節(jié)點(diǎn)號(hào)父節(jié)點(diǎn)號(hào)0S0空1AS02BS0圖搜索的一般過(guò)程(1)建立一個(gè)只含有起始節(jié)點(diǎn)S的搜索圖G，把S放到一個(gè)叫做OPEN表的未擴(kuò)展節(jié)點(diǎn)表中。(2)建立一個(gè)叫做CLOSED的已擴(kuò)展節(jié)點(diǎn)表，其初始為空表。(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這條路徑而得到的(指針將在第7步中設(shè)置)。圖搜索的一般過(guò)程(6)擴(kuò)展節(jié)點(diǎn)n，同時(shí)生成不是n的祖先的那些后繼節(jié)點(diǎn)的集合M。把M的這些成員作為n的后繼節(jié)點(diǎn)添入圖G中。(7)對(duì)那些未曾在G中出現(xiàn)過(guò)的(既未曾在OPEN表上或CLOSED表上出現(xiàn)過(guò)的)M成員設(shè)置一個(gè)通向n的指針。把M的這些成員加進(jìn)OPEN表。對(duì)已經(jīng)在OPEN或CLOSED表上的每一個(gè)M成員，確定是否需要更改通到n的指針?lè)较?。?duì)已在CLOSED表上的每個(gè)M成員，確定是否需要更改圖G中通向它的每個(gè)后裔節(jié)點(diǎn)的指針?lè)较颉?8)按某一任意方式或按某個(gè)探試值，重排OPEN表。(9)GOLOOP。開始把S放入OPEN表OPEN表為空表？把第一個(gè)節(jié)點(diǎn)(n)從OPEN表移至CLOSED表n為目標(biāo)節(jié)點(diǎn)嗎？把n的后繼節(jié)點(diǎn)放入OPEN表的末端，提供返回節(jié)點(diǎn)n的指針修改指針?lè)较蛑嘏臤PEN表失敗成功圖搜索一般過(guò)程的框圖是是否否一、盲目搜索

盲目搜索又叫做無(wú)信息搜索，一般只適用于求解比較簡(jiǎn)單的問(wèn)題。主要包括寬度優(yōu)先搜索、等深度優(yōu)先搜索等。特點(diǎn)：

1）搜索按規(guī)定的路線進(jìn)行，不使用與問(wèn)題有關(guān)的啟發(fā)性信息。

2）適用于其狀態(tài)空間圖是樹狀結(jié)構(gòu)的一類問(wèn)題。131、寬度優(yōu)先搜索

定義：如果搜索是以接近起始節(jié)點(diǎn)的程度依次擴(kuò)展節(jié)點(diǎn)的，那么這種搜索就叫做寬度優(yōu)先搜索(breadth-firstsearch)。

基本思想：從初始節(jié)點(diǎn)S開始，逐層地對(duì)節(jié)點(diǎn)進(jìn)行擴(kuò)展并考察它是否為目標(biāo)節(jié)點(diǎn)，在第n層的節(jié)點(diǎn)沒(méi)有全部擴(kuò)展并考察之前，不對(duì)第n＋1層的節(jié)點(diǎn)進(jìn)行擴(kuò)展。OPEN表中的節(jié)點(diǎn)總是按進(jìn)入的先后順序排列，先進(jìn)入的節(jié)點(diǎn)排在前面，后進(jìn)入的排在后面。14寬度優(yōu)先搜索示意圖15寬度優(yōu)先搜索算法：

(1)把起始節(jié)點(diǎn)放到OPEN表中(如果該起始節(jié)點(diǎn)為一目標(biāo)節(jié)點(diǎn)，則求得一個(gè)解答)。

(2)如果OPEN是個(gè)空表，則沒(méi)有解，失敗退出；否則繼續(xù)。

(3)把第一個(gè)節(jié)點(diǎn)(節(jié)點(diǎn)n)從OPEN表移出，并把它放入CLOSED擴(kuò)展節(jié)點(diǎn)表中。

(4)擴(kuò)展節(jié)點(diǎn)n。如果沒(méi)有后繼節(jié)點(diǎn)，則轉(zhuǎn)向上述第(2)步。

(5)把n的所有后繼節(jié)點(diǎn)放到OPEN表的末端，并提供從這些后繼節(jié)點(diǎn)回到n的指針。

(6)如果n的任一個(gè)后繼節(jié)點(diǎn)是個(gè)目標(biāo)節(jié)點(diǎn)，則找到一個(gè)解答，成功退出；否則轉(zhuǎn)向第(2)步。2023/2/216寬度優(yōu)先搜索算法框圖17寬度優(yōu)先搜索方法分析：寬度優(yōu)先搜索是圖搜索一般過(guò)程的特殊情況，將圖搜索一般過(guò)程中的第8步具體化為本算法中的第6步，這實(shí)際是將OPEN表作為“先進(jìn)先出”的隊(duì)列進(jìn)行操作。寬度優(yōu)先搜索方法能夠保證在搜索樹中找到一條通向目標(biāo)節(jié)點(diǎn)的最短途徑；這棵搜索樹提供了所有存在的路徑(如果沒(méi)有路徑存在，那么對(duì)有限圖來(lái)說(shuō)，就說(shuō)該法失敗退出；對(duì)于無(wú)限圖來(lái)說(shuō)，則永遠(yuǎn)不會(huì)終止)。18

例如：寬度優(yōu)先搜索用于八數(shù)碼難題。這個(gè)問(wèn)題就是要把初始棋局變?yōu)槿缦履繕?biāo)棋局的問(wèn)題：

搜索樹上的所有節(jié)點(diǎn)都標(biāo)記它們所對(duì)應(yīng)的狀態(tài)描述，每個(gè)節(jié)點(diǎn)旁邊的數(shù)字表示節(jié)點(diǎn)擴(kuò)展的順序(按順時(shí)針?lè)较蛞苿?dòng)空格)。圖中最后一個(gè)節(jié)點(diǎn)是目標(biāo)節(jié)點(diǎn)。19八數(shù)碼難題的寬度優(yōu)先搜索樹

2620對(duì)應(yīng)動(dòng)態(tài)演示圖212、深度優(yōu)先搜索基本思想：從初始節(jié)點(diǎn)S開始，在其子節(jié)點(diǎn)中選擇一個(gè)節(jié)點(diǎn)進(jìn)行考察，若不是目標(biāo)節(jié)點(diǎn)，則再在該子節(jié)點(diǎn)中選擇一個(gè)節(jié)點(diǎn)進(jìn)行考察，一直如此向下搜索。當(dāng)?shù)竭_(dá)某個(gè)子節(jié)點(diǎn)，且該子節(jié)點(diǎn)既不是目標(biāo)節(jié)點(diǎn)又不能繼續(xù)擴(kuò)展時(shí)，才選擇其兄弟節(jié)點(diǎn)進(jìn)行考察。2023/2/222

深度優(yōu)先搜索示意圖

2023/2/223

在深度優(yōu)先搜索中，首先擴(kuò)展最新產(chǎn)生的(即最深的)節(jié)點(diǎn)（深度相等的節(jié)點(diǎn)可以任意排列）。其結(jié)果是搜索沿著狀態(tài)空間某條單一的路徑從起始節(jié)點(diǎn)向下進(jìn)行下去；只有當(dāng)搜索到達(dá)一個(gè)沒(méi)有后裔的狀態(tài)時(shí)，它才考慮另一條替代的路徑。替代路徑與前面已經(jīng)試過(guò)的路徑不同之處僅僅在于改變最后n步，而且保持n盡可能小。3、深度優(yōu)先搜索2023/2/2243.1.3深度優(yōu)先搜索2023/2/225對(duì)于許多問(wèn)題，其狀態(tài)空間搜索樹的深度可能為無(wú)限深，或者可能至少要比某個(gè)可接受的解答序列的已知深度上限還要深。為了避免考慮太長(zhǎng)的路徑(防止搜索過(guò)程沿著無(wú)益的路徑擴(kuò)展下去)，往往給出一個(gè)節(jié)點(diǎn)擴(kuò)展的最大深度——深度界限。任何節(jié)點(diǎn)如果達(dá)到了深度界限，那么都將把它們作為沒(méi)有后繼節(jié)點(diǎn)處理。值得說(shuō)明的是，即使應(yīng)用了深度界限的規(guī)定，所求得的解答路徑并不一定就是最短的路徑。有界深度優(yōu)先搜索

定義節(jié)點(diǎn)的深度如下：

(1)起始節(jié)點(diǎn)(即根節(jié)點(diǎn))的深度為0。

(2)任何其它節(jié)點(diǎn)的深度等于其父輩節(jié)點(diǎn)深度加上1。2023/2/226含有深度界限的深度優(yōu)先搜索算法：

(1)把起始節(jié)點(diǎn)S放到未擴(kuò)展節(jié)點(diǎn)OPEN表中。如果此節(jié)點(diǎn)為一目標(biāo)節(jié)點(diǎn)，則得到一個(gè)解。

(2)如果OPEN為一空表，則失敗退出。

(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表的前頭。如果沒(méi)有后裔，則轉(zhuǎn)向(2)。

(6)如果后繼節(jié)點(diǎn)中有任一個(gè)為目標(biāo)節(jié)點(diǎn)，則求得一個(gè)解，成功退出；否則，轉(zhuǎn)向(2)。有界深度優(yōu)先搜索2023/2/227算法動(dòng)態(tài)演示圖

2023/2/228

例如：按深度優(yōu)先搜索生成八數(shù)碼難題搜索樹，設(shè)置深度界限為5。

下圖繪出了搜索樹，粗線條的路徑表明含有5條應(yīng)用規(guī)則的一個(gè)解。從圖可見，深度優(yōu)先搜索過(guò)程是沿著一條路徑進(jìn)行下去，直到深度界限為止，然后再考慮只有最后一步有差別的相同深度或較淺深度可供選擇的路徑，接著再考慮最后兩步有差別的那些路徑，等等。2023/2/229八數(shù)碼難題的深度優(yōu)先搜索樹

2023/2/230二、啟發(fā)式搜索

盲目搜索的不足：效率低，耗費(fèi)過(guò)多的計(jì)算空間與時(shí)間。寬度優(yōu)先搜索、深度優(yōu)先搜索，或等代價(jià)搜索算法,是按事先規(guī)定的路線進(jìn)行搜索，或按已經(jīng)付出的代價(jià)決定下一步要搜索的節(jié)點(diǎn)，其主要差別是OPEN表中待擴(kuò)展節(jié)點(diǎn)的順序問(wèn)題。如果找到一種方法用于排列待擴(kuò)展節(jié)點(diǎn)的順序，即選擇最有希望的節(jié)點(diǎn)加以擴(kuò)展，那么，搜索效率將會(huì)大為提高。2023/2/231二、啟發(fā)式搜索

盲目搜索的共同特點(diǎn)：沒(méi)有利用問(wèn)題本身的特性信息，在決定要被擴(kuò)展的節(jié)點(diǎn)時(shí)，都沒(méi)有考慮該節(jié)點(diǎn)在解的路徑上的可能性有多大，它是否有利于問(wèn)題求解以及求出的解是否為最優(yōu)解等。2023/2/232二、啟發(fā)式搜索

啟發(fā)信息進(jìn)行搜索技術(shù)一般需要某些有關(guān)具體問(wèn)題領(lǐng)域特性的、與具體問(wèn)題求解過(guò)程有關(guān)的、并可指導(dǎo)搜索過(guò)程朝著最有希望方向前進(jìn)的控制信息，把此種信息叫做啟發(fā)信息。

把利用啟發(fā)信息的搜索方法叫做啟發(fā)性搜索方法。

特點(diǎn)：重排OPEN表，選擇最有希望的節(jié)點(diǎn)加以擴(kuò)展種類：最佳優(yōu)先搜索、A*算法等2023/2/2331、啟發(fā)式搜索策略

啟發(fā)信息按其用途可分為3種：

(1)用于決定要擴(kuò)展的下一個(gè)節(jié)點(diǎn)，以免像在寬度優(yōu)先或深度優(yōu)先搜索中那樣盲目地?cái)U(kuò)展。

(2)在擴(kuò)展一個(gè)節(jié)點(diǎn)的過(guò)程中，用于決定要生成哪一個(gè)或哪幾個(gè)后繼節(jié)點(diǎn)，以免盲目地同時(shí)生成所有可能的節(jié)點(diǎn)。

(3)用于決定某些應(yīng)該從搜索樹中拋棄或修剪的節(jié)點(diǎn)。2023/2/2342、估價(jià)函數(shù)用來(lái)估算節(jié)點(diǎn)希望程度的量度，叫做估價(jià)函數(shù)(evaluationfunction)。估價(jià)函數(shù)的任務(wù)就是估計(jì)OPEN表中各節(jié)點(diǎn)的重要程度。一個(gè)節(jié)點(diǎn)的“希望”(promise)有幾種不同的定義方法:1)估算目標(biāo)節(jié)點(diǎn)到此節(jié)點(diǎn)的距離；

2)解答路徑包括被估價(jià)過(guò)的節(jié)點(diǎn)，并計(jì)算全條路徑的長(zhǎng)度或難度。2023/2/2352、估價(jià)函數(shù)

用符號(hào)f來(lái)標(biāo)記估價(jià)函數(shù)，用f(n)表示節(jié)點(diǎn)n的估價(jià)函數(shù)值。暫時(shí)令f為任意函數(shù)，以后將會(huì)提出f是從起始節(jié)點(diǎn)約束地通過(guò)節(jié)點(diǎn)n而到達(dá)目標(biāo)節(jié)點(diǎn)的最小代價(jià)路徑上的一個(gè)估算代價(jià)。

一般形式：

f(n)=g(n)+h(n)g(n)是從s0到n的實(shí)際代價(jià)。

h(n)是從節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)sg的估計(jì)代價(jià)。2023/2/2363、有序搜索

用估價(jià)函數(shù)f來(lái)排列GRAPHSEARCH第8步中OPEN表上的節(jié)點(diǎn)。根據(jù)習(xí)慣，OPEN表上的節(jié)點(diǎn)按照它們f函數(shù)值的遞增順序排列。根據(jù)推測(cè)，某個(gè)具有低估價(jià)值的節(jié)點(diǎn)較有可能處在最佳路徑上。應(yīng)用某個(gè)算法(例如等代價(jià)算法)選擇OPEN表上具有最小f值的節(jié)點(diǎn)作為下一個(gè)要擴(kuò)展的節(jié)點(diǎn)。這種搜索方法叫做有序搜索或最佳優(yōu)先搜索，而其算法就叫做有序搜索算法或最佳優(yōu)先算法?？梢娝偸沁x擇最有希望的節(jié)點(diǎn)作為下一個(gè)要擴(kuò)展的節(jié)點(diǎn)。有序搜索(orderedsearch)又稱為最好優(yōu)先搜索(best-firstsearch)。2023/2/2373、有序搜索

尼爾遜（Nilsson）曾提出一個(gè)有序搜索的基本算法。估價(jià)函數(shù)f按照如下方法確定：一個(gè)節(jié)點(diǎn)希望程度越大，其f值就越小。被選為擴(kuò)展的節(jié)點(diǎn)，是估價(jià)函數(shù)最小的節(jié)點(diǎn)。2023/2/238有序狀態(tài)空間搜索算法(1)把起始節(jié)點(diǎn)S放到OPEN表中，計(jì)算f(S)并把其值與節(jié)點(diǎn)S聯(lián)系起來(lái)。(2)如果OPEN是個(gè)空表，則失敗退出，無(wú)解。(3)從OPEN表中選擇一個(gè)f值最小的節(jié)點(diǎn)i。結(jié)果有幾個(gè)節(jié)點(diǎn)合格，當(dāng)其中有一個(gè)為目標(biāo)節(jié)點(diǎn)時(shí)，則選擇此目標(biāo)節(jié)點(diǎn)，否則就選擇其中任一個(gè)節(jié)點(diǎn)作為節(jié)點(diǎn)i。(4)把節(jié)點(diǎn)i從OPEN表中移出，并把它放入CLOSED的擴(kuò)展節(jié)點(diǎn)表中。(5)如果i是個(gè)目標(biāo)節(jié)點(diǎn)，則成功退出，求得一個(gè)解。

2023/2/239(6)擴(kuò)展節(jié)點(diǎn)i生成其全部后繼節(jié)點(diǎn)。對(duì)于i的每一個(gè)后繼節(jié)點(diǎn)j：(a)計(jì)算f(j)。(b)如果j既不在OPEN表中，又不在CLOSED表中，則用估價(jià)函數(shù)f把它添入OPEN表。從j加一指向其父輩節(jié)點(diǎn)i的指針，以便一旦找到目標(biāo)節(jié)點(diǎn)時(shí)記住一個(gè)解答路徑。(c)如果j已在OPEN表上或CLOSED表上，則比較剛剛對(duì)j計(jì)算過(guò)的f值和前面計(jì)算過(guò)的該節(jié)點(diǎn)在表中的f值。如果新的f值較小，則(i)以此新值取代舊值。(ii)從j指向i，而不是指向它的父輩節(jié)點(diǎn)。(iii)如果節(jié)點(diǎn)j在CLOSED表中，則把它移回OPEN表(7)轉(zhuǎn)向(2)，即GOTO(2)。有序狀態(tài)空間搜索算法2023/2/240注釋：步驟（6.c）是一般搜索圖所需要的，該圖中可能有一個(gè)以上的父輩節(jié)點(diǎn)。具有最小估價(jià)函數(shù)f（j）的節(jié)點(diǎn)被選作父輩節(jié)點(diǎn)。但是，由于搜索樹，它最多只有一個(gè)父輩節(jié)點(diǎn)，所以步驟（6.c）可以略去。有序狀態(tài)空間搜索算法2023/2/241

有序搜索算法框圖

2023/2/242

有序搜索的有效性直接取決于f的選擇，如果選擇的f不合適，有序搜索就可能失去一個(gè)最好的解甚至全部的解。如果沒(méi)有適用的準(zhǔn)確的希望量度，那么f的選擇將涉及兩個(gè)方面的內(nèi)容：一方面是時(shí)間和空間之間的折衷方案；另一方面是保證有一個(gè)最優(yōu)的解或任意解。有序狀態(tài)空間搜索算法2023/2/243有序搜索例子使用八數(shù)碼難題例子說(shuō)明過(guò)程GRAPHSEARCH是如何應(yīng)用估價(jià)函數(shù)排列節(jié)點(diǎn)的。采用簡(jiǎn)單的估價(jià)函數(shù)

f(n)=d(n)+W(n)

其中：d(n)是搜索樹中節(jié)點(diǎn)n的深度；W(n)用來(lái)計(jì)算對(duì)應(yīng)于節(jié)點(diǎn)n的數(shù)據(jù)庫(kù)中錯(cuò)放的棋子個(gè)數(shù)。2023/2/244起始節(jié)點(diǎn)棋局28316475的f值等于1+4=5。有序搜索例子2023/2/245八數(shù)碼難題的有序搜索樹2023/2/2462023/2/247從圖可見，這里所求得的解答路徑和用其它搜索方法找到的解答路徑相同。不過(guò)，估價(jià)函數(shù)的應(yīng)用顯著地減少了被擴(kuò)展的節(jié)點(diǎn)數(shù)(如果我們只用估價(jià)函數(shù)f(n)=d(n)，那么我們就得到寬度優(yōu)先搜索過(guò)程)。八數(shù)碼難題的有序搜索樹2023/2/248正確地選擇估價(jià)函數(shù)對(duì)確定搜索結(jié)果具有決定性的作用。使用不能識(shí)別某些節(jié)點(diǎn)真實(shí)希望的估價(jià)函數(shù)會(huì)形成非最小代價(jià)路徑；而使用一個(gè)過(guò)多地估計(jì)了全部節(jié)點(diǎn)希望的估價(jià)函數(shù)(就像寬度優(yōu)先搜索方法得到的估價(jià)函數(shù)一樣)又會(huì)擴(kuò)展過(guò)多的節(jié)點(diǎn)。八數(shù)碼難題的有序搜索樹2023/2/2494、A*算法A*算法的估價(jià)函數(shù)：令估價(jià)函數(shù)f使得在任意節(jié)點(diǎn)上其函數(shù)值f(n)能估算出從節(jié)點(diǎn)S到節(jié)點(diǎn)n的最小代價(jià)路徑的代價(jià)與從節(jié)點(diǎn)n到某一目標(biāo)節(jié)點(diǎn)的最小代價(jià)路徑的代價(jià)之總和，也就是說(shuō)f(n)是約束通過(guò)節(jié)點(diǎn)n的一條最小代價(jià)路徑的代價(jià)的一個(gè)估計(jì)。因此，OPEN表上具有最小f值的那個(gè)節(jié)點(diǎn)就是所估計(jì)的加有最少嚴(yán)格約束條件的節(jié)點(diǎn)，而且下一步要擴(kuò)展這個(gè)節(jié)點(diǎn)是合適的。2023/2/250A*算法中幾個(gè)有用的記號(hào)：令k(ni，nj)表示任意兩個(gè)節(jié)點(diǎn)ni和nj之間最小代價(jià)路徑的實(shí)際代價(jià)(對(duì)于兩節(jié)點(diǎn)間沒(méi)有通路的節(jié)點(diǎn)，函數(shù)k沒(méi)有定義)。于是，從節(jié)點(diǎn)n到某個(gè)具體的目標(biāo)節(jié)點(diǎn)ti，某一條最小代價(jià)路徑的代價(jià)可由k(n,ti)給出。令h*(n)表示整個(gè)目標(biāo)節(jié)點(diǎn)集合｛ti｝上所有k(n,ti)中最小的一個(gè)，因此，h*(n)就是從n到目標(biāo)節(jié)點(diǎn)最小代價(jià)路徑的代價(jià)，而且從n到目標(biāo)節(jié)點(diǎn)能夠獲得h*(n)的任一路徑就是一條從n到某個(gè)目標(biāo)節(jié)點(diǎn)的最佳路徑(對(duì)于任何不能到達(dá)目標(biāo)節(jié)點(diǎn)的節(jié)點(diǎn)n，函數(shù)h*沒(méi)有定義)。2023/2/251

通常感興趣的是想知道從已知起始節(jié)點(diǎn)S到任意節(jié)點(diǎn)n的一條最佳路徑的代價(jià)k(S,n)。為此，引進(jìn)一個(gè)新函數(shù)g*，這將使引入的記號(hào)得到某些簡(jiǎn)化。對(duì)所有從S開始可達(dá)到n的路徑來(lái)說(shuō)，函數(shù)g*定義為

g*(n)=k(S,n)2023/2/252

因而f*(n)值就是從S開始約束通過(guò)節(jié)點(diǎn)n的一條最佳路徑的代價(jià)，而f*(S)=h*(S)是一條從S到某個(gè)目標(biāo)節(jié)點(diǎn)中間無(wú)約束的一條最佳路徑的代價(jià)。

其次，定義函數(shù)f*，使得在任一節(jié)點(diǎn)n上其函數(shù)值f*(n)就是從節(jié)點(diǎn)S到節(jié)點(diǎn)n的一條最佳路徑的實(shí)際代價(jià)加上從節(jié)點(diǎn)n到某目標(biāo)節(jié)點(diǎn)的一條最佳路徑的代價(jià)之和，即

f*(n)=g*(n)+h*(n)2023/2/253希望估價(jià)函數(shù)f是f*的一個(gè)估計(jì)，此估計(jì)可由下式給出：

f(n)=g(n)+h(n)其中：g是g*的估計(jì)；h是h*的估計(jì)。對(duì)于g(n)來(lái)說(shuō)，一個(gè)明顯的選擇就是搜索樹中從S到n這段路徑的代價(jià)，這一代價(jià)可以由從n到S尋找指針時(shí)，把所遇到的各段弧線的代價(jià)加起來(lái)給出(這條路徑就是到目前為止用搜索算法找到的從S到n的最小代價(jià)路徑)。這個(gè)定義包含了g(n)≥g*(n)。對(duì)于h*(n)的估計(jì)h(n)，它依賴于有關(guān)問(wèn)題的領(lǐng)域的啟發(fā)信息。h叫做啟發(fā)函數(shù)。2023/2/254A算法和A*算法的定義

定義1

在GRAPHSEARCH過(guò)程中，如果第8步的重排OPEN表是依據(jù)f(x)=g(x)+h(x)進(jìn)行的，則稱該過(guò)程為A算法。

定義2

在A算法中，如果對(duì)所有的x，h(x)≤h*(x)成立,則稱h(x)為h*(x)的下界，它表示某種偏于保守的估計(jì)。2023/2/255

定義3

采用h*(x)的下界h(x)為啟發(fā)函數(shù)的A算法，稱為A*算法。當(dāng)h=0時(shí)，A*算法就變?yōu)橛行蛩阉魉惴ā?/p>

A*算法是一種有序搜索算法，其特點(diǎn)在于對(duì)估價(jià)函數(shù)的定義上。對(duì)于一般的有序搜索，總是選擇f值最小的節(jié)