第4章搜索策略

人工智能原理篇搜索策略第四章本章導(dǎo)讀現(xiàn)實(shí)世界中多數(shù)問題都是非結(jié)構(gòu)化的，一般不能用直接求解的方法來求解這樣的問題，而只能利用已有的知識(shí)一步一步地摸索著前進(jìn)。因此，常常使用基于搜索策略的方法來求解問題。搜索策略是人工智能的基本求解策略之一，已在人工智能各領(lǐng)域得到了廣泛應(yīng)用。本章主要介紹基于狀態(tài)空間表示法的搜索策略，包括盲目搜索策略和啟發(fā)式搜索策略。學(xué)習(xí)目標(biāo)熟悉搜索的基本內(nèi)容。理解搜索策略的思想。掌握寬度優(yōu)先搜索、深度優(yōu)先搜索和等代價(jià)搜索等盲目搜索策略。掌握A搜索和A*搜索等啟發(fā)式搜索策略。目錄

4搜索概述盲目搜索策略啟發(fā)式搜索策略010203搜索概述01搜索的概念4.1.1搜索就是根據(jù)問題的實(shí)際情況，按照一定的策略或規(guī)則，從知識(shí)庫中尋找可利用的知識(shí)，從而構(gòu)造出一條代價(jià)較小的推理路線，使問題得到解決的過程。搜索是人工智能中的一個(gè)核心技術(shù)，是推理不可分割的一部分，它直接關(guān)系到智能系統(tǒng)的性能和運(yùn)行效率。在搜索問題中，主要的工作是找到正確的搜索策略。搜索策略反映了狀態(tài)空間或問題空間擴(kuò)展的方法，也決定了狀態(tài)或問題的訪問順序。在人工智能中，通過運(yùn)用搜索策略解決問題的基本思想是：首先把問題的初始狀態(tài)（即起始節(jié)點(diǎn)）作為當(dāng)前狀態(tài)，選擇適用的操作符對其進(jìn)行操作，生成一組子狀態(tài)（即后繼節(jié)點(diǎn)），然后檢查目標(biāo)狀態(tài)是否在其中出現(xiàn)。若出現(xiàn)，則搜索成功，找到了問題的解；若未出現(xiàn)，則按某種搜索策略從已生成的狀態(tài)中再選一個(gè)狀態(tài)作為當(dāng)前狀態(tài)。重復(fù)上述過程，直到目標(biāo)狀態(tài)出現(xiàn)或者不再有可供操作的狀態(tài)及操作符為止。在運(yùn)用搜索策略求解問題的過程中，涉及的數(shù)據(jù)結(jié)構(gòu)除了狀態(tài)空間圖之外，還需要兩個(gè)輔助的數(shù)據(jù)結(jié)構(gòu)，即存放已訪問但未擴(kuò)展節(jié)點(diǎn)的OPEN表，以及存放已擴(kuò)展節(jié)點(diǎn)的CLOSED表。狀態(tài)空間圖的搜索過程如左圖所示。搜索過程4.1.2

（6）擴(kuò)展節(jié)點(diǎn)n，生成后繼節(jié)點(diǎn)集合M，并將集合M中的成員作為n的后繼節(jié)點(diǎn)添加入搜索圖中。（7）針對M中后繼節(jié)點(diǎn)的不同情況，分別做如下處理。①對那些未曾在搜索圖中出現(xiàn)過的（既未曾在OPEN表中，也未在CLOSED表中出現(xiàn)過）M成員，設(shè)置其父節(jié)點(diǎn)指針指向n，并加入OPEN表中。②對那些原來已在搜索圖中出現(xiàn)過，但還沒有擴(kuò)展的（已經(jīng)在OPEN表或CLOSED表中出現(xiàn)過）M成員，確定是否需要將其原來的父節(jié)點(diǎn)更改為n。③對那些先前已在搜索圖中出現(xiàn)過，并已經(jīng)擴(kuò)展了的（已在CLOSED表中）M成員，確定是否需要修改其后繼節(jié)點(diǎn)指向父節(jié)點(diǎn)的指針。若修改了其父節(jié)點(diǎn)，則將該節(jié)點(diǎn)從CLOSED表中移出，重新加入OPEN表中。（8）按某一方式或按某個(gè)估價(jià)值，重排OPEN表。繼續(xù)執(zhí)行步驟（3）。知識(shí)庫

