第五章啟發(fā)式搜索課件

1、第5章 搜索求解策略 5.1 搜索的概念搜索的概念 5.2 狀態(tài)空間的搜索策略狀態(tài)空間的搜索策略 5.3 盲目的圖搜索策略盲目的圖搜索策略 5.4 啟發(fā)式圖搜索策略啟發(fā)式圖搜索策略 5.5 與與/或或圖搜索策略圖搜索策略 例例1 三數(shù)碼問(wèn)題（數(shù)碼問(wèn)題（3 puzzle problem）。 123312初始棋局目標(biāo)棋局第5章 搜索求解策略問(wèn)題求解：?jiǎn)栴}求解：?jiǎn)栴}的表示。問(wèn)題的表示。 選擇一種相對(duì)合適的求解方法。選擇一種相對(duì)合適的求解方法。問(wèn)題求解的基本方法：?jiǎn)栴}求解的基本方法：搜索法搜索法、歸約法、歸結(jié)法、歸約法、歸結(jié)法、推理法及產(chǎn)生式等。、推理法及產(chǎn)生式等。v狀態(tài)空間表示法狀態(tài)空間表示法v搜索

2、策略：搜索策略： （1）盲目搜索：寬度優(yōu)先搜索、深度優(yōu)先搜索）盲目搜索：寬度優(yōu)先搜索、深度優(yōu)先搜索 （2）啟發(fā)式搜索：）啟發(fā)式搜索：A算法和算法和A*搜索；搜索；第5章 搜索求解策略v搜索中需要解決的基本問(wèn)題：搜索中需要解決的基本問(wèn)題：（1）是否一定能找到一個(gè)解。）是否一定能找到一個(gè)解。（2）是否終止運(yùn)行或是否會(huì)陷入一個(gè)死循環(huán)。）是否終止運(yùn)行或是否會(huì)陷入一個(gè)死循環(huán)。（3）找到的解是否是最佳解。）找到的解是否是最佳解。（4）時(shí)間與空間復(fù)雜性如何。）時(shí)間與空間復(fù)雜性如何。5.1.1 搜索的基本問(wèn)題與主要過(guò)程5.1.1 搜索的基本問(wèn)題與主要過(guò)程搜索的主要過(guò)程搜索的主要過(guò)程：(1) 從初始或目的狀態(tài)出

3、發(fā)，并將它作為當(dāng)前狀態(tài)。從初始或目的狀態(tài)出發(fā)，并將它作為當(dāng)前狀態(tài)。(2) 掃描操作算子集，將適用掃描操作算子集，將適用當(dāng)前狀態(tài)當(dāng)前狀態(tài)的一些操作算子的一些操作算子作用于當(dāng)前狀態(tài)而得到作用于當(dāng)前狀態(tài)而得到新的狀態(tài)新的狀態(tài)，并建立指向其父，并建立指向其父結(jié)點(diǎn)的結(jié)點(diǎn)的指針指針 。(3) 檢查所生成的新?tīng)顟B(tài)是否滿足檢查所生成的新?tīng)顟B(tài)是否滿足結(jié)束狀態(tài)結(jié)束狀態(tài)，如果滿足，如果滿足，則得到問(wèn)題的一個(gè)解，并可沿著有關(guān)指針從結(jié)束，則得到問(wèn)題的一個(gè)解，并可沿著有關(guān)指針從結(jié)束狀態(tài)反向到達(dá)開(kāi)始狀態(tài)，給出一解答路徑；否則，狀態(tài)反向到達(dá)開(kāi)始狀態(tài)，給出一解答路徑；否則，將新?tīng)顟B(tài)作為當(dāng)前狀態(tài)，返回第將新?tīng)顟B(tài)作為當(dāng)前狀態(tài)，返回

4、第(2)步再進(jìn)行搜索步再進(jìn)行搜索。 5.1.2 搜索策略1. 搜索方向搜索方向： (1) 數(shù)據(jù)驅(qū)動(dòng)數(shù)據(jù)驅(qū)動(dòng)：從初始狀態(tài)出發(fā)的正向搜索。：從初始狀態(tài)出發(fā)的正向搜索。 正向搜索正向搜索從問(wèn)題給出的條件（一個(gè)用于狀態(tài)轉(zhuǎn)換的操?gòu)膯?wèn)題給出的條件（一個(gè)用于狀態(tài)轉(zhuǎn)換的操作算子集合）出發(fā)。作算子集合）出發(fā)。逆向搜索逆向搜索：先從想達(dá)到的目的入手，看哪些操作算子能產(chǎn)：先從想達(dá)到的目的入手，看哪些操作算子能產(chǎn)生該目的以及應(yīng)用這些操作算子產(chǎn)生目的時(shí)需要哪些條件。生該目的以及應(yīng)用這些操作算子產(chǎn)生目的時(shí)需要哪些條件。 (2) 目的驅(qū)動(dòng)目的驅(qū)動(dòng)：從目的：從目的狀態(tài)出發(fā)的逆向搜索。狀態(tài)出發(fā)的逆向搜索。5.1.2 搜索策略

5、(3) 雙向搜索雙向搜索 雙向搜索雙向搜索：從開(kāi)始狀態(tài)出發(fā)作正向搜索，同時(shí)又從目的：從開(kāi)始狀態(tài)出發(fā)作正向搜索，同時(shí)又從目的狀態(tài)出發(fā)作逆向搜索，直到兩條路徑在中間的某處匯合狀態(tài)出發(fā)作逆向搜索，直到兩條路徑在中間的某處匯合為止。為止。5.1.2 搜索策略2. 盲目搜索與啟發(fā)式搜索盲目搜索與啟發(fā)式搜索:（1）盲目搜索：盲目搜索：在不具有對(duì)特定問(wèn)題的任何有關(guān)信在不具有對(duì)特定問(wèn)題的任何有關(guān)信息的條件下，按固定的步驟（依次或隨機(jī)調(diào)用操息的條件下，按固定的步驟（依次或隨機(jī)調(diào)用操作算子）進(jìn)行的搜索。作算子）進(jìn)行的搜索。 （2）啟發(fā)式搜索：?jiǎn)l(fā)式搜索：考慮特定問(wèn)題領(lǐng)域可應(yīng)用的知識(shí)考慮特定問(wèn)題領(lǐng)域可應(yīng)用的知識(shí)，動(dòng)

