回朔算法

回朔是設計遞歸算法的重要方法，通常採用深度優先搜尋（DFS）。

基本介紹

• 中文名：回朔算法
• 外文名：Backtracking algorithm
• 性質：算法
• 學科：程式設計，計算機。

涵義

在程式設計中,有這樣一類問題:求一類解,或求全部解,或求最優解的問題(例如八皇后問題),不是根據某種確定的算法設計法則,而是利用試探和回朔的搜尋技術求解.

其求解過程實質:是一個先序遍歷一棵"狀態樹"但是這棵樹不是在遍歷前預先建立的,而是隱含在遍歷過程中.

為了套用回朔，所求的解必須能表示成一個n元組（x1，x2，…，xn），其中xi是取自某個有窮集si．下面給出n皇后的程式代碼，給出代碼前先描述問題：在一個n×n的棋盤上放置n個皇后，且使得每兩個皇后之間不能相互"攻擊"也就是使得每兩個不在同一行，同一列及同一斜角線．（經典問題八皇后問題）

引申

#include<iostream.h>

#include<math.h>

int sum=0;//用於統計解的個數

int n;//表示皇后的個數

int *x;//解向量

bool place(int k)//判斷是否能放置

{ //cout<<"begin place";

for(int j=1;j<k;j++)//若j==k則同行

if(abs(k-j)==abs(x[j]-x[k])||x[j]==x[k])//abs(k-j)==abs(x[j]-x[k])表示在斜對角線

//x[j]==x[k]表示在同一列

return false;

return true;

}

void backtract_queen(int t)

{

if(t>n)

{//一次求解完成，計數器加一，並將該組解輸出

sum++;

for(int i=1;i<=n;i++)

cout<<x<<" ";

cout<<endl;

}

else

for(int i=1;i<=n;i++)

{

x[t]=i;

if(place(t)) backtract(t+1);//遞歸調用

}

}

void main()

{

cout<<"input the number of queen:";

cin>>n;

x=new int[n];

backtract_queen(1);

cout<<"sum="<<sum<<endl;

cout<<"edn\n";

}