回溯法是搜尋問題解的一種系統方法。回溯法求解首先需要定義一個解空間，這個空間至少包含問題的一個最優解。回溯法的下一步是組織解空間，使空間便于搜尋，典型的組織方式是樹或者圖。
一旦确定了解空間的組織方式，這個空間即可按照深度優先的方式從節點進行搜尋。在0-1背包問題中，開始節點為根節點，開始節點為一個活動節點又是一個E-節點。從E-節點試着移動到一個新的節點。如果從目前的E-節點移動到一個新的節點，那麼這個新節點就變成一個活動節點和新的E-節點。而原來的E-節點仍然是一個活動節點。若不能移動到一個新的節點，那麼目前的E-節點死掉，即不再是活動節點。然後回到最近的活動節點，這個活動節點變成新的E-節點。當已經找到答案或者不再有活動節點的時候，搜尋過程結束。
0-1背包問題
考察如下背包問題：n=3,w=[20,15,15],p=[40,25,25],c=30.從根節點開始搜尋圖20-2中的樹，根節點是目前唯一活動的節點，也是E-節點。從這裡可以移動到B節點和C節點，假定移動到B，則目前活動節點為A和B，B也是目前E-節點，在節點B，剩餘容量為10，而收益為cp=40。從B節點可以移動到D、E節點，但是移動到D節點是不可行的，因為移動到D節點所需要的容量為15. 移動到E是可行的，因為移動到E不需要占據任何容量。E變成新的E-節點，此時活動節點變成A、B、E。在節點E，剩餘容量r=10,cp=40。再從E點移動到J和K，很明顯，移動到J是不可行的，移動到K是可行的。節點K變成新的E-節點。因為K是葉子節點，是以得到一個可行解。這個解的收益是cp=40。X的值有根節點到K的路徑決定（X[i]=1表示裝入背包，X[i]=0表示不裝入背包）。因為K節點不能進一步擴充，是以K節點死亡，回溯到E節點，而E節點也不能進一步擴充，故E節點也死了。
接着再回溯到B節點，B節點也死亡了。A節點再次變成E-節點，它可以進一步進行擴充，到達節點C，此時剩餘容量r=30,cp=0。從C節點可以移動到F、G節點，假定移動到F節點，F變成新的E-節點，活動節點變成A、C、F.。在F節點，r=15,cp=25。從F節點可以移動到L、M節點。假定移動到L，此時r=0,cp=50。既然L為葉子節點，且它代表了目前最優解更好的解，我們将這個解作為最優解。節點L死亡，向上回溯到F節點。再移動到M節點，M節點死亡，再回溯到F節點，F死亡，再回溯到C節點，再移動到G節點...搜尋整棵樹，在搜尋期間發現的最好解即為最優解。
回溯方法的步驟如下：
1.定義一個解空間，它包含對問題執行個體的解。
2.用适合搜尋的方式組織解空間。
3.用深度優先方式搜尋解空間，利用界定函數避免進入無解的子空間
回溯算法的實作有一個特性：在搜尋的同時産生解空間，在搜尋過程的任何節點時刻，僅保留從開始節點到目前E-節點的路徑。
下面具體分析一個0-1背包執行個體：
n=4,c=7,w=[3,5,2,1],p=[9,10,7,4]。對象的收益密度為[3,2,3.5,4]。當以收益密度遞減的順序裝包的時候，首選對象4，然後是對象3，然後是對象1。當這三個對象裝入背包的時候，剩餘容量為1，剩餘容量可容納0.2重量的2對象，可産生收益為2，生成的解為x=[1,0.2,1,1]，相應的收益為22，雖然該解不可行，但是可行的最優解一定少于該解。
該題的解空間樹為圖20-2再加上一層節點，當位于解空間的節點B時，x[1] = 1,收益cp = 9,該節點所用容量cw=3，剩餘容量cleft=c-cw = 4.
當位于節點C時，cp=cw=0，cleft = c = 7.。按密度遞減順序填充剩餘容量，先把對象4和3裝入背包，然後将對象2的0.8倍裝入背包。這樣産生的收益為19。
在節點E，cp=9,cw=3,cleft=4。僅剩對象3和4需要考慮，按照密度遞減順序考慮，先将對象4裝入背包，然後是對象3.是以在E節點中無節點有多于cp+4+7=20的收益，若已經找到一個收益為20或者更多的解，搜尋則不必搜尋E子樹。
以下是完整的C++程式代碼：
// ConsoleApplication3.cpp : 定義控制台應用程式的入口點。
//
#include "stdafx.h"
#include <stdio.h>
#include <conio.h>
//定義全局變量
int n=4; //物品數量
double c=7; //背包容量
double v[10]; //各個物品的價值
double w[10]; //各個物品的重量
double cw = 0.0; //目前背包重量
double cp = 0.0; //目前背包中物品價值
double bestp = 0.0;//目前最優價值
double perp[10]; //機關物品價值排序後
int order[10]; //物品編号
int put[10]; //設定是否裝入
//按機關價值排序
void knapsack()
{
int i, j;
int temporder = 0;
double temp = 0.0;
for (i = 1; i <= n; i++)
perp[i] = v[i] / w[i];
//冒泡排序
for (i = 1; i <= n-1; i++)
{
for (j = i + 1; j < n; j++)
{
if (perp[i] < perp[j])
{
temporder = order[i];
order[i] = order[j];
order[j] = temporder;
temp = perp[i];
perp[i] = perp[j];
perp[j] = perp[i];
temp = v[i];
v[i] = v[j];
v[j] = temp;
temp = w[i];
w[i] = w[j];
w[j] = temp;
}
}
}
return;
}
//計算上界函數
double bound(int i)
{
double leftw = c - cw;
double b = cp;
while (i <= n && w[i] <= leftw)
{
leftw -= w[i];
b += v[i];
i++;
}
if (i <= n)
b += v[i] / w[i] * leftw;
return b;
}
//回溯函數
void backtrack(int i)
{
if (i > n)
{
bestp = cp;
return;
}
if (cw + w[i] <= c)
{
cw += w[i];
cp += v[i];
put[i] = 1;
backtrack(i + 1);
cw -= w[i];
cp -= v[i];
}
//符合條件搜尋右子樹
if (bound(i + 1) > bestp)
backtrack(i + 1);
return;
}
int main()
{
int i;
w[1] = 3;
w[2] = 5;
w[3] = 2;
w[4] = 1;
v[1] = 9;
v[2] = 10;
v[3] = 7;
v[4] = 4;
for(i=1;i<=n;i++)
{
order[i] = i;
}
//先排序
knapsack();
backtrack(1);
printf("最優價值：%.2f\n", bestp);
for (i = 1; i <= n; i++)
{
if (put[i] == 1)
printf("%d\t", order[i]);
}
getchar();
return 0;
}
八皇後問題-回溯法
基本思路：
1.建立一個全局變量二維數組chess并初始化為0；
2.逐行放皇後，若存在互相攻擊現象則向後移動一列，若不存在互相攻擊現象，則進行下一行皇後的放置
// ConsoleApplication3.cpp : 定義控制台應用程式的入口點。
//
#include "stdafx.h"
#include<stdio.h>
#include<windows.h>
#define N 4 //可以根據N來修改棋盤的格數
int count = 0;//設定一個計數器
int chess[N][N] = { 0 };//用于存放棋盤的二維數組
void print()//列印函數
{
int i = 0;
int j = 0;
printf("*****************************************\n");
for (i = 0; i<N; i++)
{
for (j = 0; j<N; j++)
{
printf("%d ", chess[i][j]);
}
printf("\n");
}
printf("*****************************************\n");
}
//判斷是否會互吃
//關鍵條件
//傳回1 表示存在互吃
//傳回0 表示正常
int check(int i, int j)//i = 7,j = 4
{
if (i == 0)
return 0;//表示正常
int k = 0;
for (k = 0; k<i; k++)
{
if (chess[k][j] == 1)//(0,4)(1,4)...
return 1;
}
for (int s = 0, k = j + 1; k<N; k++)
{
//(7,4)(6,5),(5,6),(4,7)
if (chess[i - s - 1][k] == 1)//(0,11),(1,10),(2,9),(3,8),(4,7)
return 1;
s++;
}
for (k = 0; k<j; k++)
{
if (chess[i - k - 1][j - k - 1] == 1)//(6,3)(5,2)(4,1)(3,0)
return 1;
}
for (k = 0; k<N; k++)
{
if (chess[k][j] == 1)
return 1;
}
return 0;
}
//判斷棋盤上是否有一行存在沒有皇後的情況
//傳回0 ，表示棋盤正常（每一行都有皇後）
//傳回1 ，表示棋盤有錯
int check_all()
{
int i = 0;
int j = 0;
int flag = 0;
for (i = 0; i<N; i++)
{
flag = 0;
for (j = 0; j<N; j++)
{
if (chess[i][j] == 1)
{
flag = 1;
break;
}
}
if (flag == 0)
return 1;//有錯
}
return 0;
}
//檢查某一行是否存在皇後
//傳回0 表示存在
//傳回1 表示沒皇後
int check_line(int line)
{
if (line == 0)
return 0;
int k = 0;
int s = 0;
int flag = 1;
for (s = 0; s<line - 1; s++)
{
flag = 1;
for (k = 0; k<N; k++)
{
if (chess[s][k] == 1)
flag = 0;
}
if (flag == 1)
return 1;
}
return 0;
}
//遞歸的主要算法
void queen(int i, int j)
{
//符合，置一，進入下一行
if (check_line(i) == 1)//若該行有皇後，傳回
return;
if ((i == (N - 1)))//若此時是最後一行
{
if (check(i, j) == 0)//當最後一行的皇後可以放下（表示可以成功放置）
{
chess[i][j] = 1;//将該位置1，表示皇後
print();//列印
count++;//計數器+1
}
}
if (check(i, j) == 0)//當可以放皇後時
{
chess[i][j] = 1;//放入
//print();
//Sleep(1000);
queen(i + 1, 0);//進行下一行的皇後放置
}
if (j == N)//如果j等于列數，表明越界，傳回
return;
chess[i][j] = 0;//将該位置0
//print();
//Sleep(500);
//不符合，置零，右諾
queen(i, j + 1);//将該行皇後右移一位
}
int main(void)
{
queen(0, 0);
printf("\ncount = %d\n", count);
getchar();
return 0;
}
![goalng nil interface淺析持續學習[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)