第5章 搜索與回溯算法(c++版)

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

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

2、該方向再向前試探。按此原則不斷搜索回溯再搜索，直到找到新的出路或從原路返回入口處無解為止。遞歸回溯法算法框架[一]intSearch(intk){for(i=1;i<=算符種數(shù);i++)if(滿足條件){保存結(jié)果if(到目的地)輸出解;elseSearch(k+1);恢復(fù)：保存結(jié)果之前的狀態(tài){回溯一步}}}遞歸回溯法算法框架[二]intSearch(intk){if(到目的地)輸出解;elsefor(i=1;i<=算符種數(shù);i++)if(滿足條件){保存結(jié)果;Search(k+1);恢復(fù)：保存結(jié)果之前的狀態(tài){回溯一步}}}【例1】素數(shù)環(huán):從1到20這20個數(shù)擺成一個環(huán)，要求相鄰的兩個

3、數(shù)的和是一個素數(shù)?！舅惴ǚ治觥糠浅Ｃ黠@，這是一道回溯的題目。從1開始，每個空位有20種可能，只要填進去的數(shù)合法：與前面的數(shù)不相同；與左邊相鄰的數(shù)的和是一個素數(shù)。第20個數(shù)還要判斷和第1個數(shù)的和是否素數(shù)?！舅惴鞒獭?、數(shù)據(jù)初始化；2、遞歸填數(shù)：判斷第i個數(shù)填入是否合法；A、如果合法：填數(shù)；判斷是否到達目標(biāo)（20個已填完）：是，打印結(jié)果；不是，遞歸填下一個；B、如果不合法：選擇下一種可能；【參考程序】#include#include#include#includeusingnamespacestd;boolb[21]=

4、{0};inttotal=0,a[21]={0};intsearch(int);//回溯過程intprint();//輸出方案boolpd(int,int);//判斷素數(shù)intmain(){search(1);cout<

5、elsesearch(t+1);b[i]=0;}}intprint(){total++;cout<<"<"<";for(intj=1;j<=20;j++)cout<sqrt(i))return1;elsereturn0;}【例2】設(shè)有n個整數(shù)的集合｛1,2,…,n｝，從中取出任意r個數(shù)進行排列（r#include#i

6、ncludeusingnamespacestd;intnum=0,a[10001]={0},n,r;boolb[10001]={0};intsearch(int);//回溯過程intprint();//輸出方案intmain(){cout<<"inputn,r:";cin>>n>>r;search(1);cout<<"number="<

7、search(k+1);b[i]=0;}}intprint(){num++;for(inti=1;i<=r;i++)cout<