ACM培訓(xùn)第八講-搜索

ACM程序設(shè)計(jì)

第八講-搜索湖南工學(xué)院張新玉zhangxinyu247@163.com搜索算法1.搜索問題2.搜索方法分類3.回溯方法4.一般圖搜索算法5.啟發(fā)式搜索算法1.搜索問題人類的思維過程，可以看作一個(gè)搜索過程。我們遇到的很多智力游戲問題，如傳教士和野人問題。有3個(gè)傳教士和3個(gè)野人來到河邊準(zhǔn)備渡河，河岸有一條船，每次最多可乘坐2個(gè)人。問傳教士為安全起見，應(yīng)如何規(guī)劃擺渡方案，使得在任何時(shí)刻，在河的兩岸以及船上傳教士人數(shù)不能少于野人的人數(shù)？對(duì)這個(gè)問題，在每一次渡河后，都會(huì)有幾種渡河方案供選擇，究竟哪種方案最有利？這就是搜索問題。1.搜索問題對(duì)這類問題，一般我們都轉(zhuǎn)換為狀態(tài)空間的搜索問題。如傳教士和野人問題，可用在河左岸的傳教士人數(shù)、野人人數(shù)和船的情況來表示。即，初始時(shí)狀態(tài)為（3，3，1），結(jié)束狀態(tài)為（0，0，0），而中間狀態(tài)可表示為（2，2，0）、（3，2，1）等等。

初始狀態(tài)結(jié)束狀態(tài)

LR

LRm30m03c30c03B10B011.搜索問題由此，可以看出這類問題的解，就是一個(gè)合法狀態(tài)的序列，其中序列中第一個(gè)狀態(tài)是問題的初始狀態(tài)，而最后一個(gè)狀態(tài)則是問題的結(jié)束狀態(tài)。如圖所示即搜索問題的示意圖：SgS0解路徑搜索空間全狀態(tài)空間2.搜索方法分類

不可撤回方法試探性方法回溯方法圖搜索方法3.回溯方法回溯方法，屬于盲目搜索的一種，它是這樣一種策略：首先將規(guī)則給出一個(gè)固定的排序，在搜索時(shí)，對(duì)當(dāng)前狀態(tài)依次檢測(cè)每一條規(guī)則，在當(dāng)前狀態(tài)未使用過的規(guī)則中找到第一條可應(yīng)用規(guī)則，應(yīng)用于當(dāng)前狀態(tài)，得到的新狀態(tài)重新設(shè)置為當(dāng)前狀態(tài)，并重復(fù)以上搜索。如果當(dāng)前狀態(tài)無規(guī)則可用，或者所有規(guī)則已經(jīng)被試探過仍未找到問題的解，則將當(dāng)前狀態(tài)的前一個(gè)狀態(tài)（即直接生成該狀態(tài)的狀態(tài)）設(shè)置為當(dāng)前狀態(tài)。重復(fù)以上搜索，直到找到問題的解，或已試探過所有可能仍找不到問題的解為止。3.回溯方法例：皇后問題QQQQ3.回溯方法()()3.回溯方法()()((1,1))Q3.回溯方法()()((1,1))((1,1)(2,3))QQ3.回溯方法()()((1,1))((1,1)(2,3))Q3.回溯方法()()((1,1))((1,1)(2,3))((1,1)(2,4))QQ3.回溯方法()()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))QQQ3.回溯方法()()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))QQ3.回溯方法()()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q3.回溯方法()()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))3.回溯方法()()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))((1,2))Q3.回溯方法()()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))((1,2))((1,2)(2,4))QQ3.回溯方法()()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))((1,2))((1,2)(2,4))((1,2)(2,4)(3,1))QQQ3.回溯方法()()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))((1,2))((1,2)(2,4))((1,2)(2,4)(3,1))((1,2)(2,4)(3,1)(4,3))QQQQ3.回溯方法遞歸的思想：當(dāng)前狀態(tài)目標(biāo)狀態(tài)g3.回溯方法算法描述：BACKTRACK1（DATALIST）

