回溯算法解迷宮問題（C語言）

1、回溯算法解迷宮問題(C語言)回溯法也稱為試探法,該方法首放棄關于問題規(guī)模大小的限制,并將問題的候選解按某一順序逐一枚舉和試驗.當發(fā)現(xiàn)當前候選解不可能是解時,就選擇下一個候選解;倘若當前候選解除了還不滿足問題規(guī)模要求外,滿足所有其他要求時,繼續(xù)擴大當前候選解的規(guī)模,并繼續(xù)試探.如果當前候選解滿足包括問題規(guī)模在內(nèi)的所有要求時,該候選解就是問題的一個解.在回溯法中,放棄當前候選解,尋找下一個候選解的過程稱為回溯.擴大當前候選解的規(guī)模,并繼續(xù)試探的過程成為向前試探.為了確保程序能夠終止,調(diào)整時,必須保證曾被放棄過的填數(shù)序列不被再次試驗,即要求按某種有序模型生成填數(shù)序列.給解的候選者設定一個被檢驗的順序

2、,按這個順序逐一生成候選者并檢驗.對于迷宮問題,我想用回溯法的難點就在如何為解空間排序,以確保曾被放棄過的填數(shù)序列不被再次試驗.在二維迷宮里面,從出發(fā)點開始,每個點按四鄰域算,按照右,上,左,下的順序搜索下一落腳點,有路則進,無路即退,前點再從下一個方向搜索,即可構成一有序模型.下表即迷宮  1,1,1,1,1,1,1,1,1,1,     0,0,0,1,0,0,0,1,0,1,     1,1,0,1,0,0,0,1,0,1,     1,0,0,0,0,1,1,0,0,1,  &

3、#160;  1,0,1,1,1,0,0,0,0,1,     1,0,0,0,1,0,0,0,0,0,     1,0,1,0,0,0,1,0,0,1,     1,0,1,1,1,0,1,1,0,1,     1,1,0,0,0,0,0,0,0,1,     1,1,1,1,1,1,1,1,1,1從出發(fā)點開始,按序查找下一點所選點列構成有序數(shù)列,如果4個方向都搜遍都無路走,就回退,并置前點的方向加1,依此類推. 1

4、0;2 3 4 5 6 7 8 9 10 x 1 1 1 2 3 3 3 2 . y 0 1 2 2 2 3 4 4 . c 1 1 3 3 1 1 2 1 .#include<stdio.h> #inclu

5、de<stdlib.h> #define n1 10 #define n2 10 typedef struct node int x; /存x坐標int y; /存Y坐標int c;  /存該點可能的下點所在的方向,1表示向右,2向上,3向左,4向右linkstack; linkstack top100; /迷宮矩陣int mazen1n2=1,1,1,1,1,1,1,1,1,1,     0,0,0,1,0,0,0,1,0,1,     1,1,0,1,0,0,0,1,0,1,   

6、0; 1,0,0,0,0,1,1,0,0,1,     1,0,1,1,1,0,0,0,0,1,     1,0,0,0,1,0,0,0,0,0,     1,0,1,0,0,0,1,0,0,1,     1,0,1,1,1,0,1,1,0,1,     1,1,0,0,0,0,0,0,0,1,     1,1,1,1,1,1,1,1,1,1,; int i,j,k,m=0;main() /初始化top,置所有方向數(shù)

7、為左for(i=0;i<n1*n2;i+) topi.c=1;printf("the maze is:n");/打印原始迷宮矩陣 for(i=0;i<n1;i+)  for(j=0;j<n2;j+)  printf(mazeij?"* ":"  ");  printf("n"); i=0;topi.x=1;topi.y=0;maze10=2;/*回溯算法*/do if(topi.c<5)    /還可以向前試探&

8、#160;  if(topi.x=5 && topi.y=9) /已找到一個組合     /打印路徑   printf("The way %d is:n",m+);   for(j=0;j<=i;j+)        printf("(%d,%d)->",topj.x,topj.y);    

9、;  printf("n");   /打印選出路徑的迷宮   for(j=0;j<n1;j+)         for(k=0;k<n2;k+)          if(mazejk=0) printf("  ");     else i

