1、回溯法的一般描述

    可用回溯法求解的問題P，通常要能表達(dá)為：對(duì)于已知的由n元組（x₁，x₂，…，x_n）組成的一個(gè)狀態(tài)空間E={（x₁，x₂，…，x_n）∣x_i∈S_i ，i=1，2，…，n}，給定關(guān)于n元組中的一個(gè)分量的一個(gè)約束集D，要求E中滿足D的全部約束條件的所有n元組。其中S_i是分量x_i的定義域，且 |S_i| 有限，i=1，2，…，n。我們稱E中滿足D的全部約束條件的任一n元組為問題P的一個(gè)解。

    解問題P的最樸素的方法就是枚舉法，即對(duì)E中的所有n元組逐一地檢測(cè)其是否滿足D的全部約束，若滿足，則為問題P的一個(gè)解。但顯然，其計(jì)算量是相當(dāng)大的。

    我們發(fā)現(xiàn)，對(duì)于許多問題，所給定的約束集D具有完備性，即i元組（x₁，x₂，…，x_i）滿足D中僅涉及到x₁，x₂，…，x_i的所有約束意味著j（j<i）元組（x₁，x₂，…，x_j）一定也滿足D中僅涉及到x₁，x₂，…，x_j的所有約束，i=1，2，…，n。換句話說，只要存在0≤j≤n-1，使得（x₁，x₂，…，x_j）違反D中僅涉及到x₁，x₂，…，x_j的約束之一，則以（x₁，x₂，…，x_j）為前綴的任何n元組（x₁，x₂，…，x_j，x_j+1，…，x_n）一定也違反D中僅涉及到x₁，x₂，…，x_i的一個(gè)約束，n≥i>j。因此，對(duì)于約束集D具有完備性的問題P，一旦檢測(cè)斷定某個(gè)j元組（x₁，x₂，…，x_j）違反D中僅涉及x₁，x₂，…，x_j的一個(gè)約束，就可以肯定，以（x₁，x₂，…，x_j）為前綴的任何n元組（x₁，x₂，…，x_j，x_j+1，…，x_n）都不會(huì)是問題P的解，因而就不必去搜索它們、檢測(cè)它們�；厮莘ㄕ�是針對(duì)這類問題，利用這類問題的上述性質(zhì)而提出來的比枚舉法效率更高的算法。

    回溯法首先將問題P的n元組的狀態(tài)空間E表示成一棵高為n的帶權(quán)有序樹T，把在E中求問題P的所有解轉(zhuǎn)化為在T中搜索問題P的所有解。樹T類似于檢索樹，它可以這樣構(gòu)造：

       設(shè)S_i中的元素可排成x_i⁽¹⁾ ，x_i⁽²⁾ ，…，x_i^(mi-1) ，|S_i| =m_i，i=1，2，…，n。從根開始，讓T的第I層的每一個(gè)結(jié)點(diǎn)都有m_i個(gè)兒子。這m_i個(gè)兒子到它們的雙親的邊，按從左到右的次序，分別帶權(quán)x_i+1⁽¹⁾ ，x_i+1⁽²⁾ ，…，x_i+1^(mi) ，i=0，1，2，…，n-1。照這種構(gòu)造方式，E中的一個(gè)n元組（x₁，x₂，…，x_n）對(duì)應(yīng)于T中的一個(gè)葉子結(jié)點(diǎn)，T的根到這個(gè)葉子結(jié)點(diǎn)的路徑上依次的n條邊的權(quán)分別為x₁，x₂，…，x_n，反之亦然。另外，對(duì)于任意的0≤i≤n-1，E中n元組（x₁，x₂，…，x_n）的一個(gè)前綴I元組（x₁，x₂，…，x_i）對(duì)應(yīng)于T中的一個(gè)非葉子結(jié)點(diǎn)，T的根到這個(gè)非葉子結(jié)點(diǎn)的路徑上依次的I條邊的權(quán)分別為x₁，x₂，…，x_i，反之亦然。特別，E中的任意一個(gè)n元組的空前綴（），對(duì)應(yīng)于T的根。

       因而，在E中尋找問題P的一個(gè)解等價(jià)于在T中搜索一個(gè)葉子結(jié)點(diǎn)，要求從T的根到該葉子結(jié)點(diǎn)的路徑上依次的n條邊相應(yīng)帶的n個(gè)權(quán)x₁，x₂，…，x_n滿足約束集D的全部約束。在T中搜索所要求的葉子結(jié)點(diǎn)，很自然的一種方式是從根出發(fā)，按深度優(yōu)先的策略逐步深入，即依次搜索滿足約束條件的前綴1元組（x_1i）、前綴2元組（x₁，x₂）、…，前綴I元組（x₁，x₂，…，x_i），…，直到i=n為止。

       在回溯法中，上述引入的樹被稱為問題P的狀態(tài)空間樹；樹T上任意一個(gè)結(jié)點(diǎn)被稱為問題P的狀態(tài)結(jié)點(diǎn)；樹T上的任意一個(gè)葉子結(jié)點(diǎn)被稱為問題P的一個(gè)解狀態(tài)結(jié)點(diǎn)；樹T上滿足約束集D的全部約束的任意一個(gè)葉子結(jié)點(diǎn)被稱為問題P的一個(gè)回答狀態(tài)結(jié)點(diǎn)，它對(duì)應(yīng)于問題P的一個(gè)解。