6、態(tài)地確定調(diào)用操作算子的步驟，優(yōu)先選擇較，動(dòng)態(tài)地確定調(diào)用操作算子的步驟，優(yōu)先選擇較適合的操作算子，盡量減少不必要的搜索，以求適合的操作算子，盡量減少不必要的搜索，以求盡快地到達(dá)結(jié)束盡快地到達(dá)結(jié)束狀態(tài)。狀態(tài)。5.1.2 搜索策略3.人工智能的主要搜索策略：人工智能的主要搜索策略：求求任一解任一解的搜索策略：的搜索策略： 爬山法（爬山法（Hill Climbing）；）； 深度優(yōu)先法（深度優(yōu)先法（Depth-first search）；）； 限定范圍搜索法（限定范圍搜索法（Beam Search）；）； 回溯法（回溯法（Back-tracking）；）； 最好優(yōu)先法（最好優(yōu)先法（Best-first

7、 search）；）；5.1.2 搜索策略3.人工智能的主要搜索策略：人工智能的主要搜索策略：求求最佳解最佳解的搜索策略：的搜索策略： 大英博物館法（大英博物館法（British museum）；）； 寬度優(yōu)先法（寬度優(yōu)先法（Breadth-first search）；）； 分支界定法（分支界定法（Branch and Bound）；）； 最佳圖搜索法（最佳圖搜索法（A*）；）； 動(dòng)態(tài)規(guī)劃法（動(dòng)態(tài)規(guī)劃法（Dynamic Programing）；）；5.1.2 搜索策略3.人工智能的主要搜索策略：人工智能的主要搜索策略：求求與或關(guān)系解圖與或關(guān)系解圖的搜索法：的搜索法： 一般的與或圖關(guān)系解的搜索法

8、；（一般的與或圖關(guān)系解的搜索法；（AO*） 極大極小法（極大極小法（Minimax）；）； - 剪枝法剪枝法（ - Pruning）；）； 啟發(fā)式剪枝法（啟發(fā)式剪枝法（Heuristic Pruning）第5章 搜索求解策略 5.1 搜索的概念搜索的概念5.2 狀態(tài)空間知識(shí)表示方法狀態(tài)空間知識(shí)表示方法 5.3 盲目的圖搜索策略盲目的圖搜索策略 5.4 啟發(fā)式圖搜索策略啟發(fā)式圖搜索策略 5.5 與與/或或圖搜索策略圖搜索策略5.2 狀態(tài)空間知識(shí)表示方法5.2.1 狀態(tài)空間表示法狀態(tài)空間表示法5.2.2 狀態(tài)空間的圖描述狀態(tài)空間的圖描述5.2.1 狀態(tài)空間表示法n 狀態(tài)空間表示法：知識(shí)表示的一種方

9、法狀態(tài)空間表示法：知識(shí)表示的一種方法n 狀態(tài)：表示系統(tǒng)狀態(tài)、事實(shí)等敘述型知識(shí)的一組變量或數(shù)狀態(tài)：表示系統(tǒng)狀態(tài)、事實(shí)等敘述型知識(shí)的一組變量或數(shù)組：組： qi：狀態(tài)變量：狀態(tài)變量,nqqqQ21 ,mfffF21 操作：表示引起狀態(tài)變化的過(guò)程型知識(shí)的一組關(guān)系或函數(shù)：操作：表示引起狀態(tài)變化的過(guò)程型知識(shí)的一組關(guān)系或函數(shù)： 操作符（算子，操作算子）：走步，過(guò)程，規(guī)則，數(shù)學(xué)算操作符（算子，操作算子）：走步，過(guò)程，規(guī)則，數(shù)學(xué)算子，運(yùn)算符或邏輯符子，運(yùn)算符或邏輯符5.2.1 狀態(tài)空間表示法 狀態(tài)空間：利用狀態(tài)變量和操作符號(hào)，表示系統(tǒng)或狀態(tài)空間：利用狀態(tài)變量和操作符號(hào)，表示系統(tǒng)或問(wèn)題的有關(guān)知識(shí)的符號(hào)體系，狀態(tài)空