10、f(mazejk=2)  printf("O ");     else printf("* ");        printf("n");        mazetopi.xtopi.y=0;   topi.c = 1;   i-;   topi.c

11、 += 1;   continue;    switch (topi.c)   /向前試探     case 1:         if(mazetopi.xtopi.y+1=0)           i+;    &#

12、160; topi.x=topi-1.x;      topi.y=topi-1.y+1;      mazetopi.xtopi.y=2;          else           topi.c += 1;    

13、;      break;       case 2:         if(mazetopi.x-1topi.y=0)           i+;      topi.x=topi-1.x-1; &

14、#160;    topi.y=topi-1.y;      mazetopi.xtopi.y=2;          else           topi.c += 1;         

15、0;break;       case 3:         if(mazetopi.xtopi.y-1=0)           i+;      topi.x=topi-1.x;      topi.y=t

16、opi-1.y-1;      mazetopi.xtopi.y=2;          else           topi.c += 1;          break;    

17、60;  case 4:         if(mazetopi.x+1topi.y=0)           i+;      topi.x=topi-1.x+1;      topi.y=topi-1.y;    &

18、#160; mazetopi.xtopi.y=2;          else           topi.c += 1;          break;        else 

19、0; /回溯   if(i=0) return;   /已找完所有解  mazetopi.xtopi.y=0;  topi.c = 1;  i-;  topi.c += 1; while(1);排列組合與回溯算法KuiBing感謝Bamboo、LeeMaRS的幫助關鍵字 遞歸 DFS 前言 這篇論文主要針對排列組合對回溯算法展開討論，在每一個討論之后，還有相關的推薦題。在開始之前，我們先應該看一下回溯算法的概念，所謂回溯：就是搜索一棵狀態(tài)樹的過程，這個過程

20、類似于圖的深度優(yōu)先搜索（DFS），在搜索的每一步（這里的每一步對應搜索樹的第i層）中產(chǎn)生一個正確的解，然后在以后的每一步搜索過程中，都檢查其前一步的記錄，并且它將有條件的選擇以后的每一個搜索狀態(tài)（即第i+1層的狀態(tài)節(jié)點）。需掌握的基本算法：排列：就是從n個元素中同時取r個元素的排列，記做P(n,r)。（當r=n時，我們稱P(n,n)=n!為全排列）例如我們有集合OR = 1,2,3,4,那么n = |OR| = 4,切規(guī)定r=3，那么P(4,3)就是：1,2,3; 1,2,4; 1,3,2; 1,3,4;1,4,2;1,4,3;2,1,3;2,1,4; 2,3,1; 2,3,4; 2,4,1;

21、 2,4,3; 3,1,2; 3,1,4; 3,2,1; 3,2,4; 3,4,1; 3,4,2; 4,1,2; 4,1,3; 4,2,1; 4,2,3; 4,3,1; 4,3,2算法如下：int  n, r;char usedMaxN;int  pMaxN;void permute(int pos) int i;/*如果已是第r個元素了，則可打印r個元素的排列 */    if (pos=r)         for (i=0; i<r; i+) 

22、           cout << (pi+1);        cout << endl;        return;        for (i=0; i<n; i+)        if (

23、!usedi) /*如果第i個元素未用過*/*使用第i個元素，作上已用標記，目的是使以后該元素不可用*/            usedi+;/*保存當前搜索到的第i個元素*/            ppos = i;/*遞歸搜索*/           permute(pos+

24、1); /*恢復遞歸前的值，目的是使以后改元素可用*/ usedi-;         可重排列：就是從任意n個元素中，取r個可重復的元素的排列。例如，對于集合OR=1,1,2,2, n = |OR| = 4, r = 2,那么排列如下：1,1; 1,2; 1,2; 1,1; 1,2; 1,2; 2,1; 2,1; 2,2; 2,1; 2,1; 2,2則可重排列是：1,1; 1,2; 2,1; 2,2.算法如下：#define FREE -1int n, r;/*使元素有序*/int EMaxN

25、 = 0,0,1,1,1; int PMaxN;char usedMaxN; void permute(int pos)int i;/*如果已選了r個元素了，則打印它們*/    if (pos=r)          for (i=0; i<r; i+)            cout << Pi;    &