DATALIST：從初始到當(dāng)前的狀態(tài)表（逆向）

返回值：從當(dāng)前狀態(tài)到目標(biāo)狀態(tài)的路徑 （以規(guī)則表的形式表示） 或FAIL。3.回溯方法1, DATA:=FIRST(DATALIST)2, IFMENBER(DATA,TAIL(DATALIST)) RETURNFAIL;

3, IFTERM(DATA)RETURNNIL;4, IFDEADEND(DATA)RETURNFAIL;5, IFLENGTH(DATALIST)>BOUND RETURNFAIL;6, RULES:=APPRULES(DATA);3.回溯方法7,LOOP:IFNULL(RULES)RETURNFAIL;8, R:=FIRST(RULES);9, RULES:=TAIL(RULES);10, RDATA:=GEN(R,DATA);11, RDATALIST:=CONS(RDATA,DATALIST);12, PATH:=BACKTRCK1(RDATALIST)13, IFPATH=FAILGOLOOP;14, RETURNCONS(R,PATH);4.一般圖搜索算法問題的引入：回溯搜索：只保留從初始狀態(tài)到當(dāng)前狀態(tài)的一條路徑圖搜索：保留所有已經(jīng)搜索過的路徑如果控制系統(tǒng)保留所有規(guī)則應(yīng)用后生成并鏈接起來的狀態(tài)記錄圖,則稱工作在這種方式下的控制系統(tǒng)使用了圖搜索策略。實(shí)際上圖搜索策略是實(shí)現(xiàn)從一個(gè)隱含圖中,生成一部分確實(shí)含有一個(gè)目標(biāo)節(jié)點(diǎn)的顯式表示的子圖搜索過程。4.一般圖搜索算法問題的引入：回溯搜索：只保留從初始狀態(tài)到當(dāng)前狀態(tài)的一條路徑圖搜索：保留所有已經(jīng)搜索過的路徑如果控制系統(tǒng)保留所有規(guī)則應(yīng)用后生成并鏈接起來的狀態(tài)記錄圖,則稱工作在這種方式下的控制系統(tǒng)使用了圖搜索策略。實(shí)際上圖搜索策略是實(shí)現(xiàn)從一個(gè)隱含圖中,生成一部分確實(shí)含有一個(gè)目標(biāo)節(jié)點(diǎn)的顯式表示的子圖搜索過程。4.一般圖搜索算法一些基本概念：節(jié)點(diǎn)深度： 根節(jié)點(diǎn)深度=0

其它節(jié)點(diǎn)深度=父節(jié)點(diǎn)深度+101234.一般圖搜索算法一些基本概念：路徑:設(shè)一節(jié)點(diǎn)序列為(n0,n1,…,nk)，對(duì)于i=1,…,k，若節(jié)點(diǎn)ni-1具有一個(gè)后繼節(jié)點(diǎn)ni，則該序列稱為從n0到nk的路徑。路徑的耗散值:

一條路徑的耗散值等于連接這條路徑各節(jié)點(diǎn)間所有耗散值的總和。用C(ni,nj)表示從ni到nj的路徑的耗散值。擴(kuò)展一個(gè)節(jié)點(diǎn):

生成出該節(jié)點(diǎn)的所有后繼節(jié)點(diǎn)，并給出它們之間的耗散值。這一過程稱為“擴(kuò)展一個(gè)節(jié)點(diǎn)”。4.一般圖搜索算法一般性圖搜索算法：1:G←S,OPEN←(S);建立一個(gè)搜索圖G,它只含有初始節(jié)點(diǎn)S,建立一個(gè)OPEN表(今后它用于存儲(chǔ)生成的節(jié)點(diǎn)),開始它只含有初始節(jié)點(diǎn)S。2:CLOSED←();建立一個(gè)CLOSED表(今后它用于存儲(chǔ)已擴(kuò)展節(jié)點(diǎn)或?qū)⒁獢U(kuò)展的某個(gè)節(jié)點(diǎn)),它的初始狀態(tài)為空表。3:LOOP:ifOPEN=()thenreturnFAIL;進(jìn)入循環(huán)。如果OPEN表已空,說明沒有節(jié)點(diǎn)可擴(kuò)展,就返回FAIL,即失敗。4:n←FIRST(OPEN),CLOSED←(n,CLOSED);從OPEN表中取出一個(gè)節(jié)點(diǎn)n,將其放入CLOSED表中。5:ifn∈目標(biāo)集thenreturn[s→…→n];如果n為目標(biāo)節(jié)點(diǎn),則沿著G中從n到s的鏈指針得出一條路徑,并以此返回。4.一般圖搜索算法一般性圖搜索算法(續(xù))：6:M←expand(n),G'←G,G←{M,G'};擴(kuò)展節(jié)點(diǎn)n,建立集合M,并把M中的節(jié)點(diǎn)作為n的后繼者加入G中。7:

