【算法】經典算法之回溯法

【算法】回溯法的應用

1. 概念

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

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

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

2. 基本思想

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

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

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

3. 回溯法解題的一般步驟

1. 針對所給問題，确定問題的解空間：首先應明确定義問題的解空間，問題的解空間應至少包含問題的一個（最優）解。
2. 确定結點的擴充搜尋規則
3. 以深度優先方式搜尋解空間，并在搜尋過程中用剪枝函數避免無效搜尋。

4.算法架構

1. 問題架構

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

1. 非遞歸回溯架構

int a[n],i;
	初始化數組a[];
	 i = 1;
	 while (i0(有路可走)   and  (未達到目标))   還未回溯到頭
	{
	    if(i  n)                                               搜尋到葉結點
	    {   
	           搜尋到一個解，輸出；
	     }
	     else                                                    處理第i個元素
	     { 
	           a[i]第一個可能的值；
	          while(a[i]在不滿足限制條件且在搜尋空間内)
	          {
	              a[i]下一個可能的值；
	          }
	          if(a[i]在搜尋空間内)
	         {
	              辨別占用的資源；
	              i = i+1;                               擴充下一個結點
	         }
	          else 
	        {
	              清理所占的狀态空間；             回溯
	              i = i –1; 
	         }
	 	}
}
           

1. 遞歸的算法架構

  回溯法是對解空間的深度優先搜尋，在一般情況下使用遞歸函數來實作回溯法比較簡單，其中i為搜尋的深度，架構如下：

int a[n];
    try(int i)
    {
        if(in)
          輸出結果;
         else
        {
           for(j = 下界; j = 上界; j=j+1)   枚舉i所有可能的路徑
           {
              if(fun(j))                  滿足限界函數和限制條件
                {
                   a[i] = j;
                 ...                          其他操作
                   try(i+1);
                 回溯前的清理工作（如a[i]置空值等）;
                 }
            }
        }
   }