请输入您要查询的百科知识:

 

词条 回朔算法
释义

在程序设计中,有这样一类问题:求一类解,或求全部解,或求最优解的问题(例如八皇后问题),不是根据某种确定的算法设计法则,而是利用试探和回朔的搜索技术求解.

回朔还是设计递归算法的重要方法,其求解过程实质:是一个先序遍历一棵"状态树"但是这棵树不是在遍历前预先建立的,而是隐含在遍历过程中.

为了应用回朔,所求的解必须能表示成一个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\";

}

随便看

 

百科全书收录4421916条中文百科知识,基本涵盖了大多数领域的百科知识,是一部内容开放、自由的电子版百科全书。

 

Copyright © 2004-2023 Cnenc.net All Rights Reserved
更新时间:2025/3/26 6:30:11