【問題】       組合問題

    問題描述：找出從自然數(shù)1、2、……、n中任取r個(gè)數(shù)的所有組合。

    例如n=5，r=3的所有組合為： 

（1）1、2、3              （2）1、2、4              （3）1、2、5

              （4）1、3、4              （5）1、3、5              （6）1、4、5

              （7）2、3、4              （8）2、3、5              （9）2、4、5

              （10）3、4、5

則該問題的狀態(tài)空間為：

E={（x1，x2，x3）∣x_i∈S ，i=1，2，3 }     其中：S={1，2，3，4，5}

約束集為：    x1<x2<x3

       顯然該約束集具有完備性。

問題的狀態(tài)空間樹T：

⊙                ⊙           ⊙       ⊙   ⊙

⊙    ⊙   ⊙   ⊙     ⊙  ⊙  ⊙     ⊙  ⊙       ⊙

 

 

 

 

 

 

 

 

 

 

 

 

 

2、回溯法的方法

       對(duì)于具有完備約束集D的一般問題P及其相應(yīng)的狀態(tài)空間樹T，利用T的層次結(jié)構(gòu)和D的完備性，在T中搜索問題P的所有解的回溯法可以形象地描述為：

       從T的根出發(fā)，按深度優(yōu)先的策略，系統(tǒng)地搜索以其為根的子樹中可能包含著回答結(jié)點(diǎn)的所有狀態(tài)結(jié)點(diǎn)，而跳過對(duì)肯定不含回答結(jié)點(diǎn)的所有子樹的搜索，以提高搜索效率。具體地說，當(dāng)搜索按深度優(yōu)先策略到達(dá)一個(gè)滿足D中所有有關(guān)約束的狀態(tài)結(jié)點(diǎn)時(shí)，即“激活”該狀態(tài)結(jié)點(diǎn)，以便繼續(xù)往深層搜索；否則跳過對(duì)以該狀態(tài)結(jié)點(diǎn)為根的子樹的搜索，而一邊逐層地向該狀態(tài)結(jié)點(diǎn)的祖先結(jié)點(diǎn)回溯，一邊“殺死”其兒子結(jié)點(diǎn)已被搜索遍的祖先結(jié)點(diǎn)，直到遇到其兒子結(jié)點(diǎn)未被搜索遍的祖先結(jié)點(diǎn)，即轉(zhuǎn)向其未被搜索的一個(gè)兒子結(jié)點(diǎn)繼續(xù)搜索。

    在搜索過程中，只要所激活的狀態(tài)結(jié)點(diǎn)又滿足終結(jié)條件，那么它就是回答結(jié)點(diǎn)，應(yīng)該把它輸出或保存。由于在回溯法求解問題時(shí)，一般要求出問題的所有解，因此在得到回答結(jié)點(diǎn)后，同時(shí)也要進(jìn)行回溯，以便得到問題的其他解，直至回溯到T的根且根的所有兒子結(jié)點(diǎn)均已被搜索過為止。

       例如在組合問題中，從T的根出發(fā)深度優(yōu)先遍歷該樹。當(dāng)遍歷到結(jié)點(diǎn)（1，2）時(shí)，雖然它滿足約束條件，但還不是回答結(jié)點(diǎn)，則應(yīng)繼續(xù)深度遍歷；當(dāng)遍歷到葉子結(jié)點(diǎn)（1，2，5）時(shí)，由于它已是一個(gè)回答結(jié)點(diǎn)，則保存（或輸出）該結(jié)點(diǎn)，并回溯到其雙親結(jié)點(diǎn)，繼續(xù)深度遍歷；當(dāng)遍歷到結(jié)點(diǎn)（1，5）時(shí)，由于它已是葉子結(jié)點(diǎn)，但不滿足約束條件，故也需回溯。

3、回溯法的一般流程和技術(shù)

       在用回溯法求解有關(guān)問題的過程中，一般是一邊建樹，一邊遍歷該樹。在回溯法中我們一般采用非遞歸方法。下面，我們給出回溯法的非遞歸算法的一般流程：

N

Y

N

Y

N

N

Y