10、間是一個(gè)四元問(wèn)題的有關(guān)知識(shí)的符號(hào)體系，狀態(tài)空間是一個(gè)四元組：組： ),(0GSOS ：狀態(tài)集合。：狀態(tài)集合。 ：操作算子的集合。：操作算子的集合。 ：包含問(wèn)題的初始狀態(tài)是：包含問(wèn)題的初始狀態(tài)是S 的非空子集。的非空子集。 ：若干具體狀態(tài)或滿足某些性質(zhì)的路徑信息描述：若干具體狀態(tài)或滿足某些性質(zhì)的路徑信息描述。O0SGS5.2.1 狀態(tài)空間表示法 求解路徑求解路徑：從從S0結(jié)點(diǎn)到結(jié)點(diǎn)到G結(jié)點(diǎn)的路徑。結(jié)點(diǎn)的路徑。 GSSSkOOOO321210kOO,1：狀態(tài)空間的一個(gè)解。：狀態(tài)空間的一個(gè)解。 狀態(tài)空間的一個(gè)解：一個(gè)有限的狀態(tài)空間的一個(gè)解：一個(gè)有限的操作算子序列操作算子序列。v例如下棋、迷宮及各種游

11、戲。例如下棋、迷宮及各種游戲。 例例1 三數(shù)碼問(wèn)題（數(shù)碼問(wèn)題（3 puzzle problem）。 5.2.1 狀態(tài)空間表示法狀態(tài)空間表示法狀態(tài)集狀態(tài)集 ：所有擺法：所有擺法S操作算子：操作算子：將空格向上移將空格向上移Up將空格向左移將空格向左移Left將空格向下移將空格向下移Down將空格向右移將空格向右移Right123312初始棋局目標(biāo)棋局解法解法1：123123123312312312初始棋局目標(biāo)棋局downrightupleftdown5.2.1 狀態(tài)空間表示法狀態(tài)空間表示法5.2.2 狀態(tài)空間的圖描述（狀態(tài)）（狀態(tài)）（操作算子）（操作算子）狀態(tài)空間的有向圖描述狀態(tài)空間的有向圖描述

12、第5章 搜索求解策略 5.1 搜索的概念搜索的概念 5.2 狀態(tài)空間知識(shí)表示方法狀態(tài)空間知識(shí)表示方法5.3 盲目的圖搜索策略盲目的圖搜索策略 5.4 啟發(fā)式圖搜索策略啟發(fā)式圖搜索策略 5.5 與與/或或圖搜索策略圖搜索策略5.3 盲目的圖搜索策略5.3.1 回溯策略回溯策略5.3.2 寬度優(yōu)先搜索策略寬度優(yōu)先搜索策略5.3.3 深度優(yōu)先搜索策略深度優(yōu)先搜索策略5.3.1 回溯策略 帶回溯策略的搜索：帶回溯策略的搜索：（走不通就回頭）（走不通就回頭）u 從初始狀態(tài)出發(fā)，不停地、試探性地尋找路徑，從初始狀態(tài)出發(fā)，不停地、試探性地尋找路徑，直到它到達(dá)目的或直到它到達(dá)目的或“不可解結(jié)點(diǎn)不可解結(jié)點(diǎn)”，即

13、，即“死胡同死胡同”為止。為止。u 若它遇到不可解結(jié)點(diǎn)就回溯到路徑中若它遇到不可解結(jié)點(diǎn)就回溯到路徑中最近的父結(jié)最近的父結(jié)點(diǎn)點(diǎn)上，查看該結(jié)點(diǎn)是否還有其他的子結(jié)點(diǎn)未被擴(kuò)展上，查看該結(jié)點(diǎn)是否還有其他的子結(jié)點(diǎn)未被擴(kuò)展。u若有，則沿這些子結(jié)點(diǎn)繼續(xù)搜索；如果找到目標(biāo)，若有，則沿這些子結(jié)點(diǎn)繼續(xù)搜索；如果找到目標(biāo)，就成功退出搜索，返回解題路徑。就成功退出搜索，返回解題路徑。5.3.1 回溯策略1 AB 2E 3J 57 K9 G6 F10 H11 D8 C回溯搜索示意圖回溯搜索示意圖5.3.1 回溯策略回溯搜索算法的幾張表：回溯搜索算法的幾張表：(1) PS（path states）表：保存當(dāng)前搜索路徑上的狀

14、態(tài)。）表：保存當(dāng)前搜索路徑上的狀態(tài)。如果找到了目的，如果找到了目的，PS就是解路徑上的狀態(tài)有序集。就是解路徑上的狀態(tài)有序集。 (2) NPS（new path states）表：新的路徑狀態(tài)表。它包）表：新的路徑狀態(tài)表。它包含了等待搜索的狀態(tài)，其后裔狀態(tài)還未被搜索到，含了等待搜索的狀態(tài)，其后裔狀態(tài)還未被搜索到，即未被生成擴(kuò)展即未被生成擴(kuò)展 。(3) NSS（no solvable states）表：不可解狀態(tài)集，列出）表：不可解狀態(tài)集，列出了找不到解題路徑的狀態(tài)。如果在搜索中擴(kuò)展出的了找不到解題路徑的狀態(tài)。如果在搜索中擴(kuò)展出的狀態(tài)是它的元素，則可立即將之排除，不必沿該狀狀態(tài)是它的元素，則可立即

15、將之排除，不必沿該狀態(tài)繼續(xù)搜索。態(tài)繼續(xù)搜索。 回溯搜索示意圖的回溯軌跡：回溯搜索示意圖的回溯軌跡： 初值：初值：PS=A； NPS=A； NSS= ； CS=A。 5.3.1 回溯策略1 AB 2E 3J 57 K9 G6 F10 H11 D8 C5.3.1 回溯策略圖搜索算法（深度優(yōu)先、寬度優(yōu)先、最好優(yōu)先搜索等）圖搜索算法（深度優(yōu)先、寬度優(yōu)先、最好優(yōu)先搜索等）的回溯思想：的回溯思想：（1）用未處理狀態(tài)表（用未處理狀態(tài)表（NPS）使算法能返回（回溯）到其）使算法能返回（回溯）到其 中任一狀態(tài)。中任一狀態(tài)。 （2）用一張）用一張“死胡同死胡同”狀態(tài)表（狀態(tài)表（NSS）來(lái)避免算法重新搜索）來(lái)避免算

16、法重新搜索 無(wú)解的路徑。無(wú)解的路徑。 （3）在）在PS 表中記錄當(dāng)前搜索路徑的狀態(tài)，當(dāng)滿足目的時(shí)可表中記錄當(dāng)前搜索路徑的狀態(tài)，當(dāng)滿足目的時(shí)可 以將它作為結(jié)果返回。以將它作為結(jié)果返回。 （4）為避免陷入死循環(huán)必須對(duì)新生成的子狀態(tài)進(jìn)行檢查，）為避免陷入死循環(huán)必須對(duì)新生成的子狀態(tài)進(jìn)行檢查， 看它是否在該三張表中看它是否在該三張表中 。5.3.2 寬度優(yōu)先搜索策略寬度優(yōu)先搜索寬度優(yōu)先搜索：以接近起始結(jié)點(diǎn)的程度為依據(jù)進(jìn)行逐層擴(kuò)展：以接近起始結(jié)點(diǎn)的程度為依據(jù)進(jìn)行逐層擴(kuò)展的搜索方法。（用隊(duì)列的存儲(chǔ)結(jié)構(gòu)，類似于樹的按層次遍歷的搜索方法。（用隊(duì)列的存儲(chǔ)結(jié)構(gòu)，類似于樹的按層次遍歷的過(guò)程。的過(guò)程。特點(diǎn)：逐層搜索；高

17、價(jià)搜索：若解存在，必能找到。特點(diǎn)：逐層搜索；高價(jià)搜索：若解存在，必能找到。 例例2 通過(guò)搬動(dòng)積木塊，希望從初始狀態(tài)達(dá)到一個(gè)目通過(guò)搬動(dòng)積木塊，希望從初始狀態(tài)達(dá)到一個(gè)目的狀態(tài)，即三塊積木堆疊在一起。的狀態(tài)，即三塊積木堆疊在一起。 BCAABC(a) 初始狀態(tài)初始狀態(tài)(b) 目的狀態(tài)目的狀態(tài) 積木問(wèn)題積木問(wèn)題5.3.2 寬度優(yōu)先搜索策略 操作算子為操作算子為MOVE（X，Y）：把積木）：把積木X搬到搬到Y(jié)（積（積木或桌面）上面。木或桌面）上面。MOVE（A，Table）：）：“搬動(dòng)積木搬動(dòng)積木A到桌到桌面上面上”。 操作算子可運(yùn)用的先決條件：操作算子可運(yùn)用的先決條件：（1）被搬動(dòng)積木的頂部必須為空。

18、）被搬動(dòng)積木的頂部必須為空。（2）如果）如果 Y 是積木，則積木是積木，則積木 Y 的頂部也必須為空。的頂部也必須為空。（3）同一狀態(tài)下，運(yùn)用操作算子的次數(shù)不得多于一次。）同一狀態(tài)下，運(yùn)用操作算子的次數(shù)不得多于一次。5.3.2 寬度優(yōu)先搜索策略ABABACCBACCCBABCABACBAABCBCBCCABAMOVE(A,TABLE)MOVE(A,TABLE)MOVE(C,AMOVE(C,A) )MOVE(A,CMOVE(A,C) )MOVE(B,A)MOVE(B,A)MOVE(B,C)MOVE(B,C) MOVE(C,AMOVE(C,A) )MOVE(C,B)MOVE(C,B) MOVE(C

19、,B)MOVE(C,B)MOVE(A,BMOVE(A,B) )0S1S2S3S4S5S6S7S8S9S10S沒(méi)有后裔，失敗退出 積木問(wèn)題的寬度優(yōu)先搜索樹積木問(wèn)題的寬度優(yōu)先搜索樹5.3.2 寬度優(yōu)先搜索策略5.3.2 寬度優(yōu)先搜索策略vopen表（表（NPS表）：已經(jīng)生成出來(lái)但其子狀態(tài)未被搜索的狀表）：已經(jīng)生成出來(lái)但其子狀態(tài)未被搜索的狀態(tài)。態(tài)。vclosed表（表（ PS表和表和NSS表的合并）：記錄了已被生成擴(kuò)展過(guò)表的合并）：記錄了已被生成擴(kuò)展過(guò)的狀態(tài)。的狀態(tài)。 重復(fù)重復(fù)OPEN表表CLOSE表表0S0 1234。重復(fù)重復(fù)OPEN表表CLOSE表表0S0 1S1，S2，S3S0234。重復(fù)重復(fù)

20、OPEN表表CLOSE表表0S0 1S1，S2，S3S02S2，S3，S4，S5，S6，S7S1，S034。重復(fù)重復(fù)OPEN表表CLOSE表表0S0 1S1，S2，S3S02S2，S3，S4，S5，S6，S7S1，S03S3，S4，S5，S6，S7S2，S1，S04。重復(fù)重復(fù)OPEN表表CLOSE表表0S0 1S1，S2，S3S02S2，S3，S4，S5，S6，S7S1，S03S3，S4，S5，S6，S7S2，S1，S04S4，S5，S6，S7，S8S3，S2，S1，S0。5.3.3 深度優(yōu)先搜索策略0S12345678910111213KK 深度優(yōu)先搜索法中狀態(tài)的搜索次序深度優(yōu)先搜索法中狀態(tài)

21、的搜索次序0S12345678910111213KK深度優(yōu)先搜索深度優(yōu)先搜索：首先擴(kuò)展最新產(chǎn)生的節(jié)點(diǎn)，深度相等的節(jié)：首先擴(kuò)展最新產(chǎn)生的節(jié)點(diǎn)，深度相等的節(jié)點(diǎn)可以任意排列的搜索方法。點(diǎn)可以任意排列的搜索方法。（用堆棧的數(shù)據(jù)結(jié)構(gòu)）（用堆棧的數(shù)據(jù)結(jié)構(gòu)）特點(diǎn)：搜索沿著狀態(tài)空間的某單一路徑沿著起始點(diǎn)向下進(jìn)特點(diǎn)：搜索沿著狀態(tài)空間的某單一路徑沿著起始點(diǎn)向下進(jìn)行下去，僅當(dāng)搜索到達(dá)一個(gè)沒(méi)有后裔的狀態(tài)時(shí)，才選擇另行下去，僅當(dāng)搜索到達(dá)一個(gè)沒(méi)有后裔的狀態(tài)時(shí)，才選擇另一條替代路徑。一條替代路徑。5.3.3 深度優(yōu)先搜索策略v深度優(yōu)先搜索并不能保證第一次搜索到的某個(gè)狀態(tài)時(shí)的路徑深度優(yōu)先搜索并不能保證第一次搜索到的某個(gè)狀態(tài)時(shí)

22、的路徑是到這個(gè)狀態(tài)的最短路徑，為防止搜索過(guò)程沿著無(wú)益的路徑是到這個(gè)狀態(tài)的最短路徑，為防止搜索過(guò)程沿著無(wú)益的路徑擴(kuò)展下去，給出一個(gè)節(jié)點(diǎn)擴(kuò)展的最大深度擴(kuò)展下去，給出一個(gè)節(jié)點(diǎn)擴(kuò)展的最大深度深度界限深度界限。v為了保證找到解，應(yīng)選擇合適的深度限制值，或采取不斷加為了保證找到解，應(yīng)選擇合適的深度限制值，或采取不斷加大深度限制值的辦法，反復(fù)搜索，直到找到解。大深度限制值的辦法，反復(fù)搜索，直到找到解。 v與寬度優(yōu)先搜索根本的不同點(diǎn)：將擴(kuò)展的后繼節(jié)點(diǎn)放在與寬度優(yōu)先搜索根本的不同點(diǎn)：將擴(kuò)展的后繼節(jié)點(diǎn)放在OPEN表的最前端。表的最前端。 例例3 3 卒子穿陣問(wèn)題卒子穿陣問(wèn)題，要求一卒子從頂部通過(guò)下圖所要求一卒子從

23、頂部通過(guò)下圖所示的陣列到達(dá)底部。卒子行進(jìn)中不可進(jìn)入到代表敵示的陣列到達(dá)底部。卒子行進(jìn)中不可進(jìn)入到代表敵兵駐守的區(qū)域（標(biāo)注兵駐守的區(qū)域（標(biāo)注1），并不準(zhǔn)后退。假定深度），并不準(zhǔn)后退。假定深度限制值為限制值為5。 000100100100000121342134行列圖5.10陣列圖000100100100000121342134行列圖5.10陣列圖 陣列圖陣列圖 5.3.3 深度優(yōu)先搜索策略0S1S)1 ,1(2S)2,1(3S)2,2(4S)1 ,2(5S)1 ,3(6S)2,3(7S)3,2(8S)3,1(9S)2,1(14S)4,1(10S)2,2(11S)1 ,2(12S)1 ,3(13S

24、)3,2(15S)4,2(16S)4,3(17S)4,4(18S)4,1(死死解 0S1S)1 ,1(2S)2,1(3S)2,2(4S)1 ,2(5S)1 ,3(6S)2,3(7S)3,2(8S)3,1(9S)2,1(14S)4,1(10S)2,2(11S)1 ,2(12S)1 ,3(13S)3,2(15S)4,2(16S)4,3(17S)4,4(18S)4,1(死死死死深度限制深度限制解open表：S17、S18closed表：S0S16 卒子穿陣的深度優(yōu)先搜索樹卒子穿陣的深度優(yōu)先搜索樹5.3.3 深度優(yōu)先搜索策略死死死死000100100100000121342134行列圖5.10陣列圖0

25、00100100100000121342134行列圖5.10陣列圖S20(2,4)S19(2,4)S21(4,4)最優(yōu)解5.3.2 寬度優(yōu)先搜索策略重復(fù)重復(fù)OPEN表表CLOSE表表0S0 1S1，S2，S8，S18S02S2，S8，S18S1，S03S3，S8，S18S2，S1，S04S4，S7，S8，S18S3，S2，S1，S05S5，S7，S8，S18S4，S3，S2，S1，S06S6，S7，S8，S18S5，S4，S3，S2，S1，S07S8，S18S7，S6，S5，S4，S3，S2，S1，S0。 。5.3.3 深度優(yōu)先搜索策略一般情況下，深度優(yōu)先搜索法占內(nèi)存少但速度較一般情況下，深度

26、優(yōu)先搜索法占內(nèi)存少但速度較慢，廣度優(yōu)先搜索算法占內(nèi)存多但速度較快，在慢，廣度優(yōu)先搜索算法占內(nèi)存多但速度較快，在距離和深度成正比的情況下能較快地求出最優(yōu)解距離和深度成正比的情況下能較快地求出最優(yōu)解。因此在選擇用哪種算法時(shí)，要綜合考慮。決定取因此在選擇用哪種算法時(shí)，要綜合考慮。決定取舍。舍。深度搜索和寬度搜索深度搜索和寬度搜索 深度搜索與寬度搜索的控制結(jié)構(gòu)和產(chǎn)生系統(tǒng)很深度搜索與寬度搜索的控制結(jié)構(gòu)和產(chǎn)生系統(tǒng)很相似，唯一的區(qū)別在于對(duì)擴(kuò)展節(jié)點(diǎn)選取上。相似，唯一的區(qū)別在于對(duì)擴(kuò)展節(jié)點(diǎn)選取上。 由于其保留了所有的前繼節(jié)點(diǎn)，所以在產(chǎn)生后由于其保留了所有的前繼節(jié)點(diǎn)，所以在產(chǎn)生后繼節(jié)點(diǎn)時(shí)可以去掉一部分重復(fù)的節(jié)點(diǎn)，從

27、而提繼節(jié)點(diǎn)時(shí)可以去掉一部分重復(fù)的節(jié)點(diǎn)，從而提高了搜索效率。高了搜索效率。 這兩種算法每次都擴(kuò)展一個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)這兩種算法每次都擴(kuò)展一個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)，而不同的是，深度搜索下一次擴(kuò)展的是本次，而不同的是，深度搜索下一次擴(kuò)展的是本次擴(kuò)展出來(lái)的擴(kuò)展出來(lái)的子節(jié)點(diǎn)子節(jié)點(diǎn)中的一個(gè)，而廣度搜索擴(kuò)展中的一個(gè)，而廣度搜索擴(kuò)展的則是本次擴(kuò)展的節(jié)點(diǎn)的的則是本次擴(kuò)展的節(jié)點(diǎn)的兄弟節(jié)點(diǎn)兄弟節(jié)點(diǎn)。 在具體實(shí)現(xiàn)上為了提高效率在具體實(shí)現(xiàn)上為了提高效率,所以采用了不同的所以采用了不同的數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)。第5章 搜索求解策略 5.1 搜索的概念搜索的概念 5.2 狀態(tài)空間知識(shí)表示方法狀態(tài)空間知識(shí)表示方法 5.3 盲目的圖搜

