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

ACM程序設(shè)計

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

不可撤回方法試探性方法回溯方法圖搜索方法3.回溯方法回溯方法，屬于盲目搜索的一種，它是這樣一種策略：首先將規(guī)則給出一個固定的排序，在搜索時，對當(dāng)前狀態(tài)依次檢測每一條規(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)的前一個狀態(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)使用了圖搜索策略。實際上圖搜索策略是實現(xiàn)從一個隱含圖中,生成一部分確實含有一個目標(biāo)節(jié)點的顯式表示的子圖搜索過程。4.一般圖搜索算法問題的引入：回溯搜索：只保留從初始狀態(tài)到當(dāng)前狀態(tài)的一條路徑圖搜索：保留所有已經(jīng)搜索過的路徑如果控制系統(tǒng)保留所有規(guī)則應(yīng)用后生成并鏈接起來的狀態(tài)記錄圖,則稱工作在這種方式下的控制系統(tǒng)使用了圖搜索策略。實際上圖搜索策略是實現(xiàn)從一個隱含圖中,生成一部分確實含有一個目標(biāo)節(jié)點的顯式表示的子圖搜索過程。4.一般圖搜索算法一些基本概念：節(jié)點深度： 根節(jié)點深度=0

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

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

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

對M中的所有節(jié)點m(1)ifm

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

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

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

對OPEN中的節(jié)點按某種原則重新排序；9:GOLOOP；4.一般圖搜索算法節(jié)點類型：…...…...…...…...…...mjmkml4.一般圖搜索算法廣度優(yōu)先搜索法：該方法從初始節(jié)點開始,順序擴(kuò)展生成下一級各子節(jié)點,放在OPEN表中已有的節(jié)點后面(實現(xiàn)先生成的子節(jié)點先擴(kuò)展),然后從OPEN表中提取最前的一個節(jié)點檢查是否是目標(biāo)節(jié)點,否則再擴(kuò)展,再重復(fù)上述操作。這種方法認(rèn)為同一級各節(jié)點對問題求解的價值是同等的,因而對全部節(jié)點沿廣度進(jìn)行橫向掃描,按各節(jié)點生成的先后次序,先生成、先檢查、先擴(kuò)展,沿廣度遍歷所有節(jié)點。這種方法只要問題有解,即若樹圖上存在目標(biāo)節(jié)點,經(jīng)搜索一定能找到。所以,廣度優(yōu)先搜索法是完備的,是一種推理算法。但是,在問題大節(jié)點多,且目標(biāo)節(jié)點距離初始節(jié)點較遠(yuǎn)時將會產(chǎn)生許多無用節(jié)點,搜索效率低,還可能產(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ù)碼難題

在一個3×3的方框內(nèi)放有8個編號的小方塊，緊鄰空位的小方塊可以移入到空位上，通過平移小方塊可將某一布局變換為另一布局。請給出從初始狀態(tài)到目標(biāo)狀態(tài)移動小方塊的操作序列。231847651238476523184765231847652831476523184765283147652831647528314765283164752831647528371465832147652814376528314576123784651238476512567312384765目標(biāo)82341876544.一般圖搜索算法廣度優(yōu)先搜索的性質(zhì)：當(dāng)問題有解時，一定能找到解當(dāng)問題為單位耗散值，且問題有解時，一定能找到最優(yōu)解方法與問題無關(guān)，具有通用性效率較低屬于圖搜索方法4.一般圖搜索算法深度優(yōu)先搜索法：該方法從初始節(jié)點開始,順序擴(kuò)展生成下一級各子節(jié)點,放在OPEN表中已有的節(jié)點前面(實現(xiàn)后生成的子節(jié)點先擴(kuò)展),然后從OPEN表中提取最前的一個節(jié)點檢查是否是目標(biāo)節(jié)點,否則再擴(kuò)展,再重復(fù)上述操作。這種方法每一次擴(kuò)展最晚生成的子節(jié)點,沿著最晚生成的子節(jié)點分支,逐級縱向深入發(fā)展。這種方法搜索一旦進(jìn)入某個分支,就將沿著該分支一直向下搜索。如果目標(biāo)節(jié)點恰好在此分支上,則可較快地得到解。但是,如果目標(biāo)節(jié)點不在此分支上,不回溯就不可能得到解。所以,深度優(yōu)先搜索是不完備的,只是推理步驟。如果回溯,不難證明其平均效率與廣度優(yōu)先搜索法相同。因此,深度優(yōu)先搜索法如果沒有啟發(fā)信息,很難有實用價值。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)深度限制不合理時，可能找不到解，可以將算法改為可變深度限制最壞情況時，搜索空間等同于窮舉與回溯法的差別：圖搜索是一個通用的與問題無關(guān)的方法5.啟發(fā)式搜索算法引入:利用知識來引導(dǎo)搜索，達(dá)到減少搜索范圍，降低問題復(fù)雜度的目的。希望引入啟發(fā)知識，在保證找到最佳解的情況下，盡可能減少搜索范圍，提高搜索效率啟發(fā)信息的強(qiáng)度強(qiáng)：降低搜索工作量，但可能導(dǎo)致找不到最優(yōu)解弱：一般導(dǎo)致工作量加大，極限情況下變?yōu)槊つ克阉?，但可能可以找到最?yōu)解。5.啟發(fā)式搜索算法基本思想:

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

f(x)=g(x)+h(x)g*(x)：為從初始節(jié)點S。到節(jié)點x的最短路徑的耗散值h*(x)：從x到目標(biāo)節(jié)點Sg的最短路徑的耗散值f*(x)=g*(x)+h*(x)：從S。經(jīng)過x到Sg的最短路徑的耗散值g(x)、h(x)、f(x)分別是g*(x)、h*(x)、f*(x)的估計值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},

計算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é)點按f值從小到大排序；8,GOLOOP；5.啟發(fā)式搜索算法一個A算法的例子:定義評價函數(shù)：

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

h(n)為當(dāng)前節(jié)點“不在位”的將牌數(shù)2831647512384765h計算舉例 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*算法:如果對一般性圖搜索算法作以下限制,則它成為A*算法:(1)OPEN表中的節(jié)點按估價函數(shù)f(x)=g(x)+h(x)的值從小至大進(jìn)行排序.(2)g(x)是到目前為止,從S。到x的一條最小耗散值路徑的耗散值,是作為從S。到x最小耗散值路徑的耗散值g*(x)的估計值,g(x)>0。

(3)h(x)是h*(x)的下界,即對所有x均有h(x)≤h*(x)。而h*(x)是從節(jié)點x到目標(biāo)節(jié)點的最小代價,若有多個目標(biāo)節(jié)點,則為其中最小的一個。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)=將牌“不在位”的距離和搜索過程實驗要求

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

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

831

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

移動一塊將牌(即走一步)就使?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é)點的表示structnode{ intstate[3][3];//數(shù)碼狀態(tài)

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

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

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

intdepth;//搜索深度

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

/*對OPEN表進(jìn)行擴(kuò)展*/expend();程序設(shè)計細(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è)計細(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ù)的計算intheuristic(structnode*x){

/*計算啟發(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表中選取第一個結(jié)點進(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<