五大經典算法之回溯法

一、基本概念

  回溯法，又稱為試探法，按選優條件向前不斷搜尋，以達到目标。但是當探索到某一步時，如果發現原先選擇并不優或達不到目标，就會退回一步重新選擇，這種達不到目的就退回再走的算法稱為回溯法。

與窮舉法的差別和聯系：

相同點：它們都是基于試探的。

差別：窮舉法要将一個解的各個部分全部生成後，才檢查是否滿足條件，若不滿足，則直接放棄該完整解，然後再嘗試另一個可能的完整解，它并沒有沿着一個可能的完整解的各個部分逐漸回退生成解的過程。而對于回溯法，一個解的各個部分是逐漸生成的，當發現目前生成的某部分不滿足限制條件時，就放棄該步所做的工作，退到上一步進行新的嘗試，而不是放棄整個解重來。

二、基本思想

  對于可以使用回溯法來解決的問題，首先可以将其解空間可以看成一棵解空間樹。在回溯法中，每次擴大目前部分解時，都面臨一個可選的狀态集合（所有的子樹），每個樹結點代表一個可能的部分解。

  回溯法對任一解的生成，一般都采用逐漸擴大解的方式。每前進一步，都試圖在目前部分解的基礎上擴大該部分解。它在問題的狀态空間樹中，從開始結點（根結點）出發，以深度優先搜尋整個狀态空間。這個開始結點成為活結點，同時也成為目前的擴充結點。在目前擴充結點處，搜尋向縱深方向移至一個新結點。這個新結點成為新的活結點，并成為目前擴充結點。如果在目前擴充結點處不能再向縱深方向移動，則目前擴充結點就成為死結點。此時，應往回移動（回溯）至最近的活結點處，并使這個活結點成為目前擴充結點。回溯法以這種工作方式遞歸地在狀态空間中搜尋，直到找到所要求的解或解空間中已無活結點時為止。

三、解題步驟(思路)

1. 針對給定的問題，定義問題的解空間；
2. 确定易于搜尋的解空間結構；
3. 以深度優先方式搜尋解空間，并且在搜尋過程中用剪枝函數避免無效搜尋。（這裡的剪枝函數就是判斷該結點是否滿足問題題設，如果滿足則向下搜尋，不滿足則在此剪枝）

四、算法架構

1. 遞歸實作：

 變量解釋：

  x：存儲試探解的數組

  n：解空間樹的層數

  i：搜尋目前所達到的層數

  start：子節點解空間的最小值

  end：子節點解空間的最大值

int x[n];
void backtrack (int i) {
    if (i > n) {
       回溯結束； 
    } else {
        // 這裡回溯子節點的解空間為start~end
       for (j = start; j <= end; j++) {
            // 滿足條件，向下搜尋
            if (j滿足題設條件) {
                x[i] = j;
                backtrack(i+1);
            // 不滿足條件，在此剪枝（即回溯）
            } else {
            }
       }
   }
}   
           

 2. 非遞歸實作：

void f_backtrack(int i) {
  //初始化解向量
  for (int j = 0; j < n; j++) {
    x[j] = 1;
  }
  while (i >= 1) {
    while (x[i] <= n) {
      if (place(i)) {
        if (i == n) {
          回溯結束；
          break;
        // 滿足條件，向下搜尋
        } else {
          i++;
          x[i] = 1;
        }
      // 不滿足條件，在此剪枝（即回溯）
      } else {
        x[i]++;
      }
    }
    //周遊完子節點解空間後，向上剪枝（即回溯）
    x[i] = 1;
    i--;
    x[i]++;
  }
}  
           

相比之下，遞歸設計方法比較簡單，而非遞歸方法，也就是循環方法設計細節比較多，但如果掌握了其特點，對不同問題的适用性很強（即代碼隻需要很少的修改就可以應用到不同問題），加之其最大的優勢：效率更高（因為遞歸的實作是通過調用函數本身，函數調用的時候，每次調用時要做位址儲存，參數傳遞等，這是通過一個遞歸工作棧實作的。具體是每次調用函數本身要儲存的内容包括：局部變量、形參、調用函數位址、傳回值。那麼，如果遞歸調用N次，就要配置設定N局部變量、N形參、N調用函數位址、N傳回值。這勢必是影響效率的。）

五、經典實作

經典問題：八皇後問題

  八皇後問題，是一個古老而著名的問題，是回溯算法的典型例題。該問題是十九世紀著名的數學家高斯1850年提出：

  在8X8格的國際象棋上擺放八個皇後，使其不能互相攻擊，即任意兩個皇後都不能處于同一行、同一列或同一斜線上（斜率為1），問有多少種擺法。高斯認為有76種方案。1854年在柏林的象棋雜志上不同的作者發表了40種不同的解，後來有人用圖論的方法解出92種結果。

遞歸實作為以下代碼中backtrack方法

非遞歸實作為以下代碼中f_backtrack方法：

#include <iostream>
using namespace std;
int n;
int *x;
int sum;
bool place(int k)
{
  for (int j = 1; j < k; j++)
    if (abs(x[k] - x[j]) == abs(k - j) || x[j] == x[k])
      return false;
  return true;
}

void output()
{
  sum++; //sum為所有的可行的解
  for (int m = 1; m <= n; m++)
  {
    cout << "<" << m << "," << x[m] << ">"; //這一行用輸出當遞歸到葉節點的時候，一個可行解
  }
  cout << endl;
}

void f_backtrack(int i)
{
  for (int j = 0; j < n; j++)
  { //初始化解向量
    x[j] = 1;
  }
  while (i >= 1)
  {
    while (x[i] <= n)
    {
      if (place(i))
      { //得到可行解
        if (i == n)
        {
          output();
          break;
        } //得到最終可行解，退出
        else
        { //得到部分可行解，搜尋下一行
          i++;
          x[i] = 1;
        }
      }
      else
      { //目前解不可行
        x[i]++;
      }
    }
    x[i] = 1;
    i--;
    x[i]++; //回溯
  }
}

void backtrack(int i)
{
  if (i > n)
  {
    output();
  }
  else
  {
    for (int j = 1; j <= n; j++)
    {
      x[i] = j;
      if (place(i))
      {
        backtrack(i + 1);
      }
      else
      {
      }
    }
  }
}

int main()
{
  n = 8;
  sum = 0;
  x = new int[n + 1];
  for (int i = 0; i <= n; i++)
    x[i] = 0;
  backtrack(1);
  cout << "方案共有" << sum << endl;
}