添磚加瓦在搜索過程中需要解決的基本問題有：（1）搜索過程是否一定能找到一個(gè)解。（2）當(dāng)搜索過程找到一個(gè)解時(shí)，找到的是否是最佳解。（3）搜索過程的時(shí)間與空間復(fù)雜性如何。（4）搜索過程是否能終止運(yùn)行或是否會(huì)陷入一個(gè)死循環(huán)。根據(jù)搜索過程中是否運(yùn)用與問題有關(guān)的信息，可以將搜索策略分為盲目搜索策略和啟發(fā)式搜索策略。在搜索過程中對OPEN表的節(jié)點(diǎn)排序，主要目的是希望從未擴(kuò)展節(jié)點(diǎn)中選出一個(gè)最具有希望的節(jié)點(diǎn)作為下一個(gè)擴(kuò)展節(jié)點(diǎn)使用。若此時(shí)的排序是任意的或者是盲目的，則為盲目搜索；若排序是以各種啟發(fā)式思想或其他準(zhǔn)則為依據(jù)的，則為啟發(fā)式搜索。搜索策略4.1.3盲目搜索策略02盲目搜索策略又稱無信息搜索策略，也就是說，在搜索過程中，只按照預(yù)先規(guī)定的搜索策略進(jìn)行搜索，而沒有任何中間信息來改變這些策略。常用的盲目搜索策略有寬度優(yōu)先搜索、深度優(yōu)先搜索和等代價(jià)搜索等。

4.2.1寬度優(yōu)先搜索寬度優(yōu)先搜索寬度優(yōu)先搜索的搜索過程可用如左圖所示的算法描述。寬度優(yōu)先搜索算法【例4-1】

貓捉老鼠問題，貓位于A處，它發(fā)現(xiàn)K處有一只老鼠（見左圖），請用寬度優(yōu)先搜索算法幫貓尋找捕捉路線。貓和老鼠的位置表示【解】使用寬度優(yōu)先搜索算法解決貓捉老鼠問題的步驟如下。（1）貓所在的位置A是起始節(jié)點(diǎn)，將A放入OPEN表中。（2）判斷該起始節(jié)點(diǎn)A是否為一目標(biāo)節(jié)點(diǎn)，若是，則求得一個(gè)解并成功退出；否則繼續(xù)。節(jié)點(diǎn)A不是老鼠所在的位置，所以不是目標(biāo)節(jié)點(diǎn)。（3）判斷OPEN表是否為空表，若是空表，則沒有解，失敗退出；否則繼續(xù)。OPEN表中有節(jié)點(diǎn)A，非空，繼續(xù)執(zhí)行。（4）把OPEN表中的第一個(gè)節(jié)點(diǎn)（記為節(jié)點(diǎn)n）移出，并放入CLOSED表中。將節(jié)點(diǎn)A從OPEN表中移出，并放入CLOSED表中。（5）判斷節(jié)點(diǎn)n是否有后繼節(jié)點(diǎn)，若有，則繼續(xù)；否則，轉(zhuǎn)向（3）。節(jié)點(diǎn)A有后繼節(jié)點(diǎn)，繼續(xù)執(zhí)行。（6）擴(kuò)展節(jié)點(diǎn)n，把節(jié)點(diǎn)n的所有后繼節(jié)點(diǎn)放入OPEN表的末端，并提供從這些后繼節(jié)點(diǎn)回到父節(jié)點(diǎn)n的指針。即擴(kuò)展節(jié)點(diǎn)A，其后繼節(jié)點(diǎn)有B和C，將它們放入OPEN表的末端，并提供回到父節(jié)點(diǎn)A的指針。（7）判斷剛產(chǎn)生的這些后繼節(jié)點(diǎn)中是否存在一個(gè)目標(biāo)節(jié)點(diǎn)，若存在，則找到一個(gè)解，成功退出。解可從目標(biāo)節(jié)點(diǎn)到起始節(jié)點(diǎn)的返回指針中得到。否則轉(zhuǎn)向（3）。后繼節(jié)點(diǎn)B和C都不是目標(biāo)節(jié)點(diǎn)，轉(zhuǎn)向（3）。循環(huán)執(zhí)行上述操作，其OPEN表和CLOSED表的狀態(tài)變化如表所示。OPEN表和CLOSED表的狀態(tài)變化循環(huán)次數(shù)OPEN表CLOSED表0（初始化）A空1B、CA2C、D、EA、B3D、E、F、GA、B、C4E、F、G、HA、B、C、D5F、G、HA、B、C、D、E6G、H、I、JA、B、C、D、E、F7H、I、J、KA、B、C、D、E、F、G從表可以看出，在第7次循環(huán)中，步驟（7）判斷G