26、#160;   cout << endl;        return;    /*標記下我們排列中的以前的元素表明是不存在的*/    Ppos = FREE;    for (i=0; i<n; i+)/*如果第I個元素沒有用過，并且與先前的不同*/        if (!usedi && Ei!=Ppos)

27、             usedi+; /*使用這個元素*/            Ppos = Ei; /*選擇現(xiàn)在元素的位置*/            permute(pos+1); /*遞歸搜索*/     &#

28、160;      usedi-; /*恢復遞歸前的值*/         組合：從n個不同元素中取r個不重復的元素組成一個子集，而不考慮其元素的順序，稱為從n個中取r個的無重組合，例如OR = 1,2,3,4, n = 4, r = 3則無重組合為：1,2,3; 1,2,4; 1,3,4; 2,3,4.算法如下：int n, r;int C5;char used5; void combine(int pos, int h)int i;/*如果已選了r個元

29、素了，則打印它們*/    if (pos=r)         for (i=0; i<r; i+)            cout<< Ci;        cout<< endl;        return;&#

30、160;       for (i=h; i<=n-r+pos; i+) /*對于所有未用的元素*/        if (!usedi) /*把它放置在組合中*/            Cpos = i;/*使用該元素*/ usedi+;/*搜索第i+1個元素*/     combine(pos+1,i+1);

31、/*恢復遞歸前的值*/ usedi-;         可重組合：類似于可重排列。例 給出空間中給定n(n<10)個點，畫一條簡單路徑，包括所有的點，使得路徑最短。解:這是一個旅行售貨員問題TSP。這是一個NP問題，其實就是一個排列選取問題。算法如下：int  n, r;char usedMaxN;int  pMaxN;double min; void permute(int pos, double dist)int i;    if (p

32、os=n)         if (dist < min) min = dist;        return;        for (i=0; i<n; i+)        if (!usedi)          

33、60;  usedi+;            ppos = i;           if (dist + cost(pointppos-1, pointppos) < min)                permut

