一、回溯法：
回溯法是一種選優(yōu)搜索法，按選優(yōu)條件向前搜索，以達到目標。但當探索到某一步時，發(fā)現(xiàn)原先選擇并不優(yōu)或達不到目標，就退回一步重新選擇，這種走不通就退回再走的技術為回溯法，而滿足回溯條件的某個狀態(tài)的點稱為“回溯點”。
二、什么樣的問題用回溯法?
這個問題與集合有關.也就是該問題的解是一個集合.滿足一個條件D的集合.來看下面百度百科的定義:
"可用回溯法求解的問題P，通常要能表達為：對于已知的由n元組（x1，x2，…，xn）組成的一個狀態(tài)空間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的一個解。"
三、算法框架：
1、問題的解空間：應用回溯法解問題時，首先應明確定義問題的解空間。問題的解空間應到少包含問題的一個（最優(yōu)）解。
2、回溯法的基本思想：確定了解空間的組織結構后，回溯法就從開始結點（根結點）出發(fā)，以深度優(yōu)先的方式搜索整個解空間。這個開始結點就成為一個活結點，同時也成為當前的擴展結點。在當前的擴展結點處，搜索向縱深方向移至一個新結點。這個新結點就成為一個新的活結點，并成為當前擴展結點。如果在當前的擴展結點處不能再向縱深方向移動，則當前擴展結點就成為死結點。換句話說，這個結點不再是一個活結點。此時，應往回移動（回溯）至最近的一個活結點處，并使這個活結點成為當前的擴展結點。回溯法即以這種工作方式遞歸地在解空間中搜索，直至找到所要求的解或解空間中已沒有活結點時為止。
運用回溯法解題通常包含以下三個步驟：
（1）針對所給問題，定義問題的解空間；
（2）確定易于搜索的解空間結構；
（3）以深度優(yōu)先的方式搜索解空間，并且在搜索過程中用剪枝函數(shù)避免無效搜索；
四. 設計回溯算法.
設計如下幾點:
1. 設定數(shù)據(jù)結構.
2. 將約束條件整合了約束函數(shù),用于檢驗當前解狀態(tài)是否合法(Islegal).
3. 一組解的出口:若找到一組解了,則打印輸出或記錄解的個數(shù).
4. 循環(huán),窮舉當前結點值,深度搜索其子樹是否有解,此處相當于遞歸.
5. 回溯函數(shù)的參數(shù): 結點共有且變化的數(shù)據(jù).
例:
1.(Target Practice )求解,10次射擊,打中90環(huán)的可能性有多少?分析:有限集合,條件是10擊中90環(huán)的一組集合,即為解.
約束條件:1)10環(huán)打完,不足90環(huán) 2)10環(huán)未打完,剩下的已不能滿足90環(huán)的要求.
if(nScore < 0 || nScore > nTimes * 10)出口: 10次打完或90分已拿到
if(nTimes == 0 || nScore == 0 )
當前結點可能的值:
for(int i = 0; i <= 10; i++)
{
TargetPractice(nTimes - 1, nScore - i);
}
參數(shù)設計:當前局, 當前分數(shù)
void TargetPractice(int nTimes, int nScore )
完整解:
void TargetPractice(int score, int num)
{
if (score < 0 || score > num * 10) return ;
if (num == 0 || score == 0) {
store[num-1] = score;
Output();
++sum;
return ;
}
for (int i = 0; i <= 10; i++)//one scene have just 11 status
{
store[num - 1] = i;
TargetPractice(score - i, num - 1);
}
}
int main()
{
TargetPractice(90, 10);
return 0;
}
2.八皇后問題.
完整解:
//數(shù)據(jù)結構:
static char Queen[8][8];//棋盤矩陣
static int a[8]; //標記:列沖突
static int b[15]; //標記:主對角線沖突
static int c[15]; //標記:從對角線沖突
static int iQueeNum = 0;//統(tǒng)計解的個數(shù)
void qu(int i);//i代表行,棋子所在行
int main()
{
int iLine, iColumn;
for (iLine = 0; iLine < 8; iLine++)
{
a[iLine] = 0;//列標記初始化
for (iColumn = 0; iColumn < 8; iColumn++)
{
Queen[iLine][iColumn] = '*';
}
}
//主,從對角線標記初始化,表示沒有沖突
for (iLine = 0; iLine < 15; iLine++)
{
b[iLine] = c[iLine] = 0;
}
qu(0);
return 0;
}
void qu(int i) //參數(shù):行
{
int iColumn;
for (iColumn = 0; iColumn < 8; iColumn++)//該行共有八種情況
{
if (a[iColumn] == 0 && b[i - iColumn + 7] == 0 && c[i + iColumn] == 0 )
{
Queen[i][iColumn] = '@'; //放皇后
a[iColumn] = 1; //標記,該列已不能放皇后
b[i - iColumn + 7] = 1; //標記,該主對角線不能放皇后
c[i + iColumn] = 1; //標記,該從對角線不能放皇后
if (i < 7)
{
qu(i + 1);//求解下一行
}
else //否則輸出
{
//輸出棋盤狀態(tài)
int iLine, iColumn;
printf("第%d種狀態(tài)為 \n", ++iQueeNum);
for (iLine = 0; iLine < 8; iLine++)
{
for (iColumn = 0; iColumn < 8; iColumn++)
{
printf("%c", Queen[iLine][iColumn]);
}
printf("\n");
}
printf("\n\n");
}
//本次回溯完, 重置標記
Queen[i][iColumn] = '*';
a[iColumn] = 0;
b[i - iColumn + 7] = 0;
c[i + iColumn] = 0;
}
}
}
拿來主義:
本文中引用其它參考文包括
http://blog.csdn.net/adcxf/archive/2008/03/20/2201039.aspx