產(chǎn)生的后繼節(jié)點(diǎn)K是目標(biāo)節(jié)點(diǎn)。此時(shí)，找到一個(gè)解，成功退出。便可得到貓捉老鼠的捕捉路線為。

該搜索結(jié)束后得到的搜索樹如左圖所示。寬度優(yōu)先搜索樹

神經(jīng)元4.2.2深度優(yōu)先搜索添磚加瓦節(jié)點(diǎn)深度的定義如下。（1）起始節(jié)點(diǎn)（即根節(jié)點(diǎn)）的深度為0。例如，圖中節(jié)點(diǎn)A的深度為0。（2）任何其他節(jié)點(diǎn)的深度等于其父節(jié)點(diǎn)深度加1。例如，圖中節(jié)點(diǎn)D的深度是2，等于其父節(jié)點(diǎn)B的深度1加1。深度相等的節(jié)點(diǎn)可以任意排列。例如，圖中節(jié)點(diǎn)B和C的排列也可以是先C后B。深度優(yōu)先搜索含有深度界限的深度優(yōu)先搜索的搜索過程可用如左圖所示的算法描述。有界深度優(yōu)先搜索算法【例】請用含有深度界限的深度優(yōu)先搜索算法解決例1中的貓捉老鼠問題?！窘狻渴褂煤猩疃冉缦薜纳疃葍?yōu)先搜索算法解決貓捉老鼠問題的步驟如下。（1）貓所在的位置A是起始節(jié)點(diǎn)，將A放入OPEN表中。（2）判斷該起始節(jié)點(diǎn)A是否為一目標(biāo)節(jié)點(diǎn)，若是，則求得一個(gè)解并成功退出；否則繼續(xù)。節(jié)點(diǎn)A不是老鼠所在的位置，所以不是目標(biāo)節(jié)點(diǎn)。（3）判斷OPEN表是否為空表，若是空表，則沒有解，失敗退出；否則繼續(xù)。OPEN表中有節(jié)點(diǎn)A，非空，繼續(xù)執(zhí)行。（4）把OPEN表中的第一個(gè)節(jié)點(diǎn)（記為節(jié)點(diǎn)n）移出，并放入CLOSED表中。將節(jié)點(diǎn)A從OPEN表中移出，并放入CLOSED表中。（5）判斷節(jié)點(diǎn)n的深度是否等于深度界限，若等于，則轉(zhuǎn)向（3）；否則繼續(xù)。針對貓捉老鼠問題，將深度界限設(shè)為3。第1次循環(huán)中節(jié)點(diǎn)A的深度為0，不等于深度界限。（6）判斷節(jié)點(diǎn)n是否有后繼節(jié)點(diǎn)，若有，則繼續(xù)；否則，轉(zhuǎn)向（3）。節(jié)點(diǎn)A有后繼節(jié)點(diǎn)，繼續(xù)執(zhí)行（7）擴(kuò)展節(jié)點(diǎn)n，把節(jié)點(diǎn)n的所有后繼節(jié)點(diǎn)放入OPEN表的前端，并提供從這些后繼節(jié)點(diǎn)回到父節(jié)點(diǎn)n的指針。擴(kuò)展節(jié)點(diǎn)A，把A的后繼節(jié)點(diǎn)B和C放入OPEN表的前端。（8）判斷剛產(chǎn)生的這些后繼節(jié)點(diǎn)中是否存在一個(gè)目標(biāo)節(jié)點(diǎn)，若存在，則找到一個(gè)解，成功退出。解可從目標(biāo)節(jié)點(diǎn)到起始節(jié)點(diǎn)的返回指針中得到。否則轉(zhuǎn)向（3）。后繼節(jié)點(diǎn)B和C都不是目標(biāo)節(jié)點(diǎn)，轉(zhuǎn)向（3）。循環(huán)執(zhí)行上述操作，第1次循環(huán)結(jié)束后，OPEN表的節(jié)點(diǎn)依次是B、C，然后進(jìn)行第2次循環(huán)，擴(kuò)展第一個(gè)節(jié)點(diǎn)B，其后繼節(jié)點(diǎn)有D和E，將它們放入OPEN表的前端，并提供回到父節(jié)點(diǎn)B的指針。

