#include "stdafx.h"
/*
算法系列---回溯算法
引言
尋找問題的解的一種可靠的方法是首先列出所有候選解，然后依次檢查每一個(gè)，在檢查完所有或部分候選解后，即可找到所需要的解。理論上，當(dāng)候選解數(shù)量有限并且通過檢查所有或部分候選解能夠得到所需解時(shí)，上述方法是可行的。不過，在實(shí)際應(yīng)用中，很少使用這種方法，因?yàn)楹蜻x解的數(shù)量通常都非常大(比如指數(shù)級(jí)，甚至是大數(shù)階乘），即便采用最快的計(jì)算機(jī)也只能解決規(guī)模很小的問題。對(duì)候選解進(jìn)行系統(tǒng)檢查的方法有多種，其中回溯和分枝定界法是比較常用的兩種方法。按照這兩種方法對(duì)候選解進(jìn)行系統(tǒng)檢查通常會(huì)使問題的求解時(shí)間大大減少(無論對(duì)于最壞情形還是對(duì)于一般情形）。事實(shí)上，這些方法可以使我們避免對(duì)很大的候選解集合進(jìn)行檢查，同時(shí)能夠保證算法運(yùn)行結(jié)束時(shí)可以找到所需要的解。因此，這些方法通常能夠用來求解規(guī)模很大的問題。
算法思想
回溯(backtracking）是一種系統(tǒng)地搜索問題解答的方法。為了實(shí)現(xiàn)回溯，首先需要為問題定義一個(gè)解空間(solution space），這個(gè)空間必須至少包含問題的一個(gè)解(可能是最優(yōu)的）。
下一步是組織解空間以便它能被容易地搜索。典型的組織方法是圖(迷宮問題)或樹(N皇后問題)。
一旦定義了解空間的組織方法，這個(gè)空間即可按深度優(yōu)先的方法從開始節(jié)點(diǎn)進(jìn)行搜索。
回溯方法的步驟如下：
1) 定義一個(gè)解空間，它包含問題的解。
2) 用適于搜索的方式組織該空間。
3) 用深度優(yōu)先法搜索該空間，利用限界函數(shù)避免移動(dòng)到不可能產(chǎn)生解的子空間。
回溯算法的一個(gè)有趣的特性是在搜索執(zhí)行的同時(shí)產(chǎn)生解空間。在搜索期間的任何時(shí)刻，僅保留從開始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的路徑。因此，回溯算法的空間需求為O(從開始節(jié)點(diǎn)起最長(zhǎng)路徑的長(zhǎng)度）。這個(gè)特性非常重要，因?yàn)榻饪臻g的大小通常是最長(zhǎng)路徑長(zhǎng)度的指數(shù)或階乘。所以如果要存儲(chǔ)全部解空間的話，再多的空間也不夠用。
算法應(yīng)用
回溯算法的求解過程實(shí)質(zhì)上是一個(gè)先序遍歷一棵"狀態(tài)樹"的過程,只是這棵樹不是遍歷前預(yù)先建立的,而是隱含在遍歷過程中<<數(shù)據(jù)結(jié)構(gòu)>>(嚴(yán)蔚敏).
回溯算法的基本思想是：從一條路往前走，能進(jìn)則進(jìn)，不能進(jìn)則退回來，換一條路再試。
回溯法是一個(gè)既帶有系統(tǒng)性又帶有跳躍性的搜索算法。它在包含問題的所有解的解空間樹中，按照深度優(yōu)先的策略，從根結(jié)點(diǎn)出發(fā)搜索解的空間樹。算法搜索至解的空間樹的任一結(jié)點(diǎn)時(shí)，總是先判斷該結(jié)點(diǎn)是否肯定不包含問題的解。如果肯定不包含，則跳過對(duì)以該結(jié)點(diǎn)為根的子樹的系統(tǒng)搜索，逐層向其祖先結(jié)點(diǎn)回溯。否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先的策略進(jìn)行搜索。回溯法在用來求問題的所有解時(shí)，要回溯到根，且根結(jié)點(diǎn)的所有子樹都已被搜索遍才結(jié)束。而回溯法在用來求問題的任一解時(shí)，只要搜索到問題的一個(gè)解就可以結(jié)束。這種以深度優(yōu)先的方式系統(tǒng)地搜索問題的解的算法稱為回溯法，它適用于解一些組合數(shù)較大的問題。
算法框架：
1、問題的解空間：應(yīng)用回溯法解問題時(shí)，首先應(yīng)明確定義問題的解空間。問題的解空間應(yīng)至少包含一個(gè)(最優(yōu)）解。
2、回溯法的基本思想：確定了解空間的組織結(jié)構(gòu)后，回溯法就從開始結(jié)點(diǎn)(根結(jié)點(diǎn)）出發(fā)，以深度優(yōu)先的方式搜索整個(gè)解空間，這個(gè)開始結(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)。換句話說，這個(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)。回溯法即以這種工作方式遞歸地在解空間中搜索，直至找到所要求的解或解空間中已沒有活結(jié)點(diǎn)時(shí)為止。
運(yùn)用回溯法解題通常包含以下三個(gè)步驟：
(1）針對(duì)所給問題，定義問題的解空間；
(2）確定易于搜索的解空間結(jié)構(gòu)；
(3）以深度優(yōu)先的方式搜索解空間，并且在搜索過程中用剪枝函數(shù)避免無效搜索。
3、遞歸回溯：由于回溯法是對(duì)解的空間的深度優(yōu)先搜索，因此在一般情況下可用遞歸函數(shù)來實(shí)現(xiàn)回溯法如下：
void backtrace(int i)
{
for (int j=下界;j<上界;j++)
{
matrix[i] = j;
//可行{滿足限界函數(shù)和約束條件}
if ( 可行())
{
//置值
if (i>n)
{
//中止搜索并輸出結(jié)果;
}
backtrace(i+1);
}
}
}
說明：
i是遞歸深度；
n是深度控制，即解空間樹的高度；
可行性判斷有兩方面的內(nèi)容：
①不滿約束條件則剪去相應(yīng)子樹；
②若限界函數(shù)越界，也剪去相應(yīng)子樹；
③兩者均滿足則進(jìn)入下一層；
搜索：全面訪問所有可能的情況，分為兩種：不考慮給定問題的特有性質(zhì)，按事先設(shè)好的順序，依次運(yùn)用規(guī)則，即盲目搜索的方法；另一種則考慮問題給定的特有性質(zhì)，選用合適的規(guī)則，提高搜索的效率，即啟發(fā)式的搜索。
*/
//八皇后問題
//解空間
static int matirx[8] = {0};
static int count = 0;
void display()
{
int row;
int col;
printf("\r\n======%02d=======\n",count);
for(row = 0; row <8; row ++)
{
for(col = 0; col < matirx[row]; col ++)
printf("* ");
printf("# ");
for(col = matirx[row] + 1; col < 8; col ++)
printf("* ");
printf("\n");
}
}
bool place(int row, int col)
{
int prev;
int data;
for(prev = 0; prev < row; prev ++){
data = matirx[prev];
//同一列
if(col == data)
return false;
//左斜線
if ((prev-row) == (col - data) )
return false;
//右斜線
if((row - prev) == (col - data))
return false;
}
return true;
}
void queen(int row)
{
int col;
for(col=0;col<8;col++)
{
if(place(row,col))
{
matirx[row]=col;
if(row>=7)
{
count++,display();
//matirx[row]=0;
return;
}
queen(row+1);
//matirx[row]=0;
}
}
}
int main(void)
{
queen(0);
system("pause");
return 0;
}