對(duì)M中的所有節(jié)點(diǎn)m(1)ifm

G'then建立指針m→n,OPEN←CONS(M,OPEN);對(duì)M中原來不在G中的節(jié)點(diǎn)建立一個(gè)從這些節(jié)點(diǎn)到n的指針,并把它們加入OPEN表。

(2)ifm∈OPENthen根據(jù)其擴(kuò)展路徑確定是否應(yīng)將它們的指針指向n。

(3)ifm∈CLOSEDthen根據(jù)其擴(kuò)展路徑確定是否應(yīng)改變m的后代的指針。8:

對(duì)OPEN中的節(jié)點(diǎn)按某種原則重新排序；9:GOLOOP；4.一般圖搜索算法節(jié)點(diǎn)類型：…...…...…...…...…...mjmkml4.一般圖搜索算法廣度優(yōu)先搜索法：該方法從初始節(jié)點(diǎn)開始,順序擴(kuò)展生成下一級(jí)各子節(jié)點(diǎn),放在OPEN表中已有的節(jié)點(diǎn)后面(實(shí)現(xiàn)先生成的子節(jié)點(diǎn)先擴(kuò)展),然后從OPEN表中提取最前的一個(gè)節(jié)點(diǎn)檢查是否是目標(biāo)節(jié)點(diǎn),否則再擴(kuò)展,再重復(fù)上述操作。這種方法認(rèn)為同一級(jí)各節(jié)點(diǎn)對(duì)問題求解的價(jià)值是同等的,因而對(duì)全部節(jié)點(diǎn)沿廣度進(jìn)行橫向掃描,按各節(jié)點(diǎn)生成的先后次序,先生成、先檢查、先擴(kuò)展,沿廣度遍歷所有節(jié)點(diǎn)。這種方法只要問題有解,即若樹圖上存在目標(biāo)節(jié)點(diǎn),經(jīng)搜索一定能找到。所以,廣度優(yōu)先搜索法是完備的,是一種推理算法。但是,在問題大節(jié)點(diǎn)多,且目標(biāo)節(jié)點(diǎn)距離初始節(jié)點(diǎn)較遠(yuǎn)時(shí)將會(huì)產(chǎn)生許多無用節(jié)點(diǎn),搜索效率低,還可能產(chǎn)生組合爆炸。因此,這種方法較適宜問題不大的環(huán)境中。4.一般圖搜索算法廣度優(yōu)先搜索算法：1:G:=G0(G0=s),OPEN:=(s),CLOSED:=();2:LOOP:IFOPEN=()THENEXIT(FAIL);3:n:=FIRST(OPEN);4:IFGOAL(n)THENEXIT(SUCCESS);5:REMOVE(n,OPEN),ADD(n,CLOSED);6:EXPAND(n)→{mi},G:=ADD(mi,G);7:IF目標(biāo)在{mi}中THENEXIT(SUCCESS);8:

ADD(OPEN,mj),

并標(biāo)記mj到n的指針;9:GOLOOP;

4.一般圖搜索算法例:8數(shù)碼難題

