1.回溯法算法思想：
定義：
回溯法(探索與回溯法)是一種選優搜索法，按選優條件向前搜索，以達到目標。但當探索到某一步時，發現原先選擇并不優或達不到目標，就退回一步重新選擇，這種走不通就退回再走的技術為回溯法，而滿足回溯條件的某個狀態的點稱為“回溯點”。
1、回溯法適用：有許多問題，當需要找出它的解集（全部解）或者要求回答什么解是滿足某些約束條件的最優解時，往往要使用回溯法。
2、有組織的窮舉式搜索：回溯法的基本做法是搜索或者有的組織窮盡搜索。它能避免搜索所有的可能性。即避免不必要的搜索。這種方法適用于解一些組合數相當大的問題。
3、搜索解空間樹：回溯法在問題的解空間樹中，按深度優先策略，從根結點出發搜索解空間樹。算法搜索至解空間樹的任意一點時，先判斷該結點是否包含問題的解。如果肯定不包含（剪枝過程），則跳過對該結點為根的子樹的搜索，逐層向其祖先結點回溯；否則，進入該子樹，繼續按深度優先策略搜索。
為了實現回溯，我們先弄明白以下兩個問題：
1）首先應該明確問題的解空間。
2）其次是組織解空間以便它能用以被搜索到。
2. 問題的解空間 和空間樹
這個空間必須至少包含一個解（可能是最優的）。 一個復雜問題的解決往往由多部分構成，即，一個大的解決方案可以看作是由若干個小的決策組成。很多時候它們構成一個決策序列。解決一個問題的所有可能的決策序列構成該問題的解空間。解空間中滿足約束條件的決策序列稱為可行解。一般說來，解任何問題都有一個目標，在約束條件下使目標值達到最大（或最?。┑目尚薪夥Q為該問題的最優解。在解空間中，前k項決策已經取定的所有決策序列之集稱為k定子解空間。0定子解空間即是該問題的解空間。
問題的解空間通常是在搜索問題的解的過程中動態產生的，這是回溯算法的一個重要特性。
解空間的確定與我們對問題的描述有關。如何組織解空間的結構會直接影響對問題的求解效率。這是因為回溯方法的基本思想是通過搜索解空間來找到問題所要求的解。一般地，可以用一棵樹來描述解空間，稱為解空間樹。
當所給的問題是從n個元素的集合S中找出滿足某種性質的子集時，相應的解空間樹稱為子集合樹。此時，解空間有
個元素，遍歷子集樹的任何算法均需的計算時間。
如例:定和子集問題： 已知一個正實數的集合P= {W1,w2, … Wn}和另一個正實數M．試求P的所有子集S，使得S中的數之和等于M。這個問題的解可以表
示成0/1數組{x1,x2,…,xn}，依據W1是否屬于S， X1分別取值1或0。故解空間中共有個元素。它的樹結構是一棵完整二叉樹。
當所給的問題是確定n個元素的滿足某種性質的排列時，相應的解空間樹稱為排列樹，此時，解空間有個元素。遍歷排列樹的任何算法均需的計算時間，均需的
計算時間。
我們把這個例子逐一解析：
問題的解向量：問題的解能夠表示成一個n元式(x1,x2,…,xn)的形式。
顯約束：對分量xi的取值限定。
隱約束：為滿足問題的解而對不同分量之間施加的約束。
解空間：對于問題的一個實例，解向量滿足顯式約束條件的所有多元組，構成了該實例的一個解空間。
注意：同一個問題可以有多種表示，有些表示方法更簡單，所需表示的狀態空間更小（存儲量少，搜索方法簡單）。
下面是n=3時的0-1背包問題用完全二叉樹表示的解空間：
為了敘述方便，引進一些關于解空間樹結構的術語。解空間樹上的每個節點確定求解問題的一個問題狀態，它由一條從根到該節點的路徑描述。由根到所有其它節點的路徑描述了這個問題的狀態空間。解狀態是這樣一些問題狀態S，對于這些問題狀態，由根到S的那條路徑確定了解空間的一個元組。即答案狀態是這樣的一些解狀態S，對于這些解狀態而言，由根到S的這條路徑確定了這個問題的一個解（即可行解），解空間的樹結構稱為狀態空間樹。
確定了解空間的組織結構后，回溯法就從初始節點（解空間樹的根節點）出發，以深度優先的方式搜索整個解空間。這個開始節點就成為一個活節點，同時也成為當前的擴展節點。在當前擴展節點處，搜索向縱深方向移至一個新節點。這個新節點就成為一個新的活節點，并且成為當前的擴展節點。如果在當前的擴展節點處不能再向縱深方向搜索，則當前的擴展節點就成為死節點。此時應往回移動（回溯）至最近一個活節點處，并使這個活節點成為當前擴展節點。如此繼續。回溯法就是以這種工作方式遞歸地在解空間中搜索，直至找到要求的解或解空間中已無活節點時為止。
事實上，當我們將問題的有關數據以一定的數據結構存儲好以后（例如，旅行商問題存儲賦權圖的鄰接矩陣、定和子集問題是存儲已知的n+1個數、4皇后問題用整數對(i,j)表示棋盤上各個位置，不必先建立一個解空間樹），就搜索生成解空間樹的一部分或全部，并尋找所需要的解。也就是說，對于實際問題不必生成整個狀態空間樹，然后在整個解空間中搜索，我們只需有選擇地搜索。為了使搜索更加有效，常常在搜索過程中加一些判斷以決定搜索是否該終止或改變路線。通常采用兩種策略來避免無效的搜索，提高回溯法的搜索效率：
其一是使用約束函數，在擴展節點處剪去不滿足約束的子樹；
其二是用限界函數， “剪去”不能達到最優解的子樹。
這兩種函數統稱為剪枝函數。
總結：
擴展結點:一個正在產生兒子的結點稱為擴展結點
活結點:一個自身已生成但其兒子還沒有全部生成的節點稱做活結點
死結點:一個所有兒子已經產生的結點稱做死結點
深度優先的問題狀態生成法：如果對一個擴展結點R，一旦產生了它的一個兒子C，就把C當做新的擴展結點。在完成對子樹C（以C為根的子樹）的窮盡搜索之后，將R重新變成擴展結點，繼續生成R的下一個兒子（如果存在）
寬度優先的問題狀態生成法：在一個擴展結點變成死結點之前，它一直是擴展結點。
回溯法：為了避免生成那些不可能產生最佳解的問題狀態，要不斷地利用限界函數(bounding function)來處死(剪枝)那些實際上不可能產生所需解的活結點，以減少問題的計算量。具有限界函數的深度優先生成法稱為回溯法。（回溯法 = 窮舉 + 剪枝）。
3.回溯法的思路
描述問題：
定義可用回溯法求解的問題P：對于已知的由n元組（x1，x2，…，xn）組成的一個狀態空間E={（x1，x2，…，xn）∣xi∈Si ，i=1，2，…，n}，給定關于n元組中的一個分量的一個約束集D，要求E中滿足D的全部約束條件的所有n元組。其中Si是分量xi的定義域，且 |Si| 有限，i=1，2，…，n。我們稱E中滿足D的全部約束條件的任一n元組為問題P的一個解。
解問題P的最樸素的方法就是枚舉法，即對E中的所有n元組逐一地檢測其是否滿足D的全部約束，若滿足，則為問題P的一個解。但顯然，其計算量是相當大的。
基本思路：
若已有滿足約束條件的部分解，不妨設為（x1,x2,x3,……xi），I<n,則添加x(i+1)屬于s(i+2)，檢查 (x1,x2,……,xi,x(i+1))是否滿足條件，滿足了就繼續添加x(i+2)、s(i+2)，若所有的x(i+1)屬于s(i+1)都不能得到 部分解，就去掉xi，回溯到(xi,x2,……x(i- 1))，添加那些未考察過的x1屬于s1，看其是否滿足約束條件，為此反復進行，直至得到解或證明無解。
這個回溯法明顯提高算法效率。
4.回溯法的步驟
總結起來，運用回溯法解題通常包括以下三個步驟
1).確定問題的解空間 ：針對所給問題，定義問題的解空間；
子集樹問題：裝載問題、符號三角形問題、0-1背包問題、最大團問題
排列樹問題：批處理作業調度、n后問題、旅行售貨員問題、圓排列問題、電路板排列問題
其他：圖的m著色問題
2).確定易于搜索的解空間結構：
找出適當的剪枝函數，約束函數和限界函數。
3).以深度優先的方式搜索解空間，并且在搜索過程中用剪枝函數避免無效的搜索。
遞歸回溯
迭代回溯
4）利用限界函數避免移動到不可能產生解的子空間
5.算法框架
1. 遞歸回溯：
回溯法對解空間作深度優先搜索，因此，在一般情況下用遞歸方法實現回溯法。
void backtracking (int t)
{
if (t > n) {
// 到達葉子結點，將結果輸出
output (x);
}
else {
// 遍歷結點t的所有子結點，即枚舉t所有可能的路徑
// f(n,t)=下界;g(n,t)=上界;
for (int i = f(n,t); i <= g(n,t); i ++ ) {//
x[t] = h[i];//滿足界限函數和約束函數
// 如果不滿足剪枝條件，則繼續遍歷，進入下一層
if (constraint (t) && bound (t))
backtrack (t + 1);
}
}
}
t是遞歸深度；
n是深度控制，即解空間樹的的高度；
可行性判斷有兩方面的內容：不滿約束條件則剪去相應子樹；若限界函數越界，也剪去相應子樹；兩者均滿足則進入下一層；
2. 迭代回溯
采用樹的非遞歸深度優先遍歷算法，可將回溯法表示為一個非遞歸迭代過程。
// 針對N叉樹的迭代回溯方法
void iterativeBacktrack ()
{
int t = 1;
while (t > 0) { //有路可走
if (f(n,t) <= g(n,t)) {
// 遍歷結點t的所有子結點
for (int i = f(n,t); i <= g(n,t); i ++) {
x[t] = h(i);
// 剪枝
if (constraint(t) && bound(t)) {
// 找到問題的解，輸出結果
if (solution(t)) {
output(x);
}
else // 未找到，向更深層次遍歷
t ++;
}
}
}
else {
t–;
}
}
}
6. 回溯法依賴的兩種數據結構
回溯法通常在解空間樹上進行搜索，一般依賴的兩種數據結構：子集樹和排列樹
子集樹（遍歷子集樹需O(2^n)計算時間）：
一般有裝載問題、符號三角形問題、0-1背包問題、最大團問題
void backtrack (int t)
{
if (t > n)
// 到達葉子結點
output (x);
else
for (int i = 0;i <= 1;i ++) {
x[t] = i;
// 約束函數
if ( legal(t) )
backtrack( t+1 );
}
}
排列樹（遍歷排列樹需要O(n!)計算時間）：
一般有批處理作業調度、n后問題、旅行售貨員問題、圓排列問題、電路板排列問題
void backtrack (int t)
{
if (t > n)
output(x);
else
for (int i = t;i <= n;i++) {
// 完成全排列
swap(x[t], x[i]);
if (legal(t))
backtrack(t+1);
swap(x[t], x[i]);
}
}
其中f(n,t),g(n,t)表示當前擴展結點處未搜索過的子樹的起始標號和終止標號, h(i)表示當前擴展節點處，x[t]第i個可選值constraint(t)和bound(t)是當前 擴展結點處的約束函數和限界函數。constraint(t)返回true時，在當前擴展結點 x[1:t]取值滿足約束條件，否則不滿足約束條件，可減去相應的子樹。bound(t)返 回的值為true時，在當前擴展結點x[1:x]處取值未使目標函數越界，還需要由backtrack(t+1) 對其相應的子樹進一步搜索。
7.回溯法的應用
應用回溯法有：
-
1）裝載問題
-
2）批處理作業調度
-
3）符號三角形問題
-
4）n后問題
-
5）0-1背包問題
-
6）最大團問題
-
7）圖的m著色問題
-
8）旅行售貨員問題
-
9）圓排列問題
-
10）電路板排列問題
-
11）連續郵資問題
n皇后問題：
1.問題表述：在n×n格的棋盤上放置彼此不受攻擊的n個皇后。按照國際象棋的規則，皇后可以攻擊與之處在同一行或同一列或同一斜線上的棋子。n后問題等價于在n×n格的棋盤上放置n個皇后，任何2個皇后不放在同一行或同一列或同一斜線上。求不同的解的個數。
復雜問題從簡單問題入手，我們先分析四皇后的問題，四叉樹展示了求解的過程：
2. 問題分析：
(1) 解空間：一組n元一維向量(x1, x2, x3, … , xn),搜索空間是：1<=xi<=n， i=1,2,3,…,n
(2) 約束條件：
1)不同列：xi != xj
2)不處于同一正、反對角線：|i-j| != |x(i)-x(j)|
3. 代碼實現：
-
// stdafx.h : include file for standard system include files, // or project specific include files that are used frequently, but // are changed infrequently // #pragma once #include <stdio.h> #include "stdlib.h" #include <iostream> using namespace std; //宏定義 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 typedef int Status; typedef int ElemType;
Test.cpp
// Test.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <vector>
class queen
{
// 皇后在棋盤上的位置
struct q_place {
int x;
int y;
q_place ()
: x(0),y(0)
{}
};
public:
queen(int qc)
: q_count (qc), sum_solution (0) {
curr_solution.resize (q_count);
}
void backtrack () {
_backtracking (0);
}
private:
/************************************************************************/
/* 判斷對應的位置是否存在當前的方案中
*/
/************************************************************************/
bool _isCoordinate(int x, int y)
{
for (size_t i = 0;i < curr_solution.size(); ++ i) {
if (curr_solution[i].x ==x && curr_solution[i].y == y) {
return true;
}
}
return false;
}
/************************************************************************/
/* 打印當前的位置
*/
/************************************************************************/
void _printResult()
{
for (size_t i = 0;i < curr_solution.size(); ++ i) {
for(size_t j = 0;j < curr_solution.size(); ++j) {
if (_isCoordinate(i, j)) {
cout<<"1 ";
}else{
cout<<"0 ";
}
}
cout<< endl;
}
cout << "sum_solution = " << sum_solution << endl;
}
/************************************************************************/
/* 現在從第i行算起繼續為后續的棋子選擇合適的位置
*/
/************************************************************************/
void _backtracking (int i)
{
if (i >= q_count) { //找到一個解決方案，將結果輸出
++ sum_solution ;
_printResult();
}
else {
for (int j = 0;j < q_count; ++ j) {
//將第i行第j列放置一個棋子
curr_solution[i].x = j;
curr_solution[i].y = i;
if (isOk(i)) { //當前布局合法
_backtracking (i + 1);
}
}
}
}
/************************************************************************/
/* 判斷第k個皇后的位置是否與前面的皇后相沖突
*/
/************************************************************************/
bool isOk(int k)
{
for (int i = 0; i < k; ++ i) {
if ((abs(curr_solution[i].x - curr_solution[k].x) == abs(curr_solution[i].y - curr_solution[k].y))
|| curr_solution[i].x == curr_solution[k].x) {
return false;
}
}
return true;
}
private:
vector<q_place> curr_solution; // 當前解決方案
const int q_count; // 皇后個數
int sum_solution; // 當前找到的解決方案的個數
};
int main()
{
queen q(5);
q.backtrack ();
return 0;
}
定和0/1背包問題
問題表述：給定n種物品和一背包。第i件物品的重量是wi，其價值為pi，背包的容量為C。問應如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大?
0-1背包問題是一個數規劃問題：確定一個向量：x=（x1,x2,…,xn）滿足：
例如：n=3但是時候：W = (10, 8,5)p = (5,5,1)C = 16;最優解為：(1,01),此時價值為：6
0/1背包問題用完全二叉樹表示的解空間：
問題分析：
(1) 解空間：一組n元一維向量(x1, x2, x3, … , xn),搜索空間是：1<=xi<=n， i=1,2,3,…,n
(2) 約束條件：
可行性約束函數：
上界函數：
考慮一個右子樹的時候，設
r：是當前未考慮的剩余物品的總價值(remainder)
cp：是當前的價值(current price)
bestp：是當前得到的最優價值(best price)
那么，滿足：
但是，上界r太松。
一個更加緊的上界：
將剩余物品按照單位重量價值排序，然后依次裝入物品，直到裝不下，再將剩余物品的一部分放入背包。(r_n <= r)
c語言實現：
// TestWin32.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
int curr_weight = 0; //當前重量
int curr_value = 0; //當前價值
int bestv = 0; //最優解
int x_length = 0; //
/************************************************************************/
/* 將物品按單位價格降序排序 */
/************************************************************************/
void sortItem(itemGoods *item, int n){
itemGoods temp;
for(int i = 0; i < n-1; ++i){
for(int j = i+1; j < n; ++j){
if((item[i].v/item[i].w) < (item[j].v/item[j].w)){
temp = item[i];
item[i] = item[j];
item[j] = temp;
}
}
}
}
/************************************************************************/
/* 邊界函數 ： 計算上界
@int C, 背包容量
@int i 第i個物品
@int n 物品個數
*/
/************************************************************************/
int bound(itemGoods *item, int capacity, int i, int n){
int capacity_left = capacity - curr_weight;
int value_left = curr_value;
// 按物品單位價值遞減序裝入物品
while(i <= n && item[i].w <= capacity_left){
capacity_left -= item[i].w;
value_left += item[i].v;
++i;
}
//裝滿背包
if(i <= n)
value_left += item[i].v * capacity_left / item[i].w;
return value_left;
}
/************************************************************************/
/* 遞歸回溯
@int capacity, 背包容量
@int i 第i個物品
@int n 物品個數
*/
/************************************************************************/
void backtrack(itemGoods *item, int capacity, int i, int n, int *bestX){
if(i >= n){
//到達葉子結點，更新最優價值
if(bestv < curr_value){
bestv = curr_value;
x_length = 0;
for(int i = 0; i < n; ++i)
if(item[i].visited){
bestX[x_length] = item[i].id;
++x_length;
}
}
return;
}
//搜索左子樹：左剪枝，能放的下的物品
if(curr_weight + item[i].w <= capacity){
curr_weight += item[i].w;
curr_value += item[i].v;
item[i].visited = true;
backtrack(item,capacity,i+1,n,bestX);
curr_weight -= item[i].w;
curr_value -= item[i].v;
}
//搜索右子樹：放不下的物品
if(bound(item,capacity,i,n) > bestv)
item[i].visited = false;
backtrack(item,capacity,i+1,n,bestX);
}
int Knapsack(itemGoods *item, int n, int capacity, int *bestX){
sortItem(item,n);
backtrack(item,capacity,0,n,bestX);
return bestv;
}
void initGoods(itemGoods *item,int n){
cout << "物品信息：" << endl;
for(int i = 0; i < n; ++i){
item[i].id = i;
item[i].visited = false;
cout << "物品" <<i<<"重量：";
cin >> item[i].w;
cout << "物品" <<i<<"價值：";
cin >> item[i].v;
}
}
void printKnapsack(int *bestX, int max_value){
cout << "背包的物品id:" << endl;
for(int i = 0; i < x_length; ++i)
cout << bestX[i]+1 << "\t";
cout << endl;
cout << "最大價值： " << max_value << endl;
}
int main(){
int n;
cout << "物品數量:" << endl;
cin >> n;
int capacity;
cout << "背包容量:" << endl;
cin >> capacity;
itemGoods *item = new itemGoods[n];
initGoods(item, n);
int *bestX = new int[n]; //當前最優解
int max_value = Knapsack(item,n,capacity, bestX);
printKnapsack(bestX, max_value);
return 0;
}
c++實現：
// stdafx.h : include file for standard system include files,
// or project specific include files that are used frequently, but
// are changed infrequently
//
#pragma once
#include "targetver.h"
#include <stdio.h>
#include "stdlib.h"
#include <iostream>
using namespace std;
//宏定義
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status ;
typedef int ElemType ;
typedef struct itemGoods{
int id;
bool visited;
int w;
int v;
}itemGoods ;
class knapsack{
private:
itemGoods *item ;
int capacity; //背包容量
int n; //物品數
int curr_weight;//當前重量
int curr_value; //當前價值
Status bestV; //當前最優值
int *bestX; //當前最優解
int x_length; //最優解的數量
private:
void _sortItem();
int _bound(int i);
void _backtrack(int i); //遞歸回溯函數
public:
knapsack (itemGoods *item, int c,int n)
:capacity(c), n(n), curr_value(0), bestV (0), curr_weight(0),x_length(0),item(item)
{
bestX = new int[n];
bestX[0]=0;
}
int backtrack () ;
void printKnapsack();
};
Test.cpp
// Test.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
/************************************************************************/
/* 邊界函數 ： 計算上界
*/
/************************************************************************/
int knapsack::_bound(int i)
{
//計算上界
int cleft = capacity - curr_weight;
int value_left = curr_value;
//以物品單位重量價值遞減序裝入物品
while(i < n && item[i].w <= cleft) {
cleft -= item[i].w;
value_left += item[i].v;
i++;
}
//裝滿背包
if(i< n)
value_left += item[i].v/item[i].w * cleft;
return value_left;
}
/************************************************************************/
/* 遞歸回溯
*/
/************************************************************************/
void knapsack::_backtrack(int i)
{
if(i>=n) {
if(bestV < curr_value) {
bestV = curr_value;
x_length = 0;
for(int j = 0;j < n;j++)
if(item[j].visited) {
bestX[j] = item[j].id;
++x_length;
}
}
return;
}
if(curr_weight + item[i].w <= capacity) { //搜索左子樹
item[i].visited = TRUE;
curr_weight += item[i].w;
curr_value += item[i].v;
_backtrack(i+1);
curr_weight -= item[i].w;
curr_value -= item[i].v;
}
if(_bound(i+1)>bestV) { //搜索右子樹
item[i].visited = FALSE;
_backtrack(i+1);
}
}
/************************************************************************/
/* 排序 :將物品按單位價格降序排序
*/
/************************************************************************/
void knapsack::_sortItem(){
itemGoods temp;
for(int i = 0; i < n-1; ++i){
for(int j = i+1; j < n; ++j){
if((item[i].v/item[i].w) < (item[j].v/item[j].w)){
temp = item[i];
item[i] = item[j];
item[j] = temp;
}
}
}
}
int knapsack::backtrack () {
_sortItem();
_backtrack(0);
return bestV;
}
void knapsack::printKnapsack(){
cout << "背包的物品id:" << endl;
for(int i = 0; i < x_length; ++i)
cout << bestX[ i] << "\t";
cout << endl;
cout << "最大價值： " << bestV << endl;
}
int main(){
int n = 3;
cout << "物品數量:" << endl;
//cin >> n;
int capacity = 5;
cout << "背包容量:" << endl;
//cin >> capacity;
itemGoods *item = new itemGoods[n];
//初始化物品
//cout << "物品信息：" << endl;
//for(int i = 0; i < n; ++i){
// item[i].id = i;
// item[i].visited = FALSE;
// cout << "物品" <<i<<"重量：";
// cin >> item[i].w;
// cout << "物品" <<i<<"價值：";
// cin >> item[i].v;
//}
item[0].id = 0;
item[0].visited = FALSE;
item[0].w =2;
item[0].v = 2;
item[1].id = 1;
item[1].visited = FALSE;
item[1].w = 2;
item[1].v = 2;
item[2].id = 2;
item[2].visited = FALSE;
item[2].w =4;
item[2].v = 10;
knapsack ks(item,capacity,n);
int max_value = ks.backtrack();
ks.printKnapsack();
return 0;
}
轉自：http://blog.csdn.net/hguisu/article/details/7709276
原創文章，作者：s19930811，如若轉載，請注明出處：http://www.www58058.com/2796