28、索策略盲目的圖搜索策略5.4 啟發(fā)式圖搜索策略啟發(fā)式圖搜索策略 5.5 與與/或或圖搜索策略圖搜索策略盲目圖搜索策略特點(diǎn)：盲目圖搜索策略特點(diǎn)：v1）不需要重排）不需要重排OPEN表；表；v2）沒(méi)有啟發(fā)信息的一種搜索形式；）沒(méi)有啟發(fā)信息的一種搜索形式；v3）一般只適用于求解簡(jiǎn)單的問(wèn)題。）一般只適用于求解簡(jiǎn)單的問(wèn)題。5.4 啟發(fā)式圖搜索策略5.4 啟發(fā)式圖搜索策略5.4.1 啟發(fā)式策略啟發(fā)式策略5.4.2 啟發(fā)信息和估價(jià)函數(shù)啟發(fā)信息和估價(jià)函數(shù)5.4.3 A搜索算法搜索算法5.4.4 A*搜索算法及其特性分析搜索算法及其特性分析 為什么需要啟發(fā)式搜索？為什么需要啟發(fā)式搜索？盲目搜索的不足：盲目搜索的

29、不足：l 效率低，耗費(fèi)過(guò)多的計(jì)算時(shí)間和空間；效率低，耗費(fèi)過(guò)多的計(jì)算時(shí)間和空間；l 可能產(chǎn)生組合爆炸；可能產(chǎn)生組合爆炸； 什么可以做啟發(fā)信息？什么可以做啟發(fā)信息？ 用來(lái)簡(jiǎn)化搜索過(guò)程有關(guān)用來(lái)簡(jiǎn)化搜索過(guò)程有關(guān)具體問(wèn)題領(lǐng)域的特性信息具體問(wèn)題領(lǐng)域的特性信息叫做啟發(fā)信叫做啟發(fā)信息；息； 利用利用啟發(fā)式信息啟發(fā)式信息進(jìn)行搜索的方法就是啟發(fā)式搜索方法進(jìn)行搜索的方法就是啟發(fā)式搜索方法特點(diǎn)：重排特點(diǎn)：重排OPEN表，選擇表，選擇最有希望的節(jié)點(diǎn)最有希望的節(jié)點(diǎn)加以擴(kuò)展；加以擴(kuò)展； 種類：種類：A算法，算法，A*算法等算法等5.4 啟發(fā)式圖搜索策略5.4.1 啟發(fā)式策略運(yùn)用啟發(fā)式策略的兩種基本情況運(yùn)用啟發(fā)式策略的兩種基

