网站关键词做标签,mysql的网站开发,网站建设需要备案吗,重庆网站建设网站制作2024/03/19#xff1a;程序更新说明#xff08;文末程序下载链接已更新#xff09; 版本#xff1a;v1.0 → v1.2 ① 修复#xff1a;将 CLOSED 表内容从优先级队列中分离开来#xff0c;原优先级队列作 OPEN 表#xff0c;并用链表树隐式地代替 CLOSED 表#xff0c;以… 2024/03/19程序更新说明文末程序下载链接已更新 版本v1.0 → v1.2 ① 修复将 CLOSED 表内容从优先级队列中分离开来原优先级队列作 OPEN 表并用链表树隐式地代替 CLOSED 表以此修复之前版本内存爆炸的问题尤其以 HC 爬山法严重 ② 优化实时搜索树动态绘制而非总是保持 10 行 ③ 其它优化代码修复其它的一些小问题 一、写在前面
许久没有写图形化界面的程序了最近学习了一些经典的盲目搜索算法与智能搜索算法正好拿来还原三阶魔方试试手 提前声明 我不是专业搞人工智能的理论或者实现过程有些许错误也很正常评论区指出即可 先说一下开发环境吧源码及打包程序的下载链接放在文末
1.1 开发环境
编程语言Python 3.12
图形界面库tkintertools 2.6.21.1底层为 tkinter
第三方依赖库tkintertools 2.6.21.1就这么一个
二、程序概览
2.1 代码情况
代码量1000 行左右
代码大小34KB
2.2 图片展示 主界面 界面设置 自定义打乱顺序 BFS 宽度优先搜索 DFS 深度优先搜索 USC 一致代价搜索 闵可夫斯基距离 A 算法 自定义启发函数 A* 算法 2.3 详细功能
左侧是 3D 显示区鼠标左键旋转右键平移滚轮缩放。
右侧是设定区点击“开始搜索并还原”时会弹出搜索树弹窗点击“随机打乱”左边的“/”会弹出“自定义打乱顺序”弹窗。
算法对应表
缩写BFSDFSUCSA / A*HCREV测试常用说明宽度优先深度优先代价优先A 或者 A* 算法爬山法不是算法逆序还原 启发函数对应表
缩写CBSVECLDMHTHMMKWSK/说明切比雪夫距离欧几里得距离曼哈顿距离汉明距离闵可夫斯基距离h*
自定义顺序说明
每个项目由三个部分组成编号方向旋向
方向对应表
缩写RLUDFB说明右Right左Left上Up下Down前Front后Back 旋向有两个顺时针和逆时针对应开关的两种状态
三、实现过程分析
3.1 状态表示
三阶魔方一共有 3³ 27 个方块于是使用 1×27 大小的数组来表示每个方块的位置给它们编号 0~26当编号与其数组索引一致时表示魔方为还原状态。
当然由于魔方的特性这 27 个位置中有些并不会改变。比如当操作不涉及中转的时候有 11×6 7 个方块永远不会改变位置而当操作涉及中转的时候只有中心处方块不会改变位置。为了方便表示仍然采用整个 1×27 大小的数组表示状态。
3.2 操作方式
分两种情况
当不允许三阶魔方中转的时候操作共有 6×2 12 种即在魔方 6 个面上顺时针旋转 90°或者逆时针旋转 90°。当允许三阶魔方中转的时候共有 (63)×2 18 种即在第一种情况下加上了三个坐标轴垂直的三个中间面的旋转。
当然经分析我认为采用第 1 种情况可能会得到更好结果。
对于第一种情况魔方将有 11×6 7 个位置始终固定使得在完成几乎相同功能的前提下搜索空间会小一点且还原的最终结果只有1个那就是数组元素与其索引一致。
但反观第二种情况魔方只有最中间 1 个元素始终固定在使得搜索空间变大的情况下还会导致一个程序中不方便处理的问题。因为在这个时候你会发现魔方还原的目标状态不只“数组元素与其索引一致”这么一种情况虽然这可以提高发现目标节点的概率但搜索空间也变大了程序实现起来比较麻烦效率也不见得比第 1 种好。
3.3 启发函数的设计
魔方数据在数组中体现为 1×27并不方便于直接进行代价的估计但其在空间上实际是 3×3×3 的每个方块都有其对应的坐标于是可以计算每个方块当前位置与目标位置之间的某种差异并以此作为估计值。
选用的基本启发函数有切比雪夫距离、欧几里得距离、曼哈顿距离和闵可夫斯基距离同时尝试了一下汉明距离。 不知道什么是切比雪夫距离、欧几里得距离等的朋友可以去百度一下。 设上述距离对应的启发函数分别为 、、、 和 。
其中闵可夫斯基距离拥有可调节的参数 p我这里动态地根据问题的规模大小设计其值。而汉明距离并非一个空间上的关系它是从数组的数据上直接进行考虑的即目标数组与当前数组的差异。
对于上述的启发函数并非所有都满足可纳性。由于魔方转动一次只能转动一个面也就是说方块只能在一个面上移动对于方块分两种情况
角方块每次旋转都是沿坐标方向的对应曼哈顿距离边方块每次旋转都是沿斜直线方向对应欧几里得距离面中心方块始终没有任何移动计算时不考虑它。
每个面上角方块与边方块各占一半故 但是有 因此有 已知对于闵可夫斯基距离参数 p1 时参数 p2 时参数 p∞ 时可通过调控其参数 p 来控制其最终效果。
汉明距离并非空间上的距离属于抽象距离无法与上面的进行比较。
综上启发函数为切比雪夫距离、欧几里得距离时算法为 A* 算法曼哈顿距离对应的为 A 算法闵可夫斯基距离是否为 A* 算法与参数 p 有关汉明距离对应的暂时无法确定。
3.4 算法实现
BFS用队列实现
DFS用堆栈实现
UCS用优先级队列实现评估函数 F 代价函数 G
A/A*用优先级队列实现评估函数 F 代价函数 G 启发函数 H
HC用优先级队列实现评估函数 F 启发函数 H
3.5 结果显示方法
结果采用三种方式进行可视化。
搜索之前的打乱魔方与搜索之后的还原魔方通过 3D 魔方实时演示旋转过程搜索过程之中通过进度条得知总搜索空间的大小以及当前搜索的空间大小直观显示其百分占比并实时显示搜索次数搜索完成后显示还原步骤的数量搜索过程中实时展示搜索树由于此数的每层节点数量是指数级增长的于是就需要将其对数化后以线性的方式的进行展示层数越大颜色越深搜索完毕后标识出搜索路径。
这里说一下为什么实际搜索的状态空间是 11 的 n 次方而不是 12 的 n 次方因为每次操作虽然有 12 步但实际我们手动不允许它执行与上次转动相反的操作因为你顺时针转一下再逆时针转一下那不等于没转吗
别小看这点优化11⁶ 177156112⁶ 2985984仅 6 步相差多少自己看看。
四、写在后面
4.1 开源图形库
本程序使用的 tkintertools 是我自己一个人开发的图形界面库基于 tkinter实现了一些 tkinter 没有的功能里面还有一个可以称为“微型 3D 引擎”的子模块上述 3D 效果就是这样实现的此外还提供了较为强大的动画能力希望大家能支持一下下 GitHub repoGitHub - Xiaokang2022/tkintertools github.io: Profile - 简介 - tkintertools (xiaokang2022.github.io) 4.2 源代码下载
链接文件包含了源代码以及已经打包好可以直接运行的 exe 文件。
源代码及打包程序下载链接Magic Cube v1.2.zip - 蓝奏云
记得给我点赞收藏以及在评论区留下你的足迹呀
