实验四 n皇后问题求解

实验四 n皇后问题求解

ID:14555980

大小:49.00 KB

页数:4页

时间:2018-07-29

实验四 n皇后问题求解_第1页
实验四 n皇后问题求解_第2页
实验四 n皇后问题求解_第3页
实验四 n皇后问题求解_第4页
资源描述:

《实验四 n皇后问题求解》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、实验四N皇后问题求解一、题目1)以Q-皇后问题为例,掌握回溯法的基本设计策略。2)掌握回溯法解决Q-皇后问题的算法并实现;二、算法设计思想回溯法是在包含问题的所有解的解空间树中,按照深度优先搜索的策略,从根结点出发深度探索解空间树。当探索到某一结点时,要先判断该结点是否包含问题的解,如果包含,就从该结点出发继续探索下去,如果该结点不包含问题的解,则逐层向其祖先结点回溯。(其实回溯法就是对隐式图的深度优先搜索算法)。若用回溯法求问题的所有解时,要回溯到根,且根结点的所有可行的子树都要已被搜索遍才结束。而若使用回溯法求任一个解时,只要搜索到问题的一个解就可以

2、结束。判断解是否可行的条件:1.不在同一行或者同一列,x[i]!=x[j],i!=j2.不在一条斜线上,设两个皇后在(i,j)和(k,l)位置,

3、i-k

4、!=

5、j-l

6、三、程序#include#includeintn,stack[100];//存当前路径inttotal;//路径数intatt(int,int);voidmake(intl)//递归搜索以stack[l]为初结点的所有路径{inti,j;//子结点个数if(l==n+1){total=total+1;//路径数+1for(i=1;i<=n;i++)pr

7、intf("输出皇后的列位置%-3d",stack[i]);//输出第i行皇后的列位置stack[i]printf("");exit;//回溯}for(i=1;i<=n;i++){stack[l]=i;//算符i作用于生成stack[l-1]产生子状态stack[l];if(!att(l,i))make(l+1);}//再无算符可用,回溯}intatt(intl,inti){intk;for(k=1;k

8、

9、i==stack[k])return1;return0;}intmain()

10、{printf("N=");scanf("%d",&n);total=0;//路径数初始化为0make(1);//从结点1出发,递归搜索所有的路径printf("%d",total);system("pause");return0;}四、运行结果六、心得体会在解决N皇后的时候一开始有点不止如何着手,因为这里有个N的不确定性,所以选择简单少量的情况进行具体考虑显得相对容易了许多,还有一个值得注意的问题就是如何判断要不要重新开始搜索,并且在已经形成的简单模型基础上进行改进,使之也能满足后面较复杂情况。

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。