30、本情況： （1）一個(gè)問(wèn)題由于在問(wèn)題陳述和數(shù)據(jù)獲取方面固有）一個(gè)問(wèn)題由于在問(wèn)題陳述和數(shù)據(jù)獲取方面固有 的模糊性，的模糊性，可能可能會(huì)使它會(huì)使它沒(méi)有一個(gè)確定的解。沒(méi)有一個(gè)確定的解。 （2）雖然一個(gè)問(wèn)題可能有確定解，但是其）雖然一個(gè)問(wèn)題可能有確定解，但是其狀態(tài)空間狀態(tài)空間 特別大，特別大，搜索中生成擴(kuò)展的狀態(tài)數(shù)會(huì)隨著搜索搜索中生成擴(kuò)展的狀態(tài)數(shù)會(huì)隨著搜索 的深度呈指數(shù)級(jí)增長(zhǎng)。的深度呈指數(shù)級(jí)增長(zhǎng)。5.4.1 啟發(fā)式策略 “啟發(fā)啟發(fā)”（heuristic）：關(guān)于發(fā)現(xiàn)和發(fā)明操作算）：關(guān)于發(fā)現(xiàn)和發(fā)明操作算子及搜索方法的研究。子及搜索方法的研究。 在狀態(tài)空間搜索中，啟發(fā)式被定義成一系列在狀態(tài)空間搜索中，啟發(fā)式被

