1、概念

      回溯算法實際上一個類似枚舉的搜索嘗試過程,主要是在搜索嘗試過程中尋找問題的解,當發現已不滿足求解條件時,就“回溯”返回,嘗試別的路徑。

   回溯法是一種選優搜索法,按選優條件向前搜索,以達到目標。但當探索到某一步時,發現原先選擇并不優或達不到目標,就退回一步重新選擇,這種走不通就退回再走的技術為回溯法,而滿足回溯條件的某個狀態的點稱為“回溯點”。

     許多復雜的,規模較大的問題都可以使用回溯法,有“通用解題方法”的美稱。

2、基本思想

   在包含問題的所有解的解空間樹中,按照深度優先搜索的策略,從根結點出發深度探索解空間樹。當探索到某一結點時,要先判斷該結點是否包含問題的解,如果包含,就從該結點出發繼續探索下去,如果該結點不包含問題的解,則逐層向其祖先結點回溯。(其實回溯法就是對隱式圖的深度優先搜索算法)。

       若用回溯法求問題的所有解時,要回溯到根,且根結點的所有可行的子樹都要已被搜索遍才結束。

       而若使用回溯法求任一個解時,只要搜索到問題的一個解就可以結束。

3、用回溯法解題的一般步驟:

    (1)針對所給問題,確定問題的解空間:

            首先應明確定義問題的解空間,問題的解空間應至少包含問題的一個(最優)解。

    (2)確定結點的擴展搜索規則

    (3)以深度優先方式搜索解空間,并在搜索過程中用剪枝函數避免無效搜索。

4、算法框架

     (1)問題框架

      設問題的解是一個n維向量(a1,a2,………,an),約束條件是ai(i=1,2,3,…..,n)之間滿足某種條件,記為f(ai)。

     (2)非遞歸回溯框架

   1: int a[n],i;
   2: 初始化數組a[];
   3: i = 1;
   4: while (i>0(有路可走)   and  (未達到目標))  // 還未回溯到頭
   5: {
   6:     if(i > n)                                              // 搜索到葉結點
   7:     {   
   8:           搜索到一個解,輸出;
   9:     }
  10:     else                                                   // 處理第i個元素
  11:     { 
  12:           a[i]第一個可能的值;
  13:           while(a[i]在不滿足約束條件且在搜索空間內)
  14:           {
  15:               a[i]下一個可能的值;
  16:           }
  17:           if(a[i]在搜索空間內)
  18:          {
  19:               標識占用的資源;
  20:               i = i+1;                              // 擴展下一個結點
  21:          }
  22:          else 
  23:         {
  24:               清理所占的狀態空間;            // 回溯
  25:               i = i –1; 
  26:          }
  27: }

 

        (3)遞歸的算法框架

         回溯法是對解空間的深度優先搜索,在一般情況下使用遞歸函數來實現回溯法比較簡單,其中i為搜索的深度,框架如下:

   1: int a[n];
   2: try(int i)
   3: {
   4:     if(i>n)
   5:        輸出結果;
   6:      else
   7:     {
   8:        for(j = 下界; j <= 上界; j=j+1)  // 枚舉i所有可能的路徑
   9:        {
  10:            if(fun(j))                 // 滿足限界函數和約束條件
  11:              {
  12:                 a[i] = j;
  13:               ...                         // 其他操作
  14:                 try(i+1);
  15:               回溯前的清理工作(如a[i]置空值等);
  16:               }
  17:          }
  18:      }
  19: }