34、e(pos+1, dist + cost(pointppos-1, pointppos); usedi-;        例對于0和1的所有排列，從中同時選取r個元素使得0和1的數(shù)量不同。解 這道題很簡單，其實就是從0到2r的二元表示。算法如下：void dfs(int pos)   if (pos = r)          for (i=0; i<r; i+) cout<<pi; &#

35、160;     cout<<endl;       return;      ppos = 0;   dfs(pos+1);   ppos = 1;   dfs(pos+1); 例找最大團問題。一個圖的團，就是包括了圖的所有點的子圖，并且是連通的。也就是說，一個子圖包含了n個頂點和n*(n-1)/2條邊，找最大團問題是一個NP問題。算法如下：#define MaxN 50&

36、#160;int  n, max;int  pathMaxNMaxN;int  inCliqueMaxN; void dfs(int inGraph)int i, j;int GraphMaxN; if ( inClique0+inGraph0<=max ) return;if ( inClique0>max ) max=inClique0; /*對于圖中的所有點*/    for (i=1; i<=inGraph0; i+)    /*把節(jié)點放置到團中*/

37、        +inClique0; inCliqueinClique0=inGraphi;/*生成一個新的子圖*/ Graph0=0; for (j=i+1; j<=inGraph0; j+)     if (pathinGraphiinGraphj )          Graph+Graph0=inGraphj;   

38、60; dfs(Graph);/*從團中刪除節(jié)點*/        -inClique0;int main()int inGraphMaxN;int i, j;  cin >>n;  while (n > 0)          for (i=0; i<n; i+) for (j=0; j<n; j+)     cin >>pathij

39、;        max = 1;/*初始化*/        inClique0= 0;        inGraph0 = n; for (i=0; i<n; i+) inGraphi+1=i;        dfs(inGraph);     &#

40、160;  cout<<max<<endl;        cin >>n;    return 0;組合算法的選擇與應用（一）作者：未知    信息學文章來源：網(wǎng)絡    點擊數(shù)： 50    更新時間：2005-1-20【關鍵字】組合算法 評價依據(jù) 復雜性 選擇 應用 【摘要】本文提出了在組合算法設計和組合算法選擇方面所應當遵循的三個原則

41、，即通用性、可計算性和較少的信息冗余量，并初步分析了它們之間的相互關系。這三個原則是整個組合算法設計的主導思想，也是數(shù)學建模和算法優(yōu)化的方向。通過對三個問題的分析，提示了組合算法的設計方法，改進方向和優(yōu)化技術，是對一系列組合數(shù)學原理的實際應用，也是對組合算法設計的初步研究。【Abstract】The disquisition brings forward three principle in combination arithmetic designing and combination arithmetic choice. There is currency, countability an

42、d less information redundancy. And the disquisition analyses the relation of them. The three principle is the dominant ideology in combination arithmetic designing. Also it is the aspect of making mathematics modeling and optimizing arithmetic. Then the disquisition analyses three questions, prompts

43、 the devisal's method, betterment's way and the technique optimizing arithmetic. That is actual appliance to a catena of combination mathematics elements and it is also initial research in combination arithmetic designing.【正文】一、引 論組合數(shù)學是一個古老的數(shù)學分支，也是當代數(shù)學中非常重要的數(shù)學分支。它發(fā)源于有趣的數(shù)學游戲，許多古典的組合數(shù)學問題，無論在理論

44、數(shù)學或應用數(shù)學上都有很重要的研究價值。今天，一方面，極為成熟的組合計數(shù)理論為物理學、化學、生物學的發(fā)展奠定了堅實的基礎，另一方面，由于計算機軟硬件的限制，組合計數(shù)理論的計算機實踐又必然涉及到基于多項式時間內(nèi)的算法優(yōu)化問題。本文正是基于以上情況，對一系列組合問題的算法設計做了一些初步探索。二、組合算法的評價依據(jù)任何事物都有好壞之分，算法也不例外。眾所周知，時間復雜度與空間復雜度是算法評價的主要依據(jù)。那么，除了這兩點外，組合算法的設計還應遵循怎樣的原則呢？1通用性通用性即可移植性。一個算法，是只適合于一個特殊問題，還是可以適用于一類問題，這是組合算法評價的一個主要依據(jù)，有些組合數(shù)學問題，許多信息學

45、競賽或數(shù)學建模競賽選手一看到題目后往往使用模擬法或構造產(chǎn)生式系統(tǒng) ，然后用深度優(yōu)先搜索（DFS），或廣度優(yōu)先搜索（BFS）求解，用這些方法設計的程序往往受到時間或空間的限制，而且由于在綜合數(shù)據(jù)庫中信息存儲的數(shù)據(jù)結構不同，其算法實現(xiàn)時的規(guī)模 也不同，這必然影響到算法的通用性問題。解決問題的辦法是對原問題進行數(shù)學抽象，取其精華，去其糟粕。只有對原問題的數(shù)學模型仔細分析，抓住本質，才能建立高效的組合算法，只有這種經(jīng)過數(shù)學抽象的算法，才能具有較好的通用性，能夠應付較大的規(guī)模。另外，在大規(guī)模組合算法的設計過程中，強調(diào)通用性的好處是顯而易見的，它便于算法的優(yōu)化和升級。在實際應用中的某些條件改變時，可以重寫

46、較少的代碼。從軟件工程學的角度來說，通用性是必需的。2可計算性這里指的可計算性，是指能夠在多項式時間內(nèi)得出結果。一般來說，對于遞歸函數(shù)來說，由于計算機系統(tǒng)中的空間一定，因此對問題的規(guī)模有較嚴格的限制（例如在Turbo Pascal 7.0系統(tǒng)中，棧的最大空間只有65520字節(jié)）因此說，對于大多數(shù)的遞歸函數(shù)具有較差的可計算性。通過組合方法，求遞歸函數(shù)的非遞歸形式是解決這類問題有主要方法，但并不是所有的遞歸函數(shù)都可轉化為非遞歸形式，雙遞歸函數(shù)（如Ackermann函數(shù) ）便不能轉化為非遞歸形式，這類函數(shù)具有較小的可計算性。當然，對于某些遞歸函數(shù)，通過尋找函數(shù)本身的組合意義進而將其轉化為非遞歸函數(shù)也

47、是一種方法。這種方法的應用讀者將在后文中見到。 3、信息冗余量在組合數(shù)學的建模過程中，大量的信息冗余是制約組合算法效率的一個重要因素，例如在遞歸程序運行的過程中，實際上產(chǎn)生了一棵解答樹 ，同一棵子樹的結點間的信息不相互關聯(lián)，這樣便產(chǎn)生了大量的信息冗余，解決的方法之一便是引入記憶機制，將已得出的信息記錄下來。這種機制實際上起到了剪枝的作用，但它嚴格受到空間的限制，實際上是時空矛盾在算法設計中的體現(xiàn)。這便是我們在組合算法設計中倡導函數(shù)非遞歸化的原因。它可以達到零信息冗余。當然，組合算法的通用性、可計算性與信息冗余程度在一定程度上是對立的。例如雙遞歸函數(shù)作為一種數(shù)學模型，能夠反映一類問題，具有通用性

48、，但卻具有較差的可計算性和較大的信息冗余量，而有些問題雖具有較好的可計算性和較低的信息冗余量，卻具有較差的通用性。總之，算法的時間復雜度，空間復雜度，通用性，可計算性和信息冗余量應是衡量組合算法的幾個主要標準。 注： 見參考文獻6第一章在本論文中，我們將規(guī)模定義為在一定時間內(nèi)程序可以運行完畢的情況下輸入數(shù)據(jù)的最大量。Ackermann函數(shù)可用遞推關系如下定義A（m，0）=A（m-1，0） m=1，2，A（m，n）=A（m-1，A（m，n-1） m=1，2， n=1，2，初始條件為A（0，n）=n+1，n=0，1，見參考文獻6第二章（產(chǎn)生式系統(tǒng)的搜索策略）三、組合算法的選擇實例 組合算法的選擇與

49、應用（五）作者：未知    信息學文章來源：網(wǎng)絡    點擊數(shù)： 26    更新時間：2005-1-20 四 總 結組合算法作為當代組合數(shù)學研究的重要組成部分，在基礎理論研究和社會實踐中發(fā)揮著越來越重要的作用，本文著重討論組合算法的評價依據(jù)，初步揭示了組合算法的設計和優(yōu)化的基本問題?？傊?，只有掌握好組合算法的通用性，可計算性和信息冗余量的組合算法評價原則，才能設計出高效的組合算法?！靖?錄】【參考文獻】1 組合數(shù)學 盧開澄 清華大學出版社（1999）2 組合數(shù)學引論 孫淑玲

50、 許胤龍 中國科學技術大學出版社（1999）3 青少年國際和全國信息學（計算機）奧林匹克競賽指導-組合數(shù)學的算法與程序設計 吳文虎 王建德 清華大學出版社（1997）4 離散數(shù)學 Richard Johnsonbaugh 電子工業(yè)出版社 （1999）5 算法與數(shù)據(jù)結構傅清祥 王曉東 電子工業(yè)出版社 （1999）6人工智能導論林堯瑞 馬少平 清華大學出版社（1999）源程序】1 算法1-1 的源程序 2 算法1-2的源程序3算法2的源程序4算法3-1的源程序5算法3-2的源程序6算法3-3的源程序7算法3-4的源程序8算法3-5的源程序回溯法是一種選優(yōu)搜索法，按選優(yōu)條件向前搜索，以達到目標。但當

51、探索到某一步時，發(fā)現(xiàn)原先選擇并不優(yōu)或達不到目標，就退回一步重新選擇，這種走不通就退回再走的技術為回溯法，而滿足回溯條件的某個狀態(tài)的點稱為“回溯點”。例再以前例說明，找n個數(shù)中r個數(shù)的組合。解將自然數(shù)排列在數(shù)組A中：A1 A2 A35 4 35 4 23 2 排數(shù)時從A1 A2 A3，后一個至少比前一個數(shù)小，并且應滿足ri+Ari>r。若ri+Arir就要回溯，該關系就是回溯條件。為直觀起見，當輸出一組組合數(shù)后，若最后一位為，也應作一次回溯（若不回，便由上述回溯條件處理）。 程序program zuhe3;type tp=array1.100 of integer;var n,r:inte

52、ger; procedure comb2(n,r:integer;a:tp);var i,ri:integer;begin ri:=1;a1:=n;repeat if ri<>r then 沒有搜索到底if ri+ari>r then 是否回溯begin ari+1:=ari-1;ri:=ri+1;endelse begin ri:=ri-1; ari:=ari-1;end; 回溯elsebegin for j:=1 to r do write(aj:3);writeln; 輸出組合數(shù)if ar=1 then 是否回溯begin ri:=ri-1; ari:=ari-1;en

53、d; 回溯else ari:=ari-1; 遞推到下一個數(shù)end;until a1<>r-1;end;begin MAINwrite('n,r=');readln(n,r);if r>n then begin writeln('Input n,r error!');halt; end comb2(n,r);end.N皇后問題的回溯算法 - 一切為了速度作者：  來自：  閱讀次數(shù)： 1 大 中 小   #include<iostream.h>const int n = 15

54、 ; /15皇后問題.改動n可變成N皇后問題const int n_sub = n - 1 ;int queenn ;  /N個棋子.N對應每一列,如n=0的棋子只下在0列,1下1.類推bool rown ;    /棋局的每一行是否有棋,有則為1,無為0 ;bool passive2*n-1 ;  /斜率為1的斜線方向上是不是有皇后bool negative2*n-1 ; /斜率為負1的斜線方向上是不是有皇后./之所以用全局變量,因全局數(shù)組元素值自動為0int main()  int cur = 0 ;/游標,當前移動的棋

55、子(哪一列的棋子) bool flag = false ; /當前棋子位置是否合法 queen0 = -1 ;  /第0列棋子準備,因一開始移動的就是第0列棋子 int count = 0 ; /一共有多少種下法 ; cout<<"=Starting="<<endl ; while(cur>=0)     while(cur>=0 && queencur<n && !flag) /當還不確定當

56、前位置是否可下      queencur+ ;/   cout<<"第"<<cur<<"列棋子開始走在第"<<queencur<<"行"<<endl ;/   cin.get() ;   if(queencur >= n) /如果當前列已經(jīng)下完(找不到合法位置)/    cout

57、<<"當前行是非法行,當前列棋子走完,沒有合法位置,回溯上一列棋子"<<endl ;/    cin.get() ;    queencur = -1 ; /當前列棋子置于準備狀態(tài)    cur- ; /回溯到上一列的棋子    if(cur>=0)          rowqueencur = false

58、;         passivequeencur + cur = false ;           negativen_sub + cur - queencur = false ;        /由于要移下一步,所以回溯棋子原位置所在行應該沒有棋子啦.置row為false     /并且棋子對應的斜線的

59、標志位passivecur和negativecur也應該要設為false ;           else     /先判斷棋子所在行沒有棋子    if(rowqueencur = false)  /當前行沒有棋子/        cout<<"棋子"<<cur<<&qu

60、ot;所在行沒有其他棋子,正在檢查斜線"<<endl ;        flag = true ; / 暫設為true,或與之前棋子斜交,則再設為false ;     /以下檢查當前棋子是否與之前的棋子斜線相交     if( passivequeencur + cur = true | negativen_sub + cur - queencur = true)    &

61、#160;   flag = false ;/      cout<<"出現(xiàn)斜線相交,該位置不合法"<<endl ;          else           flag = true ;     if(flag

62、)  /沒有斜交,位置合法/         cout<<"斜線也沒有相交,該位置合法"<<endl ;         if(cur = n-1)  /如果是最后一個棋子      /          cout<&l

