一、写在前面
许久没有写图形化界面的程序了,最近学习了一些经典的盲目搜索算法与智能搜索算法,正好拿来还原三阶魔方!试试手!
提前声明
我不是专业搞人工智能的,理论或者实现过程有些许错误也很正常,评论区指出即可
先说一下开发环境吧!源码及打包程序的下载链接放在文末!
1.1 开发环境
编程语言:Python 3.12
图形界面库:tkintertools 2.6.21.1(底层为 tkinter)
第三方依赖库:tkintertools 2.6.21.1(就这么一个)
二、程序概览
2.1 代码情况
代码量:1000 行左右
代码大小:34KB
2.2 图片展示
![多种智能搜索算法可视化还原 3D 魔方,开发秘籍:tkinter 桌面应用程序,Python,AI,魔方,智能搜索算法,搜索可视化,tkintertools,tkinter](https://imgs.yssmx.com/Uploads/2024/03/841253-1.png)
![多种智能搜索算法可视化还原 3D 魔方,开发秘籍:tkinter 桌面应用程序,Python,AI,魔方,智能搜索算法,搜索可视化,tkintertools,tkinter](https://imgs.yssmx.com/Uploads/2024/03/841253-2.png)
![多种智能搜索算法可视化还原 3D 魔方,开发秘籍:tkinter 桌面应用程序,Python,AI,魔方,智能搜索算法,搜索可视化,tkintertools,tkinter](https://imgs.yssmx.com/Uploads/2024/03/841253-3.png)
![多种智能搜索算法可视化还原 3D 魔方,开发秘籍:tkinter 桌面应用程序,Python,AI,魔方,智能搜索算法,搜索可视化,tkintertools,tkinter](https://imgs.yssmx.com/Uploads/2024/03/841253-4.png)
![多种智能搜索算法可视化还原 3D 魔方,开发秘籍:tkinter 桌面应用程序,Python,AI,魔方,智能搜索算法,搜索可视化,tkintertools,tkinter](https://imgs.yssmx.com/Uploads/2024/03/841253-5.png)
![多种智能搜索算法可视化还原 3D 魔方,开发秘籍:tkinter 桌面应用程序,Python,AI,魔方,智能搜索算法,搜索可视化,tkintertools,tkinter](https://imgs.yssmx.com/Uploads/2024/03/841253-6.png)
![多种智能搜索算法可视化还原 3D 魔方,开发秘籍:tkinter 桌面应用程序,Python,AI,魔方,智能搜索算法,搜索可视化,tkintertools,tkinter](https://imgs.yssmx.com/Uploads/2024/03/841253-7.png)
![多种智能搜索算法可视化还原 3D 魔方,开发秘籍:tkinter 桌面应用程序,Python,AI,魔方,智能搜索算法,搜索可视化,tkintertools,tkinter](https://imgs.yssmx.com/Uploads/2024/03/841253-8.png)
2.3 详细功能
左侧是 3D 显示区,鼠标左键旋转,右键平移,滚轮缩放。
右侧是设定区,点击“开始搜索并还原”时会弹出搜索树弹窗,点击“随机打乱”左边的“/”会弹出“自定义打乱顺序”弹窗。
算法对应表:
缩写 | BFS | DFS | UCS | A / A* | HC | REV(测试常用) |
说明 | 宽度优先 | 深度优先 | 代价优先 | A 或者 A* 算法 | 爬山法 | 不是算法,逆序还原 |
启发函数对应表:
缩写 | CBSV | ECLD | MHT | HM | MKWSK | / |
说明 | 切比雪夫距离 | 欧几里得距离 | 曼哈顿距离 | 汉明距离 | 闵可夫斯基距离 | h* |
自定义顺序说明:
每个项目由三个部分组成:编号,方向,旋向
方向对应表:
缩写 | R | L | U | D | F | B |
说明 | 右(Right) | 左(Left) | 上(Up) | 下(Down) | 前(Front) | 后(Back) |
旋向有两个:顺时针和逆时针,对应开关的两种状态
三、实现过程分析
3.1 状态表示
三阶魔方一共有 3³ =27 个方块,于是使用 1×27 大小的数组来表示每个方块的位置,给它们编号 0~26,当编号与其数组索引一致时,表示魔方为还原状态。
当然,由于魔方的特性,这 27 个位置中有些并不会改变。比如,当操作不涉及中转的时候,有 1+1×6 = 7 个方块永远不会改变位置,而当操作涉及中转的时候,只有中心处方块不会改变位置。为了方便表示,仍然采用整个 1×27 大小的数组表示状态。
3.2 操作方式
分两种情况:
- 当不允许三阶魔方中转的时候,操作共有 6×2 = 12 种,即在魔方 6 个面上顺时针旋转 90°或者逆时针旋转 90°。
- 当允许三阶魔方中转的时候,共有 (6+3)×2 = 18 种,即在第一种情况下加上了三个坐标轴垂直的三个中间面的旋转。
当然,经分析,我认为采用第 1 种情况可能会得到更好结果。
对于第一种情况,魔方将有 1+1×6 = 7 个位置始终固定,使得在完成几乎相同功能的前提下,搜索空间会小一点,且,还原的最终结果只有1个,那就是数组元素与其索引一致。
但反观第二种情况,魔方只有最中间 1 个元素始终固定,在使得搜索空间变大的情况下,还会导致一个程序中不方便处理的问题。因为在这个时候,你会发现,魔方还原的目标状态不只“数组元素与其索引一致”这么一种情况,虽然这可以提高发现目标节点的概率,但搜索空间也变大了,程序实现起来比较麻烦,效率也不见得比第 1 种好。
3.3 启发函数的设计
魔方数据在数组中体现为 1×27,并不方便于直接进行代价的估计,但其在空间上实际是 3×3×3 的,每个方块都有其对应的坐标,于是可以计算每个方块当前位置与目标位置之间的某种差异,并以此作为估计值。
选用的基本启发函数有切比雪夫距离、欧几里得距离、曼哈顿距离和闵可夫斯基距离,同时尝试了一下汉明距离。
不知道什么是切比雪夫距离、欧几里得距离等的朋友,可以去百度一下。
设上述距离对应的启发函数分别为 、、、 和 。
其中闵可夫斯基距离拥有可调节的参数 p,我这里动态地根据问题的规模大小设计其值。而汉明距离并非一个空间上的关系,它是从数组的数据上直接进行考虑的,即目标数组与当前数组的差异。
对于上述的启发函数,并非所有都满足可纳性。由于魔方转动一次只能转动一个面,也就是说,方块只能在一个面上移动,对于方块,分两种情况:
- 角方块:每次旋转都是沿坐标方向的,对应曼哈顿距离;
- 边方块:每次旋转都是沿斜直线方向,对应欧几里得距离;
- 面中心方块:始终没有任何移动,计算时不考虑它。
每个面上角方块与边方块各占一半,故 ,但是有:
因此有:
已知,对于闵可夫斯基距离,参数 p=1 时,,参数 p=2 时,,参数 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⁶ = 1771561,12⁶ = 2985984,仅 6 步,相差多少自己看看。
四、写在后面
4.1 开源图形库
本程序使用的 tkintertools 是我自己一个人开发的图形界面库,基于 tkinter,实现了一些 tkinter 没有的功能,里面还有一个可以称为“微型 3D 引擎”的子模块,上述 3D 效果就是这样实现的,此外还提供了较为强大的动画能力,希望大家能支持一下下!
GitHub repo:GitHub - Xiaokang2022/tkintertools
github.io: Profile - 简介 - tkintertools (xiaokang2022.github.io)
4.2 源代码下载
链接文件包含了源代码,以及已经打包好,可以直接运行的 exe 文件。
源代码及打包程序下载链接:Magic Cube.zip - 蓝奏云文章来源:https://www.toymoban.com/news/detail-841253.html
记得给我点赞!收藏!以及在评论区留下你的足迹呀!文章来源地址https://www.toymoban.com/news/detail-841253.html
到了这里,关于多种智能搜索算法可视化还原 3D 魔方的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!