31、定義成一系列操操作算子作算子，并能從狀態(tài)空間中選擇最有希望到達(dá)，并能從狀態(tài)空間中選擇最有希望到達(dá)問(wèn)題解的路徑。問(wèn)題解的路徑。 啟發(fā)式策略：利用與問(wèn)題有關(guān)的啟發(fā)信息進(jìn)行啟發(fā)式策略：利用與問(wèn)題有關(guān)的啟發(fā)信息進(jìn)行搜索。搜索。 例例4 4 一字棋一字棋。在九宮棋盤上，從空棋盤開(kāi)始，雙方輪流在棋盤上在九宮棋盤上，從空棋盤開(kāi)始，雙方輪流在棋盤上擺各自的棋子擺各自的棋子 或或 （每次一枚），誰(shuí)先取得三子一線（一行（每次一枚），誰(shuí)先取得三子一線（一行、一列或一條對(duì)角線）的結(jié)果就取勝。、一列或一條對(duì)角線）的結(jié)果就取勝。 5.4.1 啟發(fā)式策略 和和 能夠在棋盤中擺成的各種不同的棋局就是問(wèn)題空間能夠在棋盤中擺成的

32、各種不同的棋局就是問(wèn)題空間中的不同狀態(tài)。中的不同狀態(tài)。 9個(gè)位置上擺放個(gè)位置上擺放空，空， ， 有有 39 種棋局。種棋局。 可能的走法可能的走法 ： 9！。！。贏的幾率贏的幾率贏的幾率圖5.12 啟發(fā)式策略的運(yùn)用贏的幾率贏的幾率贏的幾率圖5.12 啟發(fā)式策略的運(yùn)用 啟發(fā)式策略的運(yùn)用啟發(fā)式策略的運(yùn)用5.4.1 啟發(fā)式策略圖5.13啟發(fā)式搜索下縮減的狀態(tài)空間啟發(fā)式搜索下縮減的狀態(tài)空間啟發(fā)式搜索下縮減的狀態(tài)空間5.4.1 啟發(fā)式策略5.4.2 啟發(fā)信息和估價(jià)函數(shù) 求解問(wèn)題中能利用的大多求解問(wèn)題中能利用的大多是非完備的啟發(fā)信息是非完備的啟發(fā)信息：（1）求解問(wèn)題系統(tǒng)不可能知道與實(shí)際問(wèn)題有關(guān)的全）求解問(wèn)

33、題系統(tǒng)不可能知道與實(shí)際問(wèn)題有關(guān)的全部信息，因而無(wú)法知道該問(wèn)題的全部狀態(tài)空間，也部信息，因而無(wú)法知道該問(wèn)題的全部狀態(tài)空間，也不可能用一套算法來(lái)求解所有的問(wèn)題。不可能用一套算法來(lái)求解所有的問(wèn)題。（2）有些問(wèn)題）有些問(wèn)題在理論上雖然存在著求解算法，但是在理論上雖然存在著求解算法，但是在工程實(shí)踐中，這些算法不是效率太低，就是根本在工程實(shí)踐中，這些算法不是效率太低，就是根本無(wú)法實(shí)現(xiàn)。無(wú)法實(shí)現(xiàn)。一字棋：一字棋：9！，西洋跳棋：！，西洋跳棋：1078，國(guó)際象棋：，國(guó)際象棋：10120，圍棋：，圍棋：10761。假設(shè)每步可以搜索一個(gè)棋局，用極限并行速度（假設(shè)每步可以搜索一個(gè)棋局，用極限并行速度（10-104年

34、年/步）來(lái)步）來(lái)處理，搜索一遍國(guó)際象棋的全部棋局也得處理，搜索一遍國(guó)際象棋的全部棋局也得1016年即年即1億億年才可以億億年才可以算完！算完！ 5.4.2 啟發(fā)信息和估價(jià)函數(shù)啟發(fā)信息按運(yùn)用的方法分類：?jiǎn)l(fā)信息按運(yùn)用的方法分類： （1）陳述性啟發(fā)信息：更準(zhǔn)確地描述狀態(tài)）陳述性啟發(fā)信息：更準(zhǔn)確地描述狀態(tài) （2）過(guò)程性啟發(fā)信息：一系列操作算子）過(guò)程性啟發(fā)信息：一系列操作算子 （3）控制性啟發(fā)信息：控制策略）控制性啟發(fā)信息：控制策略5.4.2 啟發(fā)信息和估價(jià)函數(shù) 估價(jià)函數(shù)：任務(wù)是估價(jià)函數(shù)：任務(wù)是估計(jì)待搜索結(jié)點(diǎn)的估計(jì)待搜索結(jié)點(diǎn)的“有希望有希望”程度程度，并依，并依次給它們排定次序（在次給它們排定次序（在

35、open表中）。表中）。 估價(jià)函數(shù)估價(jià)函數(shù)f (n) ：從初始結(jié)點(diǎn)經(jīng)過(guò)：從初始結(jié)點(diǎn)經(jīng)過(guò)n結(jié)點(diǎn)到達(dá)目的結(jié)點(diǎn)到達(dá)目的 結(jié)點(diǎn)的路結(jié)點(diǎn)的路徑的最小代價(jià)估計(jì)值，其一般形式是徑的最小代價(jià)估計(jì)值，其一般形式是 f (n)= g(n) + h (n) g(n)：從初始節(jié)點(diǎn)到節(jié)點(diǎn)：從初始節(jié)點(diǎn)到節(jié)點(diǎn)n的的實(shí)際代價(jià)實(shí)際代價(jià)h(n)： 從節(jié)點(diǎn)從節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)的到目標(biāo)節(jié)點(diǎn)的最優(yōu)路徑最優(yōu)路徑的估計(jì)代價(jià)的估計(jì)代價(jià)一般地，在一般地，在f(n)中，中， g(n)的比重越大，越傾向于寬度優(yōu)先搜索的比重越大，越傾向于寬度優(yōu)先搜索方式，而方式，而 h (n)的比重越大，表示啟發(fā)性能越強(qiáng)。的比重越大，表示啟發(fā)性能越強(qiáng)。 設(shè)初始節(jié)點(diǎn)設(shè)