63、t;"棋子走完一輪,總走法加1"<<endl ;          count+ ;  /總走法加一 ;               rowqueencur = true ;/ 當前行設為有棋子      passivequeencur + cur = true ;/

64、當前行正斜率方向有棋子      negativen_sub + cur - queencur = true ; /當前行負斜率方向上也有棋子      cur+ ;      if(cur >= n)         cur- ;       rowqueenc

65、ur = false ;        passivequeencur + cur = false ;             negativen_sub + cur - queencur = false ;/原理同回溯                

66、;  flag = false ;                 /else    cout<<n<<"皇后問題一共有"<<count<<"種解法"<<endl  ; return 0 ;/計算15皇后用時1分鐘15秒/把n改成16,測16皇后用時大約8分鐘

67、/以上測試在Barton 2000+,KingstonDDR400 256M下測試/*斜線判斷如下:正斜率對應數(shù)組passive2*n-1 ;0    1    2    3. .  n1    2    3    4.   n+12    3    4    5.  

68、 .n+23    4    5    6.   n+3.n-1 n    n+1 n+2.2*n-1 利用行和列的坐標相加,即可得到其對應斜線對應的passivei.再看一下passivei是否為1即可知道該斜線上是否有其他棋子.負斜率判斷如下負余率對應數(shù)姐negative2*n-1n-1 n    n+1 n+2.2*n-1 .3    4    5 &

69、#160;  6.    n+32    3    4    5.   .n+21    2    3    4.   n+10    1    2    3. .  n用棋子所在位置的橫坐標(cur)減去縱坐標(queencur

70、),再加上n-1,即可得到對應的negativei數(shù)組,若為1,則該行有棋子.*/初識回溯算法     回溯算法也叫試探法，它是一種系統(tǒng)地搜索問題的解的方法?；厮菟惴ǖ幕舅枷胧牵簭囊粭l路往前走，能進則進，不能進則退回來，換一條路再試。用回溯算法解決問題的一般步驟為：     一、定義一個解空間，它包含問題的解。     二、利用適于搜索的方法組織解空間。     三、利用深度優(yōu)先法搜索解空間。     四、利用限界函數(shù)避免移動到不可能產(chǎn)生解的子

