算法设计与分析课件 41 n皇后_第1页
算法设计与分析课件 41 n皇后_第2页
算法设计与分析课件 41 n皇后_第3页
算法设计与分析课件 41 n皇后_第4页
算法设计与分析课件 41 n皇后_第5页
已阅读5页，还剩12页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

算法设计与分析本节要点CONTENTSn皇后n皇后在n×n的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之在同一行、同一列、同一斜线上的棋子。设计算法在n×n的棋盘上放置n个皇后，使其彼此不受攻击。n皇后在第i行第j列放置一个皇后，那么第i行的其他位置（同行），那么第j列的其他位置（同列），同一斜线上的其他位置，都不能放置皇后。n皇后（1）定义问题的解空间n皇后问题解的形式为n元组：{x1，x2，…，xi，…，xn}，分量xi表示第i个皇后放置在第i行第xi列，xi的取值为1，2，…，n。例如x2=5，表示第2个皇后放置在第2行第5列。显约束为不同行。n皇后（2）解空间的组织结构n皇后问题的解空间是一棵m（m=n）叉树，树的深度为n。n皇后（3）搜索解空间· 约束条件在第t行放置第t个皇后时，第t个皇后的位置不能和前t−1个皇后同列、同斜线。第i个皇后和第j个皇后不同列，即xi!=xj，并且不同斜线|i−j|!=|xi−xj|。· 限界条件该问题不存在放置方案好坏的情况，所以不需要设置限界条件。n皇后在4×4的棋盘上放置4个皇后，使其彼此不受攻击。n皇后算法实现n皇后n皇后算法分析时间复杂度：

时间复杂度为O(nn+1)。空间复杂度：空间复杂度为O(n)。n皇后n皇后算法优化拓展：以上求解方法的解空间为m叉树，m=n，解空间过于庞大，所以时间复杂度很高，算法效率当然会降低。解空间越小，算法效率越高。如果能够缩小解空间，则可以提高效率。n皇后n皇后问题采用不同行作为显约束，隐约束为不同列、不同斜线，解空间为m叉树。4皇后问题，显约束为不同行的解空间树如图。n皇后显约束可以控制解空间大小，隐约束用于判定可行解或最优解。如果把显约束定为不同行、不同列，隐约束为不同斜线。4皇后问题，显约束为不同行、不同列的解空间树如图。解空间变小了好多！n皇后除最后一层外，有1+n+n(n−1)+…+n(n−1)(n−2)…2≤nn!个节点。在每个分支都需要判断约束函数，判断约束条件需要O(n)时间，总耗时O(n2n!)。n皇后算法实现算法分析时间复杂度：

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论