在一個(gè)3×3的方框內(nèi)放有8個(gè)編號(hào)的小方塊，緊鄰空位的小方塊可以移入到空位上，通過平移小方塊可將某一布局變換為另一布局。請(qǐng)給出從初始狀態(tài)到目標(biāo)狀態(tài)移動(dòng)小方塊的操作序列。231847651238476523184765231847652831476523184765283147652831647528314765283164752831647528371465832147652814376528314576123784651238476512567312384765目標(biāo)82341876544.一般圖搜索算法廣度優(yōu)先搜索的性質(zhì)：當(dāng)問題有解時(shí)，一定能找到解當(dāng)問題為單位耗散值，且問題有解時(shí)，一定能找到最優(yōu)解方法與問題無關(guān)，具有通用性效率較低屬于圖搜索方法4.一般圖搜索算法深度優(yōu)先搜索法：該方法從初始節(jié)點(diǎn)開始,順序擴(kuò)展生成下一級(jí)各子節(jié)點(diǎn),放在OPEN表中已有的節(jié)點(diǎn)前面(實(shí)現(xiàn)后生成的子節(jié)點(diǎn)先擴(kuò)展),然后從OPEN表中提取最前的一個(gè)節(jié)點(diǎn)檢查是否是目標(biāo)節(jié)點(diǎn),否則再擴(kuò)展,再重復(fù)上述操作。這種方法每一次擴(kuò)展最晚生成的子節(jié)點(diǎn),沿著最晚生成的子節(jié)點(diǎn)分支,逐級(jí)縱向深入發(fā)展。這種方法搜索一旦進(jìn)入某個(gè)分支,就將沿著該分支一直向下搜索。如果目標(biāo)節(jié)點(diǎn)恰好在此分支上,則可較快地得到解。但是,如果目標(biāo)節(jié)點(diǎn)不在此分支上,不回溯就不可能得到解。所以,深度優(yōu)先搜索是不完備的,只是推理步驟。如果回溯,不難證明其平均效率與廣度優(yōu)先搜索法相同。因此,深度優(yōu)先搜索法如果沒有啟發(fā)信息,很難有實(shí)用價(jià)值。4.一般圖搜索算法深度優(yōu)先搜索算法：1:G:=G0(G0=s),OPEN:=(s),CLOSED:=();2:LOOP:IFOPEN=()THENEXIT(FAIL);3:n:=FIRST(OPEN);4:IFGOAL(n)THENEXIT(SUCCESS);5:REMOVE(n,OPEN),ADD(n,CLOSED);6:IFDEPTH(n)≥DmGOLOOP;7:EXPAND(n)→{mi},G:=ADD(mi,G);8:IF目標(biāo)在{mi}中THENEXIT(SUCCESS);9:

ADD(mj,OPEN),

并標(biāo)記mj到n的指針;10:GOLOOP;231847652318476528314765231847652831476528316475283147652831647528316475283714658321476528143765283145761237846512384765283641752831675483214765283714652814376528314576123456789abcd12384765目標(biāo)4.一般圖搜索算法深度優(yōu)先搜索的性質(zhì)：一般不能保證找到最優(yōu)解當(dāng)深度限制不合理時(shí)，可能找不到解，可以將算法改為可變深度限制最壞情況時(shí)，搜索空間等同于窮舉與回溯法的差別：圖搜索是一個(gè)通用的與問題無關(guān)的方法5.啟發(fā)式搜索算法引入:利用知識(shí)來引導(dǎo)搜索，達(dá)到減少搜索范圍，降低問題復(fù)雜度的目的。希望引入啟發(fā)知識(shí)，在保證找到最佳解的情況下，盡可能減少搜索范圍，提高搜索效率啟發(fā)信息的強(qiáng)度強(qiáng)：降低搜索工作量，但可能導(dǎo)致找不到最優(yōu)解弱：一般導(dǎo)致工作量加大，極限情況下變?yōu)槊つ克阉?，但可能可以找到最?yōu)解。5.啟發(fā)式搜索算法基本思想:

定義一個(gè)評(píng)價(jià)函數(shù)f，對(duì)當(dāng)前的搜索狀態(tài)進(jìn)行評(píng)估，找出一個(gè)最有希望的節(jié)點(diǎn)來擴(kuò)展。評(píng)價(jià)函數(shù)的格式：

