logo资料库

极好的8皇后问题的算法解析.ppt

发布时间：2022-06-13 发布人：admin 分类：说明书 资料大小：1.31M 资料格式：ppt 举报 版权申诉
第1页 / 共78页
第2页 / 共78页
第3页 / 共78页
第4页 / 共78页
第5页 / 共78页
第6页 / 共78页
第7页 / 共78页
第8页 / 共78页
资料共78页，剩余部分请下载后查看
    第九章　 递归思想与相应算法 1
    9.2　递 归 算 法 举 例 　——八皇后问题 2
    1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 观看8皇后GUI演示 3
    在8×8的棋盘上，放置8个皇后（棋子），使两两之间 互不攻击。所谓互不攻击是说任何两个皇后都要满足： （1）不在棋盘的同一行； （2）不在棋盘的同一列； （3）不在棋盘的同一对角线上。 因为棋盘一共有8行，每行能有且只能有一个皇后，所 以，至多能放8个皇后。这8个皇后"每个应该放在哪一列上" 是解该题的任务。我们还是用试探的方法“向前走，碰壁回 头”的策略。这就是“回溯法”的解题思路。 4
    定义函数 Try(i)：将第i个皇后放到棋盘上。 由于棋盘的对称性，我们假定是逐行放置皇后。下面讨论将 第i行的皇后放在j列位置上之后（如果该位置是安全的话）， 棋盘各位置安全性的变化（对未来放置皇后过程有影响）。 在放第i行的皇后时，第i行上应还没有皇后，不会在行上 遭到其它皇后的攻击。只考虑来自列和对角线的攻击。 用数组q来记录各行皇后的位置（列号），q[i]=j表示第i 行皇后放到第j列。显然，放过第i个皇后之后，第j列就不 安全了。若用数组C表示各列的安全性，则C[j]=false。 同时，通过(i,j)的对角线也不安全了。经过分析可以看出: (1) 对于从左上到右下的对角线，每个位置都有 i–j = 常数 的特点； (2) 对于从左下到右上的对角线，每个位置都有 i + j = 常数 的特点。 5
    如何降低难度？ 先讨论四皇后问题 目的是 降低规模，降低难度 寻找解题规律 之后再回到原题的解法 注意： 因为是从第一行开始一行一行按顺序 放皇后，所以可以不用判行是否安全，只 判列和对角线是否安全 6
    判列是否安全问题 可以使用数组，元素数目５ 定义 bool C [5] ; true 第 j 列未放皇后 C [ j ]= false 第 j 列已放皇后 j=1,2,3,4 下面的难点是判对角线是否安全问题 7
    第2行皇后放到第3列，导致第3行无法无法放置皇后 8
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料