Y

建立根結(jié)點(diǎn)root

建立root的第一個(gè)孩子結(jié)點(diǎn)node

建樹完畢？

Node是葉子？

Node是解？

處理解

回溯node=parent(node)

Node還有孩子？

建立node的孩子結(jié)點(diǎn)node=parent(node)

建立node的孩子結(jié)點(diǎn)node=parent(node)

結(jié)束

開始

    在用回溯法求解問題，也即在遍歷狀態(tài)空間樹的過程中，如果采用非遞歸方法，則我們一般要用到棧的數(shù)據(jù)結(jié)構(gòu)。這時(shí)，不僅可以用棧來表示正在遍歷的樹的結(jié)點(diǎn)，而且可以很方便地表示建立孩子結(jié)點(diǎn)和回溯過程。

    例如在組合問題中，我們用一個(gè)一維數(shù)組Stack[ ]表示棧。開始�？�，則表示了樹的根結(jié)點(diǎn)。如果元素1進(jìn)棧，則表示建立并遍歷（1）結(jié)點(diǎn)；這時(shí)如果元素2進(jìn)棧，則表示建立并遍歷（1，2）結(jié)點(diǎn)；元素3再進(jìn)棧，則表示建立并遍歷（1，2，3）結(jié)點(diǎn)。這時(shí)可以判斷它滿足所有約束條件，是問題的一個(gè)解，輸出（或保存）。這時(shí)只要棧頂元素（3）出棧，即表示從結(jié)點(diǎn)（1，2，3）回溯到結(jié)點(diǎn)（1，2）。

【問題】       組合問題

    問題描述：找出從自然數(shù)1，2，…，n中任取r個(gè)數(shù)的所有組合。

    采用回溯法找問題的解，將找到的組合以從小到大順序存于a[0]，a[1]，…，a[r-1]中，組合的元素滿足以下性質(zhì)：

（1）       a[i+1]>a[i]，后一個(gè)數(shù)字比前一個(gè)大；

（2）       a[i]-i<=n-r+1。

    按回溯法的思想，找解過程可以敘述如下：

       首先放棄組合數(shù)個(gè)數(shù)為r的條件，候選組合從只有一個(gè)數(shù)字1開始。因該候選解滿足除問題規(guī)模之外的全部條件，擴(kuò)大其規(guī)模，并使其滿足上述條件（1），候選組合改為1，2。繼續(xù)這一過程，得到候選組合1，2，3。該候選解滿足包括問題規(guī)模在內(nèi)的全部條件，因而是一個(gè)解。在該解的基礎(chǔ)上，選下一個(gè)候選解，因a[2]上的3調(diào)整為4，以及以后調(diào)整為5都滿足問題的全部要求，得到解1，2，4和1，2，5。由于對(duì)5不能再作調(diào)整，就要從a[2]回溯到a[1]，這時(shí)，a[1]=2，可以調(diào)整為3，并向前試探，得到解1，3，4。重復(fù)上述向前試探和向后回溯，直至要從a[0]再回溯時(shí)，說明已經(jīng)找完問題的全部解。按上述思想寫成程序如下：

【程序】

# define   MAXN    100

int a[MAXN];

void comb(int m,int r)

{     int i,j;

       i=0;

       a[i]=1;

       do {

              if (a[i]-i<=m-r+1

              {     if (i==r-1)

                     {     for (j=0;j<r;j++)

                                   printf(“%4d”,a[j]);

                            printf(“\n”);

                     }

                     a[i]++;

                     continue;

              }

              else

              {     if (i==0)

                            return;

                     a[--i]++;

              }

       }     while (1)

}

 

main()

{     comb(5,3);

}

【問題】       填字游戲

    問題描述：在3×3個(gè)方格的方陣中要填入數(shù)字1到N（N≥10）內(nèi)的某9個(gè)數(shù)字，每個(gè)方格填一個(gè)整數(shù)，似的所有相鄰兩個(gè)方格內(nèi)的兩個(gè)整數(shù)之和為質(zhì)數(shù)。試求出所有滿足這個(gè)要求的各種數(shù)字填法。

    可用試探發(fā)找到問題的解，即從第一個(gè)方格開始，為當(dāng)前方格尋找一個(gè)合理的整數(shù)填入，并在當(dāng)前位置正確填入后，為下一方格尋找可填入的合理整數(shù)。如不能為當(dāng)前方格找到一個(gè)合理的可填證書，就要回退到前一方格，調(diào)整前一方格的填入數(shù)。當(dāng)?shù)诰艂�(gè)方格也填入合理的整數(shù)后，就找到了一個(gè)解，將該解輸出，并調(diào)整第九個(gè)的填入的整數(shù)，尋找下一個(gè)解。

    為找到一個(gè)滿足要求的9個(gè)數(shù)的填法，從還未填一個(gè)數(shù)開始，按某種順序（如從小到大的順序）每次在當(dāng)前位置填入一個(gè)整數(shù)，然后檢查當(dāng)前填入的整數(shù)是否能滿足要求。在滿足要求的情況下，繼續(xù)用同樣的方法為下一方格填入整數(shù)。如果最近填入的整數(shù)不能滿足要求，就改變填入的整數(shù)。如對(duì)當(dāng)前方格試盡所有可能的整數(shù)，都不能滿足要求，就得回退到前一方格，并調(diào)整前一方格填入的整數(shù)。如此重復(fù)執(zhí)行擴(kuò)展、檢查或調(diào)整、檢查，直到找到一個(gè)滿足問題要求的解，將解輸出。