36、初始節(jié)點(diǎn)S0和目標(biāo)節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)Sg分別如下圖的初始分別如下圖的初始棋局和目標(biāo)棋局所示。棋局和目標(biāo)棋局所示。2831647512384765初始狀態(tài)目標(biāo)狀態(tài)例例5 八數(shù)碼的估價(jià)函數(shù)八數(shù)碼的估價(jià)函數(shù)設(shè)計(jì)方法有多種，并且不同的估價(jià)函數(shù)對(duì)求解八數(shù)碼問(wèn)題有不設(shè)計(jì)方法有多種，并且不同的估價(jià)函數(shù)對(duì)求解八數(shù)碼問(wèn)題有不同的影響。同的影響。 最簡(jiǎn)單的估價(jià)函數(shù)：取一格局與目的格局相比，其位置不最簡(jiǎn)單的估價(jià)函數(shù)：取一格局與目的格局相比，其位置不符的數(shù)碼數(shù)目符的數(shù)碼數(shù)目:f(S0)=5 較好的估價(jià)函數(shù)：各數(shù)碼移到目的位置所需移動(dòng)的距離的較好的估價(jià)函數(shù)：各數(shù)碼移到目的位置所需移動(dòng)的距離的總和總和:f(S0)=6 第三種

37、估價(jià)函數(shù)：對(duì)每一對(duì)逆轉(zhuǎn)數(shù)碼乘以一個(gè)倍數(shù)。第三種估價(jià)函數(shù)：對(duì)每一對(duì)逆轉(zhuǎn)數(shù)碼乘以一個(gè)倍數(shù)。f(S0)=0 第四種估價(jià)函數(shù)：克服了僅計(jì)算數(shù)碼逆轉(zhuǎn)數(shù)目策略的局限第四種估價(jià)函數(shù)：克服了僅計(jì)算數(shù)碼逆轉(zhuǎn)數(shù)目策略的局限，將位置不符數(shù)碼數(shù)目的總和與，將位置不符數(shù)碼數(shù)目的總和與3倍數(shù)碼逆轉(zhuǎn)數(shù)目相加。倍數(shù)碼逆轉(zhuǎn)數(shù)目相加。f(S0)=0. 5.4.2 啟發(fā)信息和估價(jià)函數(shù)5.4.2 啟發(fā)信息和估價(jià)函數(shù) 估價(jià)函數(shù)：設(shè)計(jì)一個(gè)好的估價(jià)函數(shù)有相當(dāng)?shù)碾y度估價(jià)函數(shù)：設(shè)計(jì)一個(gè)好的估價(jià)函數(shù)有相當(dāng)?shù)碾y度，是一個(gè)，是一個(gè)經(jīng)驗(yàn)問(wèn)題經(jīng)驗(yàn)問(wèn)題，判斷和直覺(jué)是很重要的因素。，判斷和直覺(jué)是很重要的因素。設(shè)計(jì)估價(jià)函數(shù)的目標(biāo)是利用有限的信息做出精確設(shè)計(jì)估

38、價(jià)函數(shù)的目標(biāo)是利用有限的信息做出精確的估價(jià)的估價(jià)衡量估計(jì)函數(shù)的好壞最終標(biāo)準(zhǔn)取決于具體應(yīng)用時(shí)衡量估計(jì)函數(shù)的好壞最終標(biāo)準(zhǔn)取決于具體應(yīng)用時(shí)的搜索效果。的搜索效果。5.4.3 A搜索算法搜索算法 啟發(fā)式圖搜索法啟發(fā)式圖搜索法A算法和算法和A*算法算法 爬山法爬山法：（Pearl，1984）在搜索過(guò)程中先擴(kuò)展當(dāng)前的狀態(tài)）在搜索過(guò)程中先擴(kuò)展當(dāng)前的狀態(tài)，然后再評(píng)估他的孩子，而后選擇最佳的孩子做進(jìn)一步擴(kuò)，然后再評(píng)估他的孩子，而后選擇最佳的孩子做進(jìn)一步擴(kuò)展，展，不保留不保留他的兄弟姐妹和雙親，當(dāng)搜索遇到比其孩子更他的兄弟姐妹和雙親，當(dāng)搜索遇到比其孩子更佳的狀態(tài)則停止。佳的狀態(tài)則停止。 最佳優(yōu)先搜索：最佳優(yōu)先搜索

39、：對(duì)對(duì)OPEN表的狀態(tài)進(jìn)行排序，排序的依據(jù)表的狀態(tài)進(jìn)行排序，排序的依據(jù)是是按狀態(tài)與目標(biāo)按狀態(tài)與目標(biāo)“接近程度接近程度”的某種啟發(fā)式的某種啟發(fā)式估計(jì)，每一輪估計(jì)，每一輪循環(huán)考慮循環(huán)考慮OPEN表中最有希望的狀態(tài)。表中最有希望的狀態(tài)。 A算法：算法：使用估價(jià)函數(shù)的最佳優(yōu)先搜索。使用估價(jià)函數(shù)的最佳優(yōu)先搜索。5.4.3 A搜索算法搜索算法 A算法的基本特點(diǎn)：算法的基本特點(diǎn)： 如何尋找并設(shè)計(jì)一個(gè)與問(wèn)題有關(guān)的如何尋找并設(shè)計(jì)一個(gè)與問(wèn)題有關(guān)的 h(n) 及構(gòu)出及構(gòu)出 f(n)= h(n)+ g(n) ， 然后以然后以f(n) 的大小來(lái)排列待擴(kuò)的大小來(lái)排列待擴(kuò)展?fàn)顟B(tài)的次序，每次選擇展?fàn)顟B(tài)的次序，每次選擇f(n)