f(x)=g(x)+h(x)g*(x)：為從初始節(jié)點(diǎn)S。到節(jié)點(diǎn)x的最短路徑的耗散值h*(x)：從x到目標(biāo)節(jié)點(diǎn)Sg的最短路徑的耗散值f*(x)=g*(x)+h*(x)：從S。經(jīng)過x到Sg的最短路徑的耗散值g(x)、h(x)、f(x)分別是g*(x)、h*(x)、f*(x)的估計(jì)值5.啟發(fā)式搜索算法A算法:1,OPEN:=(s),f(s):=g(s)+h(s);2,LOOP:IFOPEN=()THENEXIT(FAIL);3,n:=FIRST(OPEN);4,IFGOAL(n)THENEXIT(SUCCESS);5,REMOVE(n,OPEN),ADD(n,CLOSED);6,EXPAND(n)→{Mi},

計(jì)算f(n,mi):=g(n,mi)+h(mi);5.啟發(fā)式搜索算法A算法(續(xù)): ADD(mj,OPEN),標(biāo)記mj到n的指針；

IFf(n,mk)<f(mk)THENf(mk):=f(n,mk),

標(biāo)記mk到n的指針；

IFf(n,ml)<f(ml,)THENf(ml):=f(n,ml),

標(biāo)記ml到n的指針, ADD(ml,OPEN);7,OPEN中的節(jié)點(diǎn)按f值從小到大排序；8,GOLOOP；5.啟發(fā)式搜索算法一個(gè)A算法的例子:定義評(píng)價(jià)函數(shù)：

f(n)=g(n)+h(n) g(n)為從初始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的耗散值

h(n)為當(dāng)前節(jié)點(diǎn)“不在位”的將牌數(shù)2831647512384765h計(jì)算舉例 h(n)=42

831

6475123457682831647528314765283164752831647523184765283147652831476528371465832147652318476523184765123847651238476512378465s(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)1234563.4.3典型的啟發(fā)式圖搜索算法A*算法:如果對(duì)一般性圖搜索算法作以下限制,則它成為A*算法:(1)OPEN表中的節(jié)點(diǎn)按估價(jià)函數(shù)f(x)=g(x)+h(x)的值從小至大進(jìn)行排序.(2)g(x)是到目前為止,從S。到x的一條最小耗散值路徑的耗散值,是作為從S。到x最小耗散值路徑的耗散值g*(x)的估計(jì)值,g(x)>0。

(3)h(x)是h*(x)的下界,即對(duì)所有x均有h(x)≤h*(x)。而h*(x)是從節(jié)點(diǎn)x到目標(biāo)節(jié)點(diǎn)的最小代價(jià),若有多個(gè)目標(biāo)節(jié)點(diǎn),則為其中最小的一個(gè)。3.4.3典型的啟發(fā)式圖搜索算法A*條件舉例:8數(shù)碼問題h1(n)=“不在位”的將牌數(shù)h2(n)=將牌“不在位”的距離和2

831

647512345768將牌1：1將牌2：1將牌6：1將牌8：2283164752831476528316475283164752318476528314765283147652318476523184765123847651238476512378465s(5)A(7)B(5)C(7)D(7)E(5)F(7)G(5)H(7)I(5)J(5)K(7)目標(biāo)12345h2(n)=將牌“不在位”的距離和搜索過程實(shí)驗(yàn)要求

編寫一程序?qū)崿F(xiàn)以A*算法搜索八數(shù)碼難題的解決步驟：

在一個(gè)3×3的方框內(nèi)放有8個(gè)編號(hào)的小方塊，緊鄰空位的小方塊可以移入到空位上，通過平移小方塊可將某一布局變換為另一布局（如圖所示）。2831675412384765A*算法回顧啟發(fā)函數(shù):8數(shù)碼問題h1(n)=“不在位”的將牌數(shù)h2(n)=將牌“不在位”的距離和2

831

647512345768將牌1：1將牌2：1將牌6：1將牌8：2移動(dòng)規(guī)則的表示規(guī)則集合:

