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