71、空間。     問題的解空間通常是在搜索問題的解的過程中動態(tài)產(chǎn)生的，這是回溯算法的一個重要特性。     下面通過一個具體實例加深大家對回溯算法的認識。     例：騎士游歷（1997年全國青少年信息學（計算機）奧林匹克分區(qū)聯(lián)賽高中組復賽試題第三題）     設有一個n×m的棋盤(2<=n<=50,2<=m<=50),如圖1,在棋盤上任一點有一個中國象棋馬， 圖1     馬走的規(guī)則為：   

72、  1、馬走日字  2、馬只能向右走     即如圖2所示： 圖2 圖3 圖4     任務1：當n，m 輸入之后,找出一條從左下角到右上角的路徑。     例如：輸入 n=4，m=4。     輸出：路徑的格式：(1,1)->(2,3)->(4,4)     若不存在路徑，則輸出"no"     任務2：當n，m 給出之后，同時給出馬起始的位置和終點的位置，試找出

73、從起點到終點的所有路徑的數(shù)目（若不存在從起點到終點的路徑,則輸出0）。     例如：     (n=10,m=10),(1,5)(起點),(3,5)(終點)，     輸出：     2（即由(1,5)到(3,5)共有2條路徑，如圖4）     分析：為了解決這個問題，我們將棋盤的橫坐標規(guī)定為x，縱坐標規(guī)定為y，對于一個m×n的棋盤，x的值從1到m，y的值從1到n。棋盤上的每一個點，可以表示為：（x坐標值，y坐標值），即用它所在的列號

