資源描述：
《回溯與搜索初步.ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、回溯與搜索初步第一部分 回溯一、回溯的概念從問題的某種可能情況出發(fā)，搜索所有能到達(dá)的可能情況，然后以其中一種可能的情況為新的出發(fā)點，繼續(xù)向下探索，當(dāng)所有可能情況都探索過且都無法到達(dá)目標(biāo)的時候，再回退到上一個出發(fā)點，繼續(xù)探索另一個可能情況，這種不斷回頭尋找目標(biāo)的方法稱為“回溯法”。一、回溯的概念回溯算法是一種有條不紊的搜索問題答案的方法，是一種能避免不必要搜索的窮舉式的搜索算法，其基本思想就是窮舉搜索。常用于查找問題的解集或符合某些限制條件的最佳解集。一、回溯的概念回溯算法常被用來解決自然數(shù)排列問題、皇后問題、迷宮問題、數(shù)的拆分、0/1背包問題、騎士問題、貨船裝箱
2、問題和圖形覆蓋問題等。下面我們來看一段走迷宮的演示，初步體會一下回溯的思路。二、回溯的一般描述procedurerbacktrack(k);beginifk>nthenreturnelseforeachx(k)，如果x(k)∈t(x(1)…x(k-1))且b(x(1)…x(k))=truedobeginifx(1)…x(k)是一個解thenwrite(x(1)…x(k)elserbacktrack(k+1);end;end;二、回溯的一般描述procedurebacktrack(n);begink:=1;whilek>0andk<=ndoif對于沒有試過的值x(
3、k)，x(k)∈t(x(1)…x(k-1))且b(x(1)…x(k))=truethenbeginifx(1)…x(k)是一個解thenwrite(x(1)…x(k));inc(k);endelsedec(k);//回溯end;三、回溯的一般步驟首先需要為問題定義一個解空間（solutionspace），這個空間必須至少包含問題的一個解；然后我們需要組織解空間，以便它能被容易地搜索。典型的組織方法是圖或樹。最后對這個空間即可按深度優(yōu)先的方法從開始節(jié)點進(jìn)行搜索。三、回溯的一般步驟開始節(jié)點既是一個活節(jié)點又是一個E-節(jié)點（expansionnode、擴(kuò)展節(jié)點）。從E-
4、節(jié)點可移動到一個新節(jié)點。如果能從當(dāng)前的E-節(jié)點移動到一個新節(jié)點，那么這個新節(jié)點將變成一個活節(jié)點和新的E-節(jié)點，舊的E-節(jié)點仍是一個活節(jié)點。如果不能移到一個新節(jié)點，當(dāng)前的E-節(jié)點就“死”了（即不再是一個活節(jié)點），那么便只能返回到最近被考察的活節(jié)點（回溯），這個活節(jié)點變成了新的E-節(jié)點。當(dāng)我們已經(jīng)找到了答案或者回溯盡了所有的活節(jié)點時，搜索過程結(jié)束。三、回溯的一般步驟定義一個解空間，它包含問題的解；用適于搜索的方式組織該空間；用深度優(yōu)先法搜索該空間，利用限界函數(shù)避免移動到不可能產(chǎn)生解的子空間。四、應(yīng)用舉例—n皇后問題我們在前面已經(jīng)討論過n皇后問題，現(xiàn)在我們用回溯的思路
5、來分析一下n皇后問題，看看是否能枚舉較少的排布。我們?nèi)耘f規(guī)定第k個皇后位于第k行。既然回溯算法是由一個節(jié)點開始擴(kuò)展的，因此我們現(xiàn)在一個一個的把皇后放到棋盤上。n皇后問題首先要把第一個皇后放到棋盤上由于第一個皇后有n列可以放，因此可擴(kuò)展出n種情況。先選其中一列放下這個皇后；然后開始放第二個皇后。同樣第二個皇后也有n列可以放，因此也能擴(kuò)展出n種情況，但第二個皇后可能會和第一個皇后發(fā)生攻擊，而一旦發(fā)生攻擊，就沒有必要往下擴(kuò)展第三個皇后，而如果沒有發(fā)生攻擊，則繼續(xù)放第三個皇后；依此類推，直到n個皇后全都放下后，即得到一組可行解。擴(kuò)展全部完成后即可得到結(jié)果。n皇后問題n皇
6、后問題n皇后問題的解空間就應(yīng)該是1～n全排列的一部分。解空間的長度是n。解空間的組織形式是一棵n叉樹，一個可行的解就是從根節(jié)點到葉子節(jié)點的一條路徑?？刂撇呗詣t是當(dāng)前皇后與前面所有的皇后都不同列和不同對角線。n皇后問題（邊界判定）functioncheck(pos:integer):boolean;vari:integer;begincheck:=true;fori:=1topos-1doif(x[pos]=x[i])or(abs(x[pos]-x[i])=abs(pos-i))thenbegincheck:=false;break;end;end;n皇后問題（遞
7、歸）proceduresearch(k:integer);vari:integer;beginifk>nthen//是否前n個皇后都已經(jīng)放下inc(count)else//還有皇后沒放fori:=1tondo//從第1列開始逐列嘗試beginx[k]:=i;//把第k個皇后放在第i列ifcheck(k)then//第k個皇后是否可以放在第i列search(k+1);//可以放，繼續(xù)處理第k+1個皇后end;end;n皇后問題（非遞歸）top:=1;//從第一個皇后開始嘗試while(top>0)do//當(dāng)還有活動節(jié)點時循環(huán)if(top>n)then//是否n個皇
8、后都放置在棋盤了begi