可見，經(jīng)過第2次循環(huán)后，OPEN表的節(jié)點(diǎn)依次為D、E、C。在整個(gè)搜索過程中，OPEN表和CLOSED表的狀態(tài)變化如左表所示。循環(huán)次數(shù)OPEN表CLOSED表0（初始化）A空1B、CA2D、E、CA、B3H、E、CA、B、D4E、CA、B、D、H5CA、B、D、H、E6F、GA、B、D、H、E、C7I、J、GA、B、D、H、E、C、F8J、GA、B、D、H、E、C、F、I9GA、B、D、H、E、C、F、I、J10KA、B、D、H、E、C、F、I、J、GOPEN表和CLOSED表的狀態(tài)變化從表可以看出，在第10次循環(huán)中，步驟（8）判斷節(jié)點(diǎn)G產(chǎn)生的后繼節(jié)點(diǎn)K是目標(biāo)節(jié)點(diǎn)。此時(shí)，找到一個(gè)解，成功退出。便可得到貓捉老鼠的捕捉路線為。

該搜索結(jié)束后得到的搜索樹如圖所示。深度優(yōu)先搜索樹知識(shí)庫深度優(yōu)先搜索策略也是一個(gè)通用的與問題無關(guān)的方法，其性質(zhì)有：（1）一般不能保證找到路徑最短的解。（2）當(dāng)深度界限設(shè)置不合理時(shí)，可能找不到解。（3）在最壞情況下，搜索空間等同于窮舉。

4.2.3等代價(jià)搜索

等代價(jià)搜索算法

貓和老鼠位置表示

循環(huán)執(zhí)行上述操作，第1次循環(huán)結(jié)束后，OPEN表的節(jié)點(diǎn)依次是B、C，然后進(jìn)行第2次循環(huán)，擴(kuò)展路徑代價(jià)值最小的節(jié)點(diǎn)C，其后繼節(jié)點(diǎn)有F和G，將它們放入OPEN表中，并提供回到父節(jié)點(diǎn)C的指針?？梢姡?jīng)過第2次循環(huán)后，OPEN表的節(jié)點(diǎn)依次為B、F、G。在整個(gè)搜索過程中，OPEN表和CLOSED表的狀態(tài)變化如表所示。OPEN表和CLOSED表的狀態(tài)變化

等代價(jià)搜索樹某小說中講述了一個(gè)曲折離奇的故事。在故事中，某人得到了藏有皇家寶藏秘密的寶匣，但是寶匣上面有一個(gè)9宮格拼圖密碼（見左圖），只有將圖片拼完整才可以打開寶匣。

請采用盲目搜索策略完成拼圖任務(wù)。寶匣4.2.4案例：寶匣上的拼圖【解】（1）用數(shù)字表示9宮格內(nèi)的圖片塊，則該拼圖的初始狀態(tài)如圖1所示，目標(biāo)狀態(tài)如圖2所示。（2）移動(dòng)拼圖中空白的圖塊，可執(zhí)行的操作有上、下、左、右，其中，需要約束空白圖塊不能移出9宮格之外。圖1拼圖的初始狀態(tài)圖2拼圖的目標(biāo)狀態(tài)（3）使用寬度優(yōu)先搜索完成拼圖任務(wù)，其搜索順序如圖所示。拼圖任務(wù)的寬度優(yōu)先搜索樹啟發(fā)式搜索策略03