回溯法找一個(gè)解的算法：

{     int m=0,ok=1;

       int n=8;

       do{

              if (ok)     擴(kuò)展;

              else         調(diào)整;

              ok=檢查前m個(gè)整數(shù)填放的合理性;

       }     while ((!ok||m!=n)&&(m!=0))

       if (m!=0) 輸出解;

       else         輸出無解報(bào)告；

}

    如果程序要找全部解，則在將找到的解輸出后，應(yīng)繼續(xù)調(diào)整最后位置上填放的整數(shù)，試圖去找下一個(gè)解。相應(yīng)的算法如下：

回溯法找全部解的算法：

{     int m=0,ok=1;

       int n=8;

       do{

              if (ok)    

{     if (m==n)      

{     輸出解；

調(diào)整；

}

else  擴(kuò)展;

                     }

                     else         調(diào)整;

              ok=檢查前m個(gè)整數(shù)填放的合理性;

       }     while (m!=0);

}

    為了確保程序能夠終止，調(diào)整時(shí)必須保證曾被放棄過的填數(shù)序列不會(huì)再次實(shí)驗(yàn)，即要求按某種有許模型生成填數(shù)序列。給解的候選者設(shè)定一個(gè)被檢驗(yàn)的順序，按這個(gè)順序逐一形成候選者并檢驗(yàn)。從小到大或從大到小，都是可以采用的方法。如擴(kuò)展時(shí)，先在新位置填入整數(shù)1，調(diào)整時(shí)，找當(dāng)前候選解中下一個(gè)還未被使用過的整數(shù)。將上述擴(kuò)展、調(diào)整、檢驗(yàn)都編寫成程序，細(xì)節(jié)見以下找全部解的程序。

【程序】

# include <stdio.h>

# define N     12

void write(int a[ ])

{     int i,j;

       for (i=0;i<3;i++)

       {     for (j=0;j<3;j++)

                     printf(“%3d”,a[3*i+j]);

              printf(“\n”);

       }

       scanf(“%*c”);

}

 

int b[N+1];

int a[10];

int isprime(int m)

{     int i;

       int primes[ ]={2,3,5,7,11,17,19,23,29,-1};

       if (m==1||m%2=0) return 0;

       for (i=0;primes[i]>0;i++)

              if (m==primes[i])   return 1;

       for (i=3;i*i<=m;)

       {     if (m%i==0)   return 0;

              i+=2;

       }

       return 1;

}

 

int checkmatrix[ ][3]={  {-1},{0,-1},{1,-1},{0,-1},{1,3,-1},

                                   {2,4,-1},{3,-1},{4,6,-1},{5,7,-1}};

int selectnum(int start)

{     int j;

       for (j=start;j<=N;j++)

              if (b[j]) return j

       return 0;

}

 

int check(int pos)

{     int i,j;

       if (pos<0)              return 0;

       for (i=0;(j=checkmatrix[pos][i])>=0;i++)

              if (!isprime(a[pos]+a[j])

                     return 0;

       return 1;

}

 

int extend(int pos)

{     a[++pos]=selectnum(1);

       b[a][pos]]=0;

       return pos;

}

 

int change(int pos)

{     int j;

       while (pos>=0&&(j=selectnum(a[pos]+1))==0)

              b[a[pos--]]=1;

       if (pos<0)              return –1

       b[a[pos]]=1;

       a[pos]=j;

       b[j]=0;

       return pos;

}

 

void find()

{     int ok=0,pos=0;

       a[pos]=1;

       b[a[pos]]=0;

       do {

              if (ok)

                     if (pos==8)

                     {     write(a);

                            pos=change(pos);

                     }

                     else  pos=extend(pos);

              else  pos=change(pos);

              ok=check(pos);

       }     while (pos>=0)

}

 

void main()

{     int i;

       for (i=1;i<=N;i++)

              b[i]=1;

       find();

}

 

上一頁  [1] [2] [3] [4] [5] [6] 下一頁