74、和行號來表示，比如(3,5)表示第3列和第5行相交的點。     要尋找從起點到終點的路徑，我們可以使用回溯算法的思想。首先將起點作為當前位置。按照象棋馬的移動規(guī)則，搜索有沒有可以移動的相鄰位置。如果有可以移動的相鄰位置，則移動到其中的一個相鄰位置，并將這個相鄰位置作為新的當前位置，按同樣的方法繼續(xù)搜索通往終點的路徑。如果搜索不成功，則換另外一個相鄰位置，并以它作為新的當前位置繼續(xù)搜索通往終點的路徑。     為簡單起見，先看4×4的棋盤，如圖3。首先將起點(1,1)作為當前位置，按照象棋馬的移動規(guī)則，可以移動到(2,3)和

75、(3,2)。假如移動到(2,3)，以(2,3)作為新的當前位置，又可以移動到 (4,4)、(4,2)和(3,1)。繼續(xù)移動，假如移動到(4,4)，將(4,4)作為新的當前位置，這時候已經(jīng)沒有可以移動的相鄰位置了。 (4,4)已經(jīng)是終點，對于任務一，我們已經(jīng)找到了一條從起點到終點的路徑，完成了任務，可以結束搜索過程。但對于任務二，我們還不能結束搜索過程。從當前位置(4,4)回溯到(2,3)，(2,3)再次成為當前位置。從(2,3)開始，換另外一個相鄰位置移動，移動到(4,2)，然后是(3,1)。(2,3)的所有相鄰位置都已經(jīng)搜索過。從(2,3)回溯到(1,1)，(1,1)再次成為當前位置。從(1

76、,1)開始，還可以移動到(3,2)，從(3,2)繼續(xù)移動，可以移動到(4,4)，這時候，所有可能的路徑都已經(jīng)試探完畢，搜索過程結束。 圖5     如果用樹形結構來組織問題的解空間（如圖5），那么尋找從起點到終點的路徑的過程,實際上就是從根結點開始，使用深度優(yōu)先方法對這棵樹的一次搜索過程。     對于任務一，要尋找一條從起點到終點的路徑，為了確保路徑上的點不被丟失，我們可以在程序中設置一個棧，用它來保存搜索過程中象棋馬移動到的每一個點。     算法程序如下：    將起點

