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

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

2、,按這個(gè)順序逐一生成候選者并檢驗(yàn).對(duì)于迷宮問題,我想用回溯法的難點(diǎn)就在如何為解空間排序,以確保曾被放棄過的填數(shù)序列不被再次試驗(yàn).在二維迷宮里面,從出發(fā)點(diǎn)開始,每個(gè)點(diǎn)按四鄰域算,按照右,上,左,下的順序搜索下一落腳點(diǎn),有路則進(jìn),無路即退,前點(diǎn)再從下一個(gè)方向搜索,即可構(gòu)成一有序模型.下表即迷宮  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ā)點(diǎn)開始,按序查找下一點(diǎn)所選點(diǎn)列構(gòu)成有序數(shù)列,如果4個(gè)方向都搜遍都無路走,就回退,并置前點(diǎn)的方向加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坐標(biāo)int y; /存Y坐標(biāo)int c;  /存該點(diǎn)可能的下點(diǎn)所在的方向,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) /已找到一個(gè)組合     /打印路徑   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的幫助關(guān)鍵字 遞歸 DFS 前言 這篇論文主要針對(duì)排列組合對(duì)回溯算法展開討論，在每一個(gè)討論之后，還有相關(guān)的推薦題。在開始之前，我們先應(yīng)該看一下回溯算法的概念，所謂回溯：就是搜索一棵狀態(tài)樹的過程，這個(gè)過程

20、類似于圖的深度優(yōu)先搜索（DFS），在搜索的每一步（這里的每一步對(duì)應(yīng)搜索樹的第i層）中產(chǎn)生一個(gè)正確的解，然后在以后的每一步搜索過程中，都檢查其前一步的記錄，并且它將有條件的選擇以后的每一個(gè)搜索狀態(tài)（即第i+1層的狀態(tài)節(jié)點(diǎn)）。需掌握的基本算法：排列：就是從n個(gè)元素中同時(shí)取r個(gè)元素的排列，記做P(n,r)。（當(dāng)r=n時(shí)，我們稱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個(gè)元素了，則可打印r個(gè)元素的排列 */    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個(gè)元素未用過*/*使用第i個(gè)元素，作上已用標(biāo)記，目的是使以后該元素不可用*/            usedi+;/*保存當(dāng)前搜索到的第i個(gè)元素*/            ppos = i;/*遞歸搜索*/           permute(pos+

24、1); /*恢復(fù)遞歸前的值，目的是使以后改元素可用*/ usedi-;         可重排列：就是從任意n個(gè)元素中，取r個(gè)可重復(fù)的元素的排列。例如，對(duì)于集合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個(gè)元素了，則打印它們*/    if (pos=r)          for (i=0; i<r; i+)            cout << Pi;    &

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

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

28、160;      usedi-; /*恢復(fù)遞歸前的值*/         組合：從n個(gè)不同元素中取r個(gè)不重復(fù)的元素組成一個(gè)子集，而不考慮其元素的順序，稱為從n個(gè)中取r個(gè)的無重組合，例如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個(gè)元

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+) /*對(duì)于所有未用的元素*/        if (!usedi) /*把它放置在組合中*/            Cpos = i;/*使用該元素*/ usedi+;/*搜索第i+1個(gè)元素*/     combine(pos+1,i+1);

31、/*恢復(fù)遞歸前的值*/ usedi-;         可重組合：類似于可重排列。例 給出空間中給定n(n<10)個(gè)點(diǎn)，畫一條簡單路徑，包括所有的點(diǎn)，使得路徑最短。解:這是一個(gè)旅行售貨員問題TSP。這是一個(gè)NP問題，其實(shí)就是一個(gè)排列選取問題。算法如下：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-;        例對(duì)于0和1的所有排列，從中同時(shí)選取r個(gè)元素使得0和1的數(shù)量不同。解 這道題很簡單，其實(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); 例找最大團(tuán)問題。一個(gè)圖的團(tuán)，就是包括了圖的所有點(diǎn)的子圖，并且是連通的。也就是說，一個(gè)子圖包含了n個(gè)頂點(diǎn)和n*(n-1)/2條邊，找最大團(tuán)問題是一個(gè)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; /*對(duì)于圖中的所有點(diǎn)*/    for (i=1; i<=inGraph0; i+)    /*把節(jié)點(diǎn)放置到團(tuán)中*/

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

38、60; dfs(Graph);/*從團(tuán)中刪除節(jié)點(diǎn)*/        -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;組合算法的選擇與應(yīng)用（一）作者：未知    信息學(xué)文章來源：網(wǎng)絡(luò)    點(diǎn)擊數(shù)： 50    更新時(shí)間：2005-1-20【關(guān)鍵字】組合算法 評(píng)價(jià)依據(jù) 復(fù)雜性 選擇 應(yīng)用 【摘要】本文提出了在組合算法設(shè)計(jì)和組合算法選擇方面所應(yīng)當(dāng)遵循的三個(gè)原則

41、，即通用性、可計(jì)算性和較少的信息冗余量，并初步分析了它們之間的相互關(guān)系。這三個(gè)原則是整個(gè)組合算法設(shè)計(jì)的主導(dǎo)思想，也是數(shù)學(xué)建模和算法優(yōu)化的方向。通過對(duì)三個(gè)問題的分析，提示了組合算法的設(shè)計(jì)方法，改進(jìn)方向和優(yōu)化技術(shù)，是對(duì)一系列組合數(shù)學(xué)原理的實(shí)際應(yīng)用，也是對(duì)組合算法設(shè)計(jì)的初步研究。【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ù)學(xué)是一個(gè)古老的數(shù)學(xué)分支，也是當(dāng)代數(shù)學(xué)中非常重要的數(shù)學(xué)分支。它發(fā)源于有趣的數(shù)學(xué)游戲，許多古典的組合數(shù)學(xué)問題，無論在理論

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

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

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

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

