1、回溯法的一般描述
可用回溯法求解的問題P，通常要能表達(dá)為：對于已知的由n元組（x1，x2，…，xn）組成的一個狀態(tài)空間E={（x1，x2，…，xn）∣xi∈Si ，i=1，2，…，n}，給定關(guān)于n元組中的一個分量的一個約束集D，要求E中滿足D的全部約束條件的所有n元組。其中Si是分量xi的定義域，且 |Si| 有限，i=1，2，…，n。我們稱E中滿足D的全部約束條件的任一n元組為問題P的一個解。
解問題P的最樸素的方法就是枚舉法，即對E中的所有n元組逐一地檢測其是否滿足D的全部約束，若滿足，則為問題P的一個解。但顯然，其計(jì)算量是相當(dāng)大的。
我們發(fā)現(xiàn)，對于許多問題，所給定的約束集D具有完備性，即i元組（x1，x2，…，xi）滿足D中僅涉及到x1，x2，…，xi的所有約束意味著j（jj。因此，對于約束集D具有完備性的問題P，一旦檢測斷定某個j元組（x1，x2，…，xj）違反D中僅涉及x1，x2，…，xj的一個約束，就可以肯定，以（x1，x2，…，xj）為前綴的任何n元組（x1，x2，…，xj，xj+1，…，xn）都不會是問題P的解，因而就不必去搜索它們、檢測它們?；厮莘ㄕ轻槍@類問題，利用這類問題的上述性質(zhì)而提出來的比枚舉法效率更高的算法。
回溯法首先將問題P的n元組的狀態(tài)空間E表示成一棵高為n的帶權(quán)有序樹T，把在E中求問題P的所有解轉(zhuǎn)化為在T中搜索問題P的所有解。樹T類似于檢索樹，它可以這樣構(gòu)造：
設(shè)Si中的元素可排成xi(1) ，xi(2) ，…，xi(mi-1) ，|Si| =mi，i=1，2，…，n。從根開始，讓T的第I層的每一個結(jié)點(diǎn)都有mi個兒子。這mi個兒子到它們的雙親的邊，按從左到右的次序，分別帶權(quán)xi+1(1) ，xi+1(2) ，…，xi+1(mi) ，i=0，1，2，…，n-1。照這種構(gòu)造方式，E中的一個n元組（x1，x2，…，xn）對應(yīng)于T中的一個葉子結(jié)點(diǎn)，T的根到這個葉子結(jié)點(diǎn)的路徑上依次的n條邊的權(quán)分別為x1，x2，…，xn，反之亦然。另外，對于任意的0≤i≤n-1，E中n元組（x1，x2，…，xn）的一個前綴I元組（x1，x2，…，xi）對應(yīng)于T中的一個非葉子結(jié)點(diǎn)，T的根到這個非葉子結(jié)點(diǎn)的路徑上依次的I條邊的權(quán)分別為x1，x2，…，xi，反之亦然。特別，E中的任意一個n元組的空前綴（），對應(yīng)于T的根。
因而，在E中尋找問題P的一個解等價(jià)于在T中搜索一個葉子結(jié)點(diǎn)，要求從T的根到該葉子結(jié)點(diǎn)的路徑上依次的n條邊相應(yīng)帶的n個權(quán)x1，x2，…，xn滿足約束集D的全部約束。在T中搜索所要求的葉子結(jié)點(diǎn)，很自然的一種方式是從根出發(fā)，按深度優(yōu)先的策略逐步深入，即依次搜索滿足約束條件的前綴1元組（x1i）、前綴2元組（x1，x2）、…，前綴I元組（x1，x2，…，xi），…，直到i=n為止。
在回溯法中，上述引入的樹被稱為問題P的狀態(tài)空間樹；樹T上任意一個結(jié)點(diǎn)被稱為問題P的狀態(tài)結(jié)點(diǎn)；樹T上的任意一個葉子結(jié)點(diǎn)被稱為問題P的一個解狀態(tài)結(jié)點(diǎn)；樹T上滿足約束集D的全部約束的任意一個葉子結(jié)點(diǎn)被稱為問題P的一個回答狀態(tài)結(jié)點(diǎn)，它對應(yīng)于問題P的一個解。
【問題】 組合問題
問題描述：找出從自然數(shù)1、2、……、n中任取r個數(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）∣xi∈S ，i=1，2，3 } 其中：S={1，2，3，4，5}
約束集為： x1 顯然該約束集具有完備性。
問題的狀態(tài)空間樹T：
⊙ ⊙ ⊙ ⊙ ⊙
可用回溯法求解的問題P，通常要能表達(dá)為：對于已知的由n元組（x1，x2，…，xn）組成的一個狀態(tài)空間E={（x1，x2，…，xn）∣xi∈Si ，i=1，2，…，n}，給定關(guān)于n元組中的一個分量的一個約束集D，要求E中滿足D的全部約束條件的所有n元組。其中Si是分量xi的定義域，且 |Si| 有限，i=1，2，…，n。我們稱E中滿足D的全部約束條件的任一n元組為問題P的一個解。
解問題P的最樸素的方法就是枚舉法，即對E中的所有n元組逐一地檢測其是否滿足D的全部約束，若滿足，則為問題P的一個解。但顯然，其計(jì)算量是相當(dāng)大的。
我們發(fā)現(xiàn)，對于許多問題，所給定的約束集D具有完備性，即i元組（x1，x2，…，xi）滿足D中僅涉及到x1，x2，…，xi的所有約束意味著j（jj。因此，對于約束集D具有完備性的問題P，一旦檢測斷定某個j元組（x1，x2，…，xj）違反D中僅涉及x1，x2，…，xj的一個約束，就可以肯定，以（x1，x2，…，xj）為前綴的任何n元組（x1，x2，…，xj，xj+1，…，xn）都不會是問題P的解，因而就不必去搜索它們、檢測它們?；厮莘ㄕ轻槍@類問題，利用這類問題的上述性質(zhì)而提出來的比枚舉法效率更高的算法。
回溯法首先將問題P的n元組的狀態(tài)空間E表示成一棵高為n的帶權(quán)有序樹T，把在E中求問題P的所有解轉(zhuǎn)化為在T中搜索問題P的所有解。樹T類似于檢索樹，它可以這樣構(gòu)造：
設(shè)Si中的元素可排成xi(1) ，xi(2) ，…，xi(mi-1) ，|Si| =mi，i=1，2，…，n。從根開始，讓T的第I層的每一個結(jié)點(diǎn)都有mi個兒子。這mi個兒子到它們的雙親的邊，按從左到右的次序，分別帶權(quán)xi+1(1) ，xi+1(2) ，…，xi+1(mi) ，i=0，1，2，…，n-1。照這種構(gòu)造方式，E中的一個n元組（x1，x2，…，xn）對應(yīng)于T中的一個葉子結(jié)點(diǎn)，T的根到這個葉子結(jié)點(diǎn)的路徑上依次的n條邊的權(quán)分別為x1，x2，…，xn，反之亦然。另外，對于任意的0≤i≤n-1，E中n元組（x1，x2，…，xn）的一個前綴I元組（x1，x2，…，xi）對應(yīng)于T中的一個非葉子結(jié)點(diǎn)，T的根到這個非葉子結(jié)點(diǎn)的路徑上依次的I條邊的權(quán)分別為x1，x2，…，xi，反之亦然。特別，E中的任意一個n元組的空前綴（），對應(yīng)于T的根。
因而，在E中尋找問題P的一個解等價(jià)于在T中搜索一個葉子結(jié)點(diǎn)，要求從T的根到該葉子結(jié)點(diǎn)的路徑上依次的n條邊相應(yīng)帶的n個權(quán)x1，x2，…，xn滿足約束集D的全部約束。在T中搜索所要求的葉子結(jié)點(diǎn)，很自然的一種方式是從根出發(fā)，按深度優(yōu)先的策略逐步深入，即依次搜索滿足約束條件的前綴1元組（x1i）、前綴2元組（x1，x2）、…，前綴I元組（x1，x2，…，xi），…，直到i=n為止。
在回溯法中，上述引入的樹被稱為問題P的狀態(tài)空間樹；樹T上任意一個結(jié)點(diǎn)被稱為問題P的狀態(tài)結(jié)點(diǎn)；樹T上的任意一個葉子結(jié)點(diǎn)被稱為問題P的一個解狀態(tài)結(jié)點(diǎn)；樹T上滿足約束集D的全部約束的任意一個葉子結(jié)點(diǎn)被稱為問題P的一個回答狀態(tài)結(jié)點(diǎn)，它對應(yīng)于問題P的一個解。
【問題】 組合問題
問題描述：找出從自然數(shù)1、2、……、n中任取r個數(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）∣xi∈S ，i=1，2，3 } 其中：S={1，2，3，4，5}
約束集為： x1 顯然該約束集具有完備性。
問題的狀態(tài)空間樹T：
⊙ ⊙ ⊙ ⊙ ⊙