77、作為當前位置    do while 不是終點       是否有可以移動的相鄰位置？       if 有可以移動的相鄰位置 then           將當前位置入棧           移動到相鄰位置     &

78、#160; else           若?？?，結束尋找過程，并返回0           回溯到棧頂中的位置        endif     loop     在求精以上算法程序的過程中，還存在這樣一個問題：怎樣從當前位置herep移動到它的相鄰位置？題目規(guī)定，象棋馬有四種移動方法，如圖2。從

79、左到右，我們分別給四種移動方法編號為0、1、2、3；對每種移動方法，可以用橫坐標和縱坐標從起點到終點的偏移值來表示，并將這些表示移動方法的偏移值保存在一個數(shù)組pyz中，如下表 編號(i)pyz(i).xzbpyz(i).yzb方向021右上12-1右下212右上31-2右下    從當前位置搜索它的相鄰位置的時候，為了便于程序的實現(xiàn)，我們可以按照移動編號的固定順序來進行，比如，首先嘗試第0種移動方法，其次嘗試第1種移動方法，再次嘗試第2種移動方法，最后嘗試第3種移動方法。     任務一參考程序如下：   

80、0; cls     type dian         xzb as integer         yzb as integer    end type    dim pyz(3) as dian, lj(50) as dian    dim herep as dian, nextp as dian &#

81、160;  dim m as integer, n as integer    rem初始化偏移值    pyz(0).xzb = 2: pyz(0).yzb = 1    pyz(1).xzb = 2: pyz(1).yzb = -1    pyz(2).xzb = 1: pyz(2).yzb = 2    pyz(3).xzb = 1: pyz(3).yzb = -2    rem初始化當前位置

82、0;   herep.xzb = 1: herep.yzb = 1    input "please input m and n:", m, n     rem在m×n的棋盤上尋找從左下角到右上角的一條路徑    def fnfind (m, n)        rem初始化變量opti（用來標識是哪種移動方法）和棧頂元素指針k      

83、;   opti = 0: k = 0        rem是否可以向下一位置移動        do while not (herep.xzb = m and herep.yzb = n)           do while opti <= 3       &

84、#160;      r = herep.xzb + pyz(opti).xzb              c = herep.yzb + pyz(opti).yzb              if r <= m and c <= n and c >= 1 then ex

85、it do              opti = opti + 1           loop            rem若可以向下一位置移動，就移動到下一位置        

86、0;  if opti <= 3 then               k = k + 1: lj(k).xzb = herep.xzb               lj(k).yzb = herep.yzb         

87、0;    herep.xzb = r: herep.yzb = c              opti = 0               rem若不能再向下移動，就回溯           else

88、0;             rem若?？?，則返回0，并結束尋找               if k = 0 then                  fnfind = 0     &#