计算机和电子信息工程通信工程论文ppt课件.ppt

魔方 求解问题的设计与实现 院 系 名称 专业名称 学生姓名 指导教师 课题简介 本设计是一个可以对魔方进行求解的程序 通过采用专家系统理论中的方法 它可以快速地对输入的魔方状态文件求解 程序的核心是一个专家的知识模块 这个模块是关于魔方的旋转序列的表示 程序不断地将当前的魔方状态图与这个模块中的符合要求的状态图对比 如果符合要求就调用相应的旋转序列 得到一个新的魔方的状态图 程序中用到了关于图搜索的A 算法 这是一个关于图搜索和结点扩展的通用的算法 但是这个算法并没有规定搜索树的扩展方式 搜索树的扩展方式采用广度优先搜索 这样可以找到符合要求的状态图的最佳路径 在程序中 将广度优先搜索与A 算法相结合来对状态图进行搜索和结点的扩展 在搜索的过程中用到了回朔操作 关于搜索与存储的问题 在魔方问题的解决过程当中要对魔方状态图进行搜索 但魔方的状态图很大 以致其不能通过显示图来表示 所以 只能用隐式状态空间图来解决 而解决问题的关键是如何用公式来表示隐式状态空间图搜索的方法 因为魔方问题中状态图相当大 不可盲目搜索 这时必须使用优化算法指导搜索 分三个设计阶段 首先要决定如何表示魔方的当前状态 然后还必须表示对魔方的操作 最后必须解决如何把这些操作运用到魔方上 在搜索中也会有一定的优化 由于状态图是按树型结构展开 所以 优化就是指 剪枝 操作 关于搜索的方法 采用的是A 算法 对于魔方状态图的存储 本程序中采用了一个二维数组 用二维数组存储魔方状态图时 考虑到存储空间的问题 因在本程序中只在魔方复原的第一阶段用到了搜索 而搜索的层数不多 但还是用了一个状态图来表示魔方的当前状态 可以节省些空间 关于专家系统的简介 专家 知识采集子系统 知识库事实 启发式 用户 用户接口 解释子系统 推理引擎 知识工程师 魔方求解过程中将一些复杂的旋转序列嵌到程序中去 可以节省大量的空间和时间 提高程序的效率 这种方法就是所谈到的专家系统 专家系统就是将某一个领域的知识进行合理的组织 与计算机程序的合理组合 严格地讲 任何具有专家功能的程序都被称为是一个专家系统 一个专家系统的主要包括两方面 知识库和推理引擎 在本程序中 由于是一个很简单的专家系统 所以只包含了这两个最主要的方面 这个过程经常由一个知识采集子系统协助 这个子系统检查正在增长的知识库的可能不一致和不完备信息 然后将它们表示给专家以做出决定 文件的输入 在这里对魔方文件的输入做简单的介绍一下 输入时 依次输入上面 定为红色 左面 定为绿色 前面 定为黄色 右面 定为蓝色 下面 定为橙色 和后面 定为白色 各面的颜色状态 在这里对颜色有严格的要求 当然 这种要求可能会对程序的灵活性有一定的影响 但我认为还是值得的 在这里要注意一点 输入的时候最好是把各面都转到前面来进行输入 在这里只有后面是按照从右到左 从上到下的顺序输入 其它各面当转到前面的时候都是按照从左到右 从上到下的顺序输入 魔方状态构造图 程序的总体设计 main cpp主模块 gm cpp文件接收模块 begin cpp程序执行模块 changemf cpp旋转操作模块 search cpp搜索模块 expert cpp专家系统模块 各个文件的主要功能 程序的入口 它主要是对在程序中用到的各种变量进行定义 文件中接收到的魔方各个面的颜色状态存放到魔方的状态图中 状态图变量定义为全局变量 在控制台中打印出程序的操作界面 对用户合理和不合理的输入给出相应的操作和提示 实现当对魔方各个面进行操作后 魔方状态图的变化 实现搜索功能 搜索我们想要得到的魔方状态 这主要应用在了魔方复原的第一阶段 将各种魔方复杂的旋转操作序列合理的组织在程序中 以便可以对魔方顺利求解 初始化 选择 选择 选择 选择 电脑求解 显示结果 输入文件 显示选择 对魔方状态图操作 显示状态 退出 输入错误 选择人工解决 魔方没有复原 没有选择帮助 选择帮助 魔方复原 选择下次操作 选择退出 选择退出 选择电脑求解 程序执行的总体流程图 全局变量的定义 在这里我简单的谈谈在程序执行过程中一些比较重要的全局变量 接受魔方状态文件二维数组graphmf 12 9 还有保存魔方当前状态图数组graphsta 12 9 还有一个魔方初始状态的数组graphmf1 12 9 这个数组开始由人工来解决问题后又选择了帮助 由电脑解决时可以很方便的将魔方的初始状态传给魔方实际操作的数组graphsta 在程序执行的初期 当接收到魔方状态文件的时候就将graphmf中的内容复制到graphsta和graphmf1中 还有一个对魔方正确的解决序列进行存储的重要变量 这里定义为队列rc 程序执行过程中对魔方合理正确的操作都存储在rc中 使魔方正确解决过程得到保存 各个模块间的调用关系 程序首先进入 main cpp 调用 begin cpp中的search begin 求解 gm cpp中的getgraph makegraph 函数和search cpp中change 函数 调用 choice 函数来接收用户的选择 change cpp中的相应的魔方操作函数 search cpp中的compara 函数由此来判断魔方是否已经被复原 调用自身 在用户每一次对魔方操作后 在choice 函数中选择由电脑来解决 依次调用 expert cpp中的first stage second stage third stage forth stage fifth stage sixth stage seventh stage eighth stage 八个函数 再调用 各个模块的详细设计 主模块 main cpp 就是程序的入口和一个简单的操作选择及一些变量的定义 include All Function h include include include includeusingnamespacestd 定义魔方矩阵 全局变量chargraphmf 12 9 接收文件的数组chargraphsta 12 9 实际操作的数组chargraphmf1 12 9 用来记录魔方初始状态的数组queuerc 存储魔方操作的步骤boolsolve 1 false void p 函数指针 用在魔方复原第一阶段的bfs中voidmain stringc while 1 search begin 求解开始cout c if c N c n break 文件接收模块 文件接收模块 gm cpp 这个模块主要是为了实现对魔方状态文件的接收 和它的副本的创建 主要是由以下的代码来完成这个功能 chars 6 20 char 100 cout ifstreaminstuf if instuf cerr notbeopen endl h 1 abort instuf getline s 0 20 魔方上面数据instuf getline s 1 20 魔方左面数据instuf getline s 2 20 魔方前面数据instuf getline s 3 20 魔方右面数据instuf getline s 4 20 魔方下面数据instuf getline s 5 20 魔方后面数据 魔方状态构造图 程序执行模块 search begin 这个模块被设计成界面的打印和对用户的输入执行相应的操作 它也是整个程序执行的第一部分 其它的函数调用都是在它的search begin 函数中来实现的 choice 打印出界面等待接收用户的输入 主函数 调用 自身函数 调用 在用户输入旋转字符串 并且程序执行相应的操作后 earch cpp中的compara 调用 来判断魔方是否被用户解出 如果解出则给出相应的提示 并且返回到search begin 函数的调用处 也就是主函数中去 旋转操作模块 这里所有的操作都是对数组graphsta的操作 这十二个函数分别是 front 1 前面顺时针操作 front 1 前面逆时针操作 back 1 后面顺时针操作 back 2 后面逆时针操作 up 1 上面顺时针操作 up 2 上面逆时针操作 down 1 下面顺时针操作 down 2 下面逆时针操作 left 1 左面顺时针操作 left 2 左面逆时针操作 right 1 右面顺时针操作 right 2 右面逆时针操作 在这里我们还有两个函数并没有提到过 一个是left front 实现的操作是 left front right back left的各个面间的数据进行转换 而一个实现的操作是 front down 实现front down back up front的各个面间的数据转换 这些和我给出的例子的操作是一样的 这里就不多说 这两个函数的定义主要是为了和专家系统的融合 因为在 八角法 中有这样的操作 搜索模块 1 生成表CLOSED 它的初始值为空 2 如果OPEN为空 则失败退出 3 选择OPEN上的第一个结点 从OPEN中移入CLOSED 称为n1 4 如果n1是目标结点 顺着G中 从n1到n的指针找到一条路径 获得解决方案 成功退出 5 扩展结点n1 生成其后继结点集M 在G中安置M的成员 成为n1的后继 6 M的每一个不在G中的成员建立一个指向n1的指针 把M的这些成员加到OPEN中 7 重排OPEN表 8 返回第3步 专家系统模块 这是程序中最为关键的一个模块 从而完成了对魔方的求解 我在这里选择的是 八角法 共分为八个阶段 第一阶段是在魔方的顶面构建出一个 X 可以任意指定魔方的顶面 在我的程序中我指定的这个阶段的顶面为白色 第二阶段是在魔方的底面构建出一个 X 在第一阶段后 所有含底面颜色的角块 应该都在底面 第三阶段是复原所有的角块 第四阶段是在顶面恢复三个正确的边块 第五阶段是恢复底面的所有