啟發(fā)式搜索策略又稱有信息搜索策略，是指在搜索過程中，利用與問題有關(guān)的信息，引導(dǎo)搜索朝最有利的方向進(jìn)行，從而加快搜索的速度，提高搜索效率。啟發(fā)式搜索策略中涉及的重要內(nèi)容有啟發(fā)性信息和估價(jià)函數(shù)，常用的啟發(fā)式搜索策略有A搜索和A*搜索。啟發(fā)式搜索策略的主要依據(jù)是問題自身的啟發(fā)性信息。

啟發(fā)性信息是指可確定搜索方向，簡化搜索過程，且可反映問題特性的控制性信息。在啟發(fā)式搜索過程中，主要根據(jù)與問題有關(guān)的啟發(fā)性信息估計(jì)各個(gè)節(jié)點(diǎn)的代價(jià)，從而確定每一次搜索的方向。啟發(fā)性信息又是通過估價(jià)函數(shù)而作用于搜索過程的。估價(jià)函數(shù)常用于估計(jì)節(jié)點(diǎn)的代價(jià)，即通過充分利用啟發(fā)性信息估計(jì)出經(jīng)過當(dāng)前節(jié)點(diǎn)搜索到目標(biāo)節(jié)點(diǎn)的代價(jià)。4.3.1啟發(fā)性信息和估價(jià)函數(shù)

添磚加瓦啟發(fā)性信息按其作用可分為3種。（1）用于確定要擴(kuò)展的下一個(gè)節(jié)點(diǎn)，避免盲目地?cái)U(kuò)展節(jié)點(diǎn)。（2）在擴(kuò)展節(jié)點(diǎn)的過程中，用于決定生成哪些后繼節(jié)點(diǎn)，避免盲目地生成所有可能節(jié)點(diǎn)。（3）用于確定應(yīng)從搜索樹中修剪或刪除的節(jié)點(diǎn)，避免盲目地保留“最不具有希望”的節(jié)點(diǎn)。

4.3.2A搜索

全局擇優(yōu)搜索的基本思想是當(dāng)確定下一個(gè)擴(kuò)展節(jié)點(diǎn)時(shí)，利用估價(jià)函數(shù)計(jì)算OPEN表中每個(gè)節(jié)點(diǎn)的估價(jià)值，然后從OPEN表的全部節(jié)點(diǎn)中選擇一個(gè)值最小的節(jié)點(diǎn)作為下一個(gè)要考察的節(jié)點(diǎn)。由于該搜索是在OPEN表的全部節(jié)點(diǎn)范圍內(nèi)選擇下一個(gè)要考察的節(jié)點(diǎn)，選擇范圍全面，故稱為全局擇優(yōu)搜索。全局擇優(yōu)搜索的搜索過程可用如圖所示的算法描述。全局擇優(yōu)搜索算法1．全局擇優(yōu)搜索【例】貓捉老鼠問題，在貓去捕捉老鼠的路程中，老鼠察覺到危險(xiǎn)，于是，老鼠從K處出發(fā)經(jīng)過P處逃到O處，如左圖所示。

其中，兩節(jié)點(diǎn)間弧的數(shù)值代表貓的體力消耗值，請用全局擇優(yōu)搜索算法幫貓尋找捕捉路線。貓和老鼠位置表示

OPEN表和CLOSED表的狀態(tài)變化

全局擇優(yōu)搜索樹

局部擇優(yōu)搜索算法2．局部擇優(yōu)搜索

OPEN表和CLOSED表的狀態(tài)變化

4.3.3A*搜索

（7）把這些后繼節(jié)點(diǎn)都送入OPEN表中，然后按照估價(jià)函數(shù)值從小到大的順序?qū)PEN表中的全部節(jié)點(diǎn)進(jìn)行排