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 个位置中有些并不会改变。比如，当操作不涉及中转的时候，有 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 v1.2.zip - 蓝奏云
记得给我点赞！收藏！以及在评论区留下你的足迹呀！
精彩文章
您阅读本篇文章共花了：
发表评论