48、，但卻具有較差的可計(jì)算性和較大的信息冗余量，而有些問題雖具有較好的可計(jì)算性和較低的信息冗余量，卻具有較差的通用性?？傊?，算法的時(shí)間復(fù)雜度，空間復(fù)雜度，通用性，可計(jì)算性和信息冗余量應(yīng)是衡量組合算法的幾個(gè)主要標(biāo)準(zhǔn)。 注： 見參考文獻(xiàn)6第一章在本論文中，我們將規(guī)模定義為在一定時(shí)間內(nèi)程序可以運(yùn)行完畢的情況下輸入數(shù)據(jù)的最大量。Ackermann函數(shù)可用遞推關(guān)系如下定義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，見參考文獻(xiàn)6第二章（產(chǎn)生式系統(tǒng)的搜索策略）三、組合算法的選擇實(shí)例 組合算法的選擇與

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

50、 許胤龍 中國科學(xué)技術(shù)大學(xué)出版社（1999）3 青少年國際和全國信息學(xué)（計(jì)算機(jī)）奧林匹克競賽指導(dǎo)-組合數(shù)學(xué)的算法與程序設(shè)計(jì) 吳文虎 王建德 清華大學(xué)出版社（1997）4 離散數(shù)學(xué) Richard Johnsonbaugh 電子工業(yè)出版社 （1999）5 算法與數(shù)據(jù)結(jié)構(gòu)傅清祥 王曉東 電子工業(yè)出版社 （1999）6人工智能導(dǎo)論林堯瑞 馬少平 清華大學(xué)出版社（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)條件向前搜索，以達(dá)到目標(biāo)。但當(dāng)

51、探索到某一步時(shí)，發(fā)現(xiàn)原先選擇并不優(yōu)或達(dá)不到目標(biāo)，就退回一步重新選擇，這種走不通就退回再走的技術(shù)為回溯法，而滿足回溯條件的某個(gè)狀態(tài)的點(diǎn)稱為“回溯點(diǎn)”。例再以前例說明，找n個(gè)數(shù)中r個(gè)數(shù)的組合。解將自然數(shù)排列在數(shù)組A中：A1 A2 A35 4 35 4 23 2 排數(shù)時(shí)從A1 A2 A3，后一個(gè)至少比前一個(gè)數(shù)小，并且應(yīng)滿足ri+Ari>r。若ri+Arir就要回溯，該關(guān)系就是回溯條件。為直觀起見，當(dāng)輸出一組組合數(shù)后，若最后一位為，也應(yīng)作一次回溯（若不回，便由上述回溯條件處理）。 程序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; 遞推到下一個(gè)數(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皇后問題.改動(dòng)n可變成N皇后問題const int n_sub = n - 1 ;int queenn ;  /N個(gè)棋子.N對(duì)應(yīng)每一列,如n=0的棋子只下在0列,1下1.類推bool rown ;    /棋局的每一行是否有棋,有則為1,無為0 ;bool passive2*n-1 ;  /斜率為1的斜線方向上是不是有皇后bool negative2*n-1 ; /斜率為負(fù)1的斜線方向上是不是有皇后./之所以用全局變量,因全局?jǐn)?shù)組元素值自動(dòng)為0int main()  int cur = 0 ;/游標(biāo),當(dāng)前移動(dòng)的棋

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

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

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

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

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

60、ot;所在行沒有其他棋子,正在檢查斜線"<<endl ;        flag = true ; / 暫設(shè)為true,或與之前棋子斜交,則再設(shè)為false ;     /以下檢查當(dāng)前棋子是否與之前的棋子斜線相交     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)  /如果是最后一個(gè)棋子      /          cout<&l

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

64、當(dāng)前行正斜率方向有棋子      negativen_sub + cur - queencur = true ; /當(dāng)前行負(fù)斜率方向上也有棋子      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 ;/計(jì)算15皇后用時(shí)1分鐘15秒/把n改成16,測(cè)16皇后用時(shí)大約8分鐘

67、/以上測(cè)試在Barton 2000+,KingstonDDR400 256M下測(cè)試/*斜線判斷如下:正斜率對(duì)應(yīng)數(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 利用行和列的坐標(biāo)相加,即可得到其對(duì)應(yīng)斜線對(duì)應(yīng)的passivei.再看一下passivei是否為1即可知道該斜線上是否有其他棋子.負(fù)斜率判斷如下負(fù)余率對(duì)應(yīng)數(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用棋子所在位置的橫坐標(biāo)(cur)減去縱坐標(biāo)(queencur

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

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

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

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

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

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

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

77、作為當(dāng)前位置    do while 不是終點(diǎn)       是否有可以移動(dòng)的相鄰位置？       if 有可以移動(dòng)的相鄰位置 then           將當(dāng)前位置入棧           移動(dòng)到相鄰位置     &

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

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

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初始化當(dāng)前位置

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（用來標(biāo)識(shí)是哪種移動(dòng)方法）和棧頂元素指針k      

83、;   opti = 0: k = 0        rem是否可以向下一位置移動(dòng)        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若可以向下一位置移動(dòng)，就移動(dòng)到下一位置        

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若不能再向下移動(dòng)，就回溯           else

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