第5章--搜索與回溯算法.ppt

《第5章--搜索與回溯算法.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、第五章搜索與回溯算法搜索與回溯是計(jì)算機(jī)解題中常用的算法，很多問(wèn)題無(wú)法根據(jù)某種確定的計(jì)算法則來(lái)求解，可以利用搜索與回溯的技術(shù)求解。回溯是搜索算法中的一種控制策略。它的基本思想是：為了求得問(wèn)題的解，先選擇某一種可能情況向前探索，在探索過(guò)程中，一旦發(fā)現(xiàn)原來(lái)的選擇是錯(cuò)誤的，就退回一步重新選擇，繼續(xù)向前探索，如此反復(fù)進(jìn)行，直至得到解或證明無(wú)解。如迷宮問(wèn)題：進(jìn)入迷宮后，先隨意選擇一個(gè)前進(jìn)方向，一步步向前試探前進(jìn),如果碰到死胡同，說(shuō)明前進(jìn)方向已無(wú)路可走，這時(shí)，首先看其它方向是否還有路可走，如果有路可走，則沿該方向再向前試探；如果已無(wú)路可走，則返回一步，再看其它方向是否還有路可走；如果有路可走

2、，則沿該方向再向前試探。按此原則不斷搜索回溯再搜索，直到找到新的出路或從原路返回入口處無(wú)解為止。遞歸回溯法算法框架[一]procedureSearch(k:integer);beginfori:=1to算符種數(shù)Doif滿足條件thenbegin保存結(jié)果if到目的地then輸出解elseSearch(k+1);恢復(fù)：保存結(jié)果之前的狀態(tài){回溯一步}end;end;遞歸回溯法算法框架[二]procedureSearch(k:integer);beginif到目的地then輸出解elsefori:=1to算符種數(shù)Doif滿足條件thenbegin保存結(jié)果Search(k+1,參數(shù)表);

3、end;end;【例1】奇數(shù)環(huán):從1到6這6個(gè)數(shù)擺成一個(gè)環(huán)，要求相鄰的兩個(gè)數(shù)的和是一個(gè)奇數(shù)?！舅惴ǚ治觥糠浅Ｃ黠@，這是一道回溯的題目。從1開(kāi)始，每個(gè)空位有6種可能，只要填進(jìn)去的數(shù)合法：與前面的數(shù)不相同；與左邊相鄰的數(shù)的和是一個(gè)奇數(shù)。第6個(gè)數(shù)還要判斷和第1個(gè)數(shù)的和是否奇數(shù)?！舅惴鞒獭?、數(shù)據(jù)初始化；2、遞歸填數(shù)：判斷第J種可能是否合法；A、如果合法：填數(shù)；判斷是否到達(dá)目標(biāo)（6個(gè)已填完）：是，打印結(jié)果；不是，遞歸填下一個(gè)；B、如果不合法：選擇下一種可能；【參考程序】programex5_1;框架[一]vara:array[0..20]ofinteger;b:array[0..20

4、]ofboolean;total:longint;procedureprint;//輸出方案varj:integer;begininc(total);write('<',total,'>:');forj:=1to6dowrite(a[j],'');writeln;end;procedureSearch(t:integer);//回溯過(guò)程vari:integer;beginfori:=1to6do//有20個(gè)數(shù)可選ifodd(a[t-1]+i)andb[i]then//判斷與前一個(gè)數(shù)是否構(gòu)成奇數(shù)及該數(shù)是否可用begina[t]:=i;b[i]:=false;ift=6thenbe

5、ginifodd(a[6]+a[1])thenprint;endelseSearch(t+1);b[i]:=true;end;end;BEGINfillchar(b,sizeof(b),#1);//b數(shù)組賦初值為T(mén)ruetotal:=0;Search(1);write('total:',total);//輸出總方案數(shù)END.【例1】素?cái)?shù)環(huán):從1到20這20個(gè)數(shù)擺成一個(gè)環(huán)，要求相鄰的兩個(gè)數(shù)的和是一個(gè)素?cái)?shù)。【算法分析】非常明顯，這是一道回溯的題目。從1開(kāi)始，每個(gè)空位有20種可能，只要填進(jìn)去的數(shù)合法：與前面的數(shù)不相同；與左邊相鄰的數(shù)的和是一個(gè)素?cái)?shù)。第20個(gè)數(shù)還要判斷和第1個(gè)數(shù)的和是否

6、素?cái)?shù)。【算法流程】1、數(shù)據(jù)初始化；2、遞歸填數(shù)：判斷第J種可能是否合法；A、如果合法：填數(shù)；判斷是否到達(dá)目標(biāo)（20個(gè)已填完）：是，打印結(jié)果；不是，遞歸填下一個(gè)；B、如果不合法：選擇下一種可能；【參考程序】programex5_1;框架[一]vara:array[0..20]ofinteger;b:array[0..20]ofboolean;total:longint;functionpd(x,y:integer):boolean;//判斷素?cái)?shù)vark,i:integer;begink:=2;i:=x+y;pd:=false;while(k<=trunc(sqrt(i)))and

7、(imodk<>0)doinc(k);ifk>trunc(sqrt(i))thenpd:=true;end;procedureprint;//輸出方案varj:integer;begininc(total);write('<',total,'>:');forj:=1to20dowrite(a[j],'');writeln;end;procedureSearch(t:integer);//回溯過(guò)程vari:integer;beginfori:=1to20do//有20個(gè)數(shù)可選ifpd(a[t-