40、 值值最小者最小者進(jìn)行擴(kuò)展進(jìn)行擴(kuò)展。 open表：保留所有已生成而未擴(kuò)展的狀態(tài)。表：保留所有已生成而未擴(kuò)展的狀態(tài)。 closed表：記錄已擴(kuò)展過(guò)的狀態(tài)。表：記錄已擴(kuò)展過(guò)的狀態(tài)。 進(jìn)入進(jìn)入open表的狀態(tài)是根據(jù)其估值的大小插入到表中合適表的狀態(tài)是根據(jù)其估值的大小插入到表中合適的位置，每次的位置，每次從表中優(yōu)先取出啟發(fā)估價(jià)函數(shù)值最小的狀態(tài)加從表中優(yōu)先取出啟發(fā)估價(jià)函數(shù)值最小的狀態(tài)加以擴(kuò)展。以擴(kuò)展。 A算法流程圖算法流程圖開(kāi)始開(kāi)始把把S0放入放入OPEN表中表中,計(jì)算計(jì)算f(S0) OPEN=NIL? 選取選取OPEN表中表中f最小的節(jié)點(diǎn)最小的節(jié)點(diǎn)i放入放入CLOSED表中表中 i=G ? 擴(kuò)展擴(kuò)展i

41、得后繼節(jié)點(diǎn)得后繼節(jié)點(diǎn)j,計(jì)算計(jì)算f(j),提供返回提供返回i的指針的指針,把把節(jié)點(diǎn)節(jié)點(diǎn)j送回送回OPEN表，利用表，利用f(j)對(duì)對(duì)OPEN表進(jìn)行重表進(jìn)行重排，調(diào)整親子關(guān)系和指針。排，調(diào)整親子關(guān)系和指針。失敗失敗成功成功5.4.3 A搜索算法搜索算法YNYN5.4.3 A搜索算法搜索算法 例例6 6 利用利用A搜索算法求解八數(shù)碼問(wèn)題的搜索樹，其搜索算法求解八數(shù)碼問(wèn)題的搜索樹，其估價(jià)函數(shù)定義為估價(jià)函數(shù)定義為 f (n)= d(n) + w (n) ：狀態(tài)的深度，每步為單位代價(jià)。：狀態(tài)的深度，每步為單位代價(jià)。 ：節(jié)點(diǎn)：節(jié)點(diǎn)n的數(shù)碼格局同目標(biāo)節(jié)點(diǎn)相比，的數(shù)碼格局同目標(biāo)節(jié)點(diǎn)相比，數(shù)碼數(shù)碼不同的位置個(gè)數(shù)

42、不同的位置個(gè)數(shù)。 w( (S0)=4)=4)(nd)(nw 設(shè)初始節(jié)點(diǎn)設(shè)初始節(jié)點(diǎn)S0和目標(biāo)節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)Sg分別如下圖的初始分別如下圖的初始棋局和目標(biāo)棋局所示。棋局和目標(biāo)棋局所示。2831647512384765初始狀態(tài)目標(biāo)狀態(tài)5.4.3 A搜索算法搜索算法2 8 31 6 47 52 8 31 47 6 52 8 31 6 4 7 52 8 31 6 47 52 31 8 47 6 52 8 3 1 47 6 52 8 31 47 6 52 8 37 1 4 6 5 8 32 1 47 6 5 2 31 8 47 6 52 31 8 47 6 51 2 3 8 47 6 51 2 38 47

43、 6 51 2 37 8 4 6 5s(4)A(1+5)B(4)C(6)D(2+3)E(5)F(6)G(3+3)H(7)I(5)J(7)K(5)L(5)M(7)目標(biāo)目標(biāo)123456 open表和表和closed表內(nèi)狀態(tài)排列的變化情況表內(nèi)狀態(tài)排列的變化情況 5.4.3 A搜索算法搜索算法重重復(fù)復(fù)OPEN表表CLOSE表表0S(4) 1B(4)，A(6), C(6)S(4)2D(5)，E(5), A(6), C(6),F(6)S(4)，B(4)3E(5), A(6), C(6),F(6), G(6),H(7)S(4)，B(4), D(5)4I(5), A(6), C(6),F(6), G(6),H

44、(7), J(7)S(4)，B(4), D(5), E(5)5K(5), A(6), C(6),F(6), G(6),H(7), J(7)S(4)，B(4), D(5), E(5), I(5)6L(5), A(6), C(6),F(6), G(6),H(7), J(7), M(7) S(4)，B(4), D(5), E(5), I(5), K(5)7A(6), C(6),F(6), G(6),H(7), J(7), M(7)S(4)，B(4), D(5), E(5), I(5), K(5), L(5)L為目的狀態(tài)，成功推出，結(jié)束搜索為目的狀態(tài)，成功推出，結(jié)束搜索 假設(shè)假設(shè)f*(n)為從初始節(jié)點(diǎn)

45、為從初始節(jié)點(diǎn)S0出發(fā)，約束經(jīng)過(guò)節(jié)點(diǎn)出發(fā)，約束經(jīng)過(guò)節(jié)點(diǎn)n到達(dá)目標(biāo)節(jié)到達(dá)目標(biāo)節(jié)點(diǎn)的最小代價(jià)值。估價(jià)函數(shù)點(diǎn)的最小代價(jià)值。估價(jià)函數(shù)f(n)則是則是f*(n)的估計(jì)值。的估計(jì)值。 f*(n)由以下兩部分所組成：由以下兩部分所組成： 一部分是從初始節(jié)點(diǎn)一部分是從初始節(jié)點(diǎn)S0到節(jié)點(diǎn)到節(jié)點(diǎn)n的最小代價(jià)，記為的最小代價(jià)，記為g*(n)； 另一部分是從節(jié)點(diǎn)另一部分是從節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)的最小代價(jià)，記為到目標(biāo)節(jié)點(diǎn)的最小代價(jià)，記為h*(n)，因，因此有此有 f*(n)=g*(n) +h*(n)5.4.4 A*搜索算法搜索算法 A*算法算法1）OPEN表中的節(jié)點(diǎn)按著估價(jià)函數(shù)表中的節(jié)點(diǎn)按著估價(jià)函數(shù)f(n)=g(n)+h(n)的值的值從小到大排序從小到大排序2）g(n)是對(duì)是對(duì)g*(n)的最優(yōu)估價(jià)；的最優(yōu)估價(jià)；3）h(n)是是h*(n)的下界：的下界：h(n) h*(n)g*(n):初始節(jié)點(diǎn)到節(jié)點(diǎn)初始節(jié)點(diǎn)到節(jié)點(diǎn)n的最小代價(jià)的最小代價(jià)h*(n)：節(jié)點(diǎn)：節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的最小代價(jià)；的最小代價(jià)；（一定存在）一定存在）5.4.4 A*搜索算法搜索算法 A*算法就是對(duì)估價(jià)函數(shù)加上一些限制后得到的一算法就是對(duì)估價(jià)函數(shù)加上一些限制后得到的一種啟發(fā)式搜索算法。種啟發(fā)式搜索算法。 如果某一問(wèn)題有