中文版 | English Version
🎓 本科毕业论文配套实现 | 针对高维、多同质目标、通配块约束的工业调度抽象模型。通过位运算状态压缩与启发式演进，在笔记本电脑（Intel i5 9300H，32GB内存）上实现 46 步极限难度谜题的秒级求解。
本框架记录了从 面向对象初学版 到 硬件级底层优化版 的完整进化轨迹：
- ⚡ 极致压榨： 利用 64-bit Bitboard 与双掩码拼接（44-bit）彻底消除 Python 对象开销与 GC 停顿。
-
🧠 智能决策： 引入可容许（Admissible）的加法模式数据库 (PDB)，将搜索空间的评估转化为
$O(1)$ 的查表操作。 -
🛠️ 工程闭环： 提供从
V0到V3的迭代源码，直观展现从面向对象到硬件友好型算法的优化路径。 - 📊 数据驱动： 相比基线版本，节点搜索量减少 87%，内存占用降低 96%，综合耗时缩短 61 倍。
| 阶段 | 核心实现 | 优化手段 | 适用场景 |
|---|---|---|---|
| V0 (Baseline) | List[List] |
错位计数法 (Hamming) | 原型验证，逻辑跑通 |
| V1 (Memory) | Tuple + __slots__ |
内存对齐 + Tie-breaker | 降低碎片化，优化对象存储 |
| V2 (Bitwise) | 64-bit Bitboard |
双向 BFS + 静态掩码异或 | 状态空间压缩，消除指针开销 |
| V3 (Ultimate) | PDB + A* |
离线预计算 + 启发式修剪 | 极限搜索，40步以上复杂解 |
variant-slider-solver/
├── V0.py # 基线版：二维列表 + 弱启发式
├── V1.py # 工程优化：一维元组 + 状态打散优化
├── V2.py # 算力压榨：位运算核心 + 双向搜索
├── V3.py # 终极版：双掩码 PDB 引导的 A* 算法
├── run_benchmark.py # 自动化评测工具 (性能、内存、路径验证)
├── cases.py # 存放预置棋盘 (Easy/Medium/Hard)
├── README.md # 项目说明文档 (中文版：含快速启动与勘误摘要)
├── README_EN.md # 项目说明文档 (英文版)
├── ERRATA.md # 学术勘误与理论补充说明 (中文版：硬核理论推导)
├── ERRATA_EN.md # 学术勘误与理论补充说明 (英文版)
├── REFERENCES.md # 核心参考文献与理论溯源 (含 DOI 与直达链接)
└── LICENSE # MIT 开源协议| 版本 | 核心技术 | 扩展节点数 | 峰值内存 | 寻路耗时 | 综合加速比 |
|---|---|---|---|---|---|
| V0 | 二维列表 + Hamming | 3,547,878 | 2,929 MB | 163.50 s | 1.0× (基线) |
| V1 | 一维元组 + __slots__ |
3,341,754 | 1,092 MB | 64.58 s | 2.53× |
| V2 | Bitboard + 双向 BFS | 1,685,505 | 242 MB | 3.09 s | 52.91× |
| V3 | PDB + 异或 A* | 469,526 | 120 MB | 2.66 s | 61.47× |
使用 run_benchmark.py 可以方便地在不同版本和难度下测试算法。
# 性能测试 (以 V3 版本 Hard 难度为例)
python run_benchmark.py V3 --mode perf --case hard
# 内存追踪 (以 V0 版本 Easy 难度为例)
python run_benchmark.py V0 --mode mem --case easy--mode: 评测模式。可选perf(执行耗时与路径) 或mem(内存峰值追踪)。--case: 预置用例难度。easy: 26步解，适合验证 V0/V1。medium: 34步解，中等难度。hard: 46步解，用于展现 V2/V3 的极限加速能力。
本仓库为中南林业科技大学本科毕业论文配套实现。
- 论文题目： 《基于位运算状态压缩与模式数据库的变体滑块谜题求解算法研究》
- 核心贡献： 证明了针对多同质目标的 PDB 可容许性，并设计了基于 XOR 自反方程的状态转移模型，实现了在 Python 环境下的硬件级性能压榨。
为践行开放科学（Open Science）精神，方便后续开发者与研究者溯源本项目（变体滑块谜题求解引擎）的理论基础，特在此提供全套参考文献的数字化检索链接。所有文献均已通过严格的交叉验证，附带官方 DOI 或 Google Scholar 永久检索地址。
👉 点击查看完整参考文献列表 (REFERENCES.md)
秉承严谨的学术态度，作者在毕业论文定稿后，对文中的工程实现细节与底层离散数学理论进行了深度核查与极限压力测试。
为确保后续研究者的引用准确性，并完善该算法在广义工业场景下的理论边界，本项目单独整理了详细的补充说明文档。主要涵盖以下三个维度的深化：
-
工程实现说明：补充说明了真实源码中基于
PDB 多起点初始化的$O(1)$ 极速松弛匹配策略（对论文算法 4-1 伪代码的工程深化）。 - 排版与文献勘误：修正了部分参考文献的页码与出版地笔误。
-
理论边界推导 (核心)：
- 补充了广义状态空间公式成立的 拓扑连通性前提（连通分量检测）。
- 揭示了通配块松弛匹配机制对 “奇偶性隔离”进行拓扑折叠 的底层代数原理。
- 严谨推导了极限障碍物密度下，奇偶性死锁恢复的 绝对数学边界 (
$N_{\text{valid}} \le 3$ )。
(注：上述补充仅涉及理论边界的拓展与排版修正，不影响论文核心算法逻辑及 61 倍性能提升的实验结论。)
👉 详细推导与说明请参阅：《学术勘误与理论补充说明》 (ERRATA.md)
- License: MIT License
- Mentor: 感谢 刘蓉老师 对算法严谨性与论文架构的悉心指导。