移動(dòng)一塊將牌(即走一步)就使?fàn)顟B(tài)發(fā)生改變.有4種走法:空格上移、空格下移、空格左移、空格右移。規(guī)則集可形式化表示如下:

設(shè)Sij記矩陣第i行第j列的數(shù)碼，i0,j0

記空格所在的行、列數(shù)值，即Si0j0=0，則

ifj0-1≥1thenSi0j0=Si0(j0-1),Si0(j0-1)=0(Si0j0向左）

ifi0-1≥1thenSi0j0=S(i0-1)j0,S(i0-1)j0=0(Si0j0向上）

ifj0+1≤3thenSi0j0=Si0(j0+1),Si0(j0+1)=0(Si0j0向右）

ifi0+1≤3thenSi0j0=S(i0+1)j0,S(i0+1)j0=0(Si0j0向下）節(jié)點(diǎn)的表示structnode{ intstate[3][3];//數(shù)碼狀態(tài)

structnode*parent;//指向父節(jié)點(diǎn)的指針

structnode*next;//指向下一節(jié)點(diǎn)的指針

intinherit;//啟發(fā)函數(shù)值

intdepth;//搜索深度

intf_value;//評(píng)價(jià)函數(shù)值};程序設(shè)計(jì)細(xì)節(jié)程序會(huì)用到的全局變量structnode*close,*open,*goal;//分別指向close表、open表和目標(biāo)節(jié)點(diǎn)的指針intend[3][3]={{1,2,3},{8,0,4},{7,6,5}};//用于比較的目標(biāo)節(jié)點(diǎn)的數(shù)碼狀態(tài)intsucceed=0;//判斷是否成功搜索到目標(biāo)狀態(tài)程序設(shè)計(jì)細(xì)節(jié)初始節(jié)點(diǎn)的創(chuàng)建structnode*p;inti,j,h;p=new(structnode);p->parent=NULL;p->next=NULL;p->depth=0;p->inherit=0;printf("請(qǐng)輸入初始狀態(tài):\n");for(i=0;i<3;i++)for(j=0;j<3;j++){ scanf("%d",&h); p->state[i][j]=h;}h=heuristic(p);p->f_value=h;程序設(shè)計(jì)細(xì)節(jié)處理open=p;close=NULL;goal=NULL;

/*對(duì)OPEN表進(jìn)行擴(kuò)展*/expend();程序設(shè)計(jì)細(xì)節(jié)結(jié)果的輸出if(succeed==0){printf("不能得到目標(biāo)狀態(tài)！\n");}else{p=goal;

i=0;while(p!=NULL){proc[i]=p->inherit;p=p->parent;i=i+1;}程序設(shè)計(jì)細(xì)節(jié)結(jié)果的輸出(續(xù)）

printf("操作步驟如下所示：\n");for(j=i;j>=0;j--){h=proc[j];switch(h){case1:

printf("第%d步為:左移\n",i-j-1);break; case2:printf("第%d步為:上移\n",i-j-1);break; case3:

printf("第%d步為:右移\n",i-j-1);break; case4:printf(“第%d步為:下移\n”,i-j-1)；break;}}}啟發(fā)函數(shù)的計(jì)算intheuristic(structnode*x){

/*計(jì)算啟發(fā)函數(shù)*/

intvalue=0;intnum,loc,flag;

for(inti=0;i<3;i++)

for(intj=0;j<3;j++)

{

num=x->state[i][j]; flag=0;

for(intk=0;k<3;k++)

{

for(intl=0;l<3;l++) if(end[k][l]==num) {

loc=abs(i-k)+abs(j-l);value=value+loc;

flag=1;

break; } if(flag==1)break;

} }

returnvalue;}擴(kuò)展過程voidexpend(){

/*從OPEN表中選取第一個(gè)結(jié)點(diǎn)進(jìn)行擴(kuò)展*/

introw,col,h;

structnode*p,*q;

while((open!=NULL)&&(succeed==0))

{

p=open;

open=open->next;

p->next=close;

close=p;

for(inti=0;i<3;i++)

for(intj=0;j<