admin管理员组文章数量:1566354
2024年5月1日发(作者:)
实验题目
回溯法实现8皇后问题
实验要求
a.掌握递归回溯算法的基本思想。
b.学习掌握应用面向对象通用回溯程序框架解决实际问题。 提
高面向对象编程的技能。
实验内容(问题描述、算法设计、算法效率)
回溯法实现8皇后问题
a.问题描述:在n*n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的
规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。N后问题等
价于在n*n格的棋盘上放置n个皇后,任何2个皇后不放在同一行或同一列或同
一斜线上。
b.算法设计:
用n元组x[1;n]表示n后问题的解。其中,x[i]表示皇后i放置在棋盘的第
i行的第x[i]列。由于不容许将2个皇后放在同一列上,所以解向量中的x[i]互不
相同。2个皇后不能放在同一斜线上是问题的隐约束。对于一般的n后问题,这
一隐约束条件可以化成显约束的形式。如果将n*n 格的棋盘看做二维方阵,其
行号从上到下,列号从左到右依次编号为1,2,...n。从棋盘左上角到右下角的主
对角线及其平行线(即斜率为-1的各斜线)上,2个下标值的差(行号-列号)
值相等。同理,斜率为+1的每条斜线上,2个下标值的和(行号+列号)值相等。
因此,若2个皇后放置的位置分别是(i,j)和(k,l),且 i-j = k -l 或 i+j = k+l,
则说明这2个皇后处于同一斜线上。以上2个方程分别等价于i-k = j-l 和 i-k =l-j。
由此可知,只要|i-k|=|l-j|成立,就表明2个皇后位于同一条斜线上。
用回溯法解n后问题,用完全n叉树表示解空间。可行性约束Place剪去不
满足行,列和斜线约束的子树。
下面的解n后问题的回溯法中,递归函数Backtrack(1)实现对整个解空间的
回溯搜索。Backtrack(i)搜索解空间中第i层子树。类Queen的数据成员记录解
空间中节点信息,以减少传给Backtrack的参数。sum记录当前已找到的可行方
案数。
在算法Backtrack中,当i>n是,算法搜索至叶节点,得到一个新的n皇后
互不攻击放置方案,当前已找到的可行方案数sum增1。
当i<=n时,当前扩展节点Z是解空间中的内部节点。该节点有x[i]=1,2,..,n
共n个儿子节点。对当前扩展节点Z的每一个儿子节点,由Place检查其可行
性,并以深度优先的方式递归对可行子树搜索,或剪去不可行子树。
c.算法效率:O(n!)
d.代码:
#include"iostream"
#include"cmath"
using namespace std;
int count=0;
int queenplace[92][8];
int board[8][8];
void putqueen(int ith)
{
int i,k,r;
if(ith==8)
{
count++;
return;
}
for(i=0;i<8;i++)
{
if(board[ith][i]==-1)
{
board[ith][i]=ith;
for(k=count;k<92;k++)
queenplace[k][ith]=i+1;//ithqueeen
//设置控制区域
for(k=0;k<8;k++)
for(r=0;r<8;r++)
if(board[k][r]==-1&&(k==ith || r==i || abs(k-ith)==abs(r-i)))
board[k][r]=ith;
putqueen(ith+1);
//回溯
for(k=0;k<8;k++)
for(r=0;r<8;r++)
if(board[k][r]==ith)
board[k][r]=-1;
}
}
}
int main()
{
int n,i,j;
for(i=0;i<8;i++)
for(j=0;j<92;j++)
queenplace[i][j]=0;
for(i=0;i<8;i++)
for(j=0;j<8;j++)
board[i][j]=-1;
putqueen(0);
cin>>n;
while(n--)
{
int in;
cin>>in;
for(j=0;j<8;j++)
cout< cout< } return 0; } 实验心得(收获、体会) 回溯法有“通用解题法”之称。用它可以系统地搜索一个问题的所有解或任一 解。回溯法在问题的解空间树中,按深度优先策略,从根节点出发搜索解空间树。 算法搜索至解空间树的任一结点时,先判断该结点是否包含问题的解。如果肯定 不包含,则跳过对以该结点为根的子树的搜索,逐层向其祖先结点回溯。否则, 进入该子树,继续按深度优先策略搜索。它适合于解组合数较大的问题
版权声明:本文标题:回溯法实现8皇后问题 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/dongtai/1714551871a410733.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论