# NPUZZLE-OUC **Repository Path**: KaiFeng10086/npuzzle-ouc ## Basic Information - **Project Name**: NPUZZLE-OUC - **Description**: No description available - **Primary Language**: Unknown - **License**: Not specified - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 0 - **Forks**: 0 - **Created**: 2024-11-22 - **Last Updated**: 2024-11-22 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README # N-Puzzle 问题求解器 ## 简介 本项目是一个针对经典滑块拼图游戏——N-Puzzle（例如 8-Puzzle 和 15-Puzzle）的求解器。通过应用启发式算法（如 A* 和 IDA*），旨在高效解决 N-Puzzle 问题，并提供详细的实验分析及可视化解路径的功能。 N-Puzzle 是一种经典的人工智能问题，用于测试各种搜索算法和启发式策略。该项目实现了 A* 和 IDA* 算法，并通过不同的启发式函数（曼哈顿距离、不在位将牌数和 Disjoint Pattern）来对比这些算法的求解效果。 ## 目录 1. [项目概述](#项目概述) 2. [安装指南](#安装指南) 3. [使用说明](#使用说明) 4. [算法实现](#算法实现) 5. [启发式函数](#启发式函数) 6. [实验数据与分析](#实验数据与分析) 7. [可视化界面](#可视化界面) 8. [参考文献](#参考文献) ## 项目概述 N-Puzzle 是一种滑块拼图游戏，用户需要通过移动滑块将初始状态恢复到目标状态。目标是找到最优的解路径，使滑块移动的步数最少。 本项目中，我们实现了以下内容： - 启发式算法：包括 A* 算法和 IDA* 算法。 - 启发式函数：曼哈顿距离、不在位将牌数和 Disjoint Pattern。 - 数据结构：为节点管理设计了 Open 表和 Closed 表。 - 可视化工具：使用 Java Swing 提供图形化界面展示求解过程。 ## 安装指南 1. 克隆项目代码： ```bash git clone <仓库地址> ``` 2. 安装必要的 Java 环境： - 本项目基于 Java 语言开发，请确保已安装 Java SE Development Kit (JDK)。 3. 编译代码： ```bash javac -d bin src/*.java ``` 4. 运行程序： ```bash java -cp bin Main ``` ## 使用说明 1. 运行程序后，用户可以选择拼图的规模（例如 3x3 或 4x4）。 2. 在可视化界面中，用户可以手动输入初始状态，或随机生成一个初始状态。 3. 用户可以选择使用的求解算法（A* 或 IDA*）以及对应的启发式函数。 4. 点击 "开始求解" 按钮，程序将展示滑块拼图的求解过程，最终显示出拼图的最优解路径。 ## 算法实现 ### A* 算法 A* 是一种启发式搜索算法，结合了广度优先和深度优先搜索的特点，利用启发式函数引导搜索方向，确保找到最优解。其核心思想是利用以下代价函数： - `f(n) = g(n) + h(n)` - `g(n)`：从起点到当前节点的实际代价。 - `h(n)`：从当前节点到目标的启发式估计。 ### IDA* 算法 IDA* 是结合 A* 和迭代加深搜索的启发式算法，适用于大规模问题，通过逐步增加阈值限制来进行深度优先搜索，减少内存占用。 ## 启发式函数 1. **曼哈顿距离**： - 每个滑块到目标位置的横纵坐标差的绝对值之和。 2. **不在位将牌数**： - 计算当前状态中与目标状态不一致的滑块数量。 3. **Disjoint Pattern**： - 将 N-Puzzle 划分为多个不重叠的子问题，预先计算每个子问题的解，利用 Pattern Database 提供更精确的启发值。 ## 实验数据与分析 在不同的 N-Puzzle 实例中，我们对比了 A* 和 IDA* 算法在求解时间、生成结点数、扩展结点数等方面的表现，并分析了不同启发式函数的效果。实验结果表明： - 曼哈顿距离在简单问题中表现优异，但在大规模问题上效率相对较低。 - Disjoint Pattern 启发式函数在复杂问题中有显著的性能优势。 具体实验结果和数据分析详见[实验报告](docs/实验数据分析报告.md)。 ## 可视化界面 本项目通过 Java Swing 实现了解路径的可视化功能。用户可以通过控制面板查看拼图的每一步解路径。界面包含： - **拼图展示区**：显示滑块拼图当前状态。 - **信息面板**：动态显示求解步骤、已生成节点数、已扩展节点数等信息。 - **控制面板**：用户可以控制动画播放速度、暂停和重新开始求解。 ## 实验结果 ### astar - 结合曼哈顿距离与线性冲突 | 初始状态 | 解路径长度 | 执行时间 | 生成节点数 | 扩展节点数 | | ------------------------------------------------- | ---------- | --------- | ---------- | ---------- | | 5, 0, 8,4, 2, 1,7, 3, 6 | 21 | 0.015625 | 1405 | 527 | | 6, 4, 7,8, 5, 0,3, 2, 1 | 31 | 0.578125 | 33239 | 12579 | | 8, 6, 7,2, 5, 4,3, 0, 1 | 31 | 0.625125 | 19660 | 12244 | | 8, 13, 0, 6,1, 15, 9, 14,3, 4, 5, 11,7, 2, 10, 12 | 52 | 5.046875 | 687564 | 330012 | | 2, 9, 5, 11,8, 3, 4, 14,7, 10, 1, 12,0, 15, 6, 13 | 51 | 12.890625 | 6488327 | 3631158 | | 12, 1, 5, 6,2, 11, 7, 9,14, 10, 0, 4,15, 3, 13, 8 | 50 | 18.609375 | 10569785 | 5658127 | ### IDAstar manhattan | 初始状态 | 启发函数 | 解路径长度 | 执行时间 | 生成节点数 | 扩展节点数 | | ------------------------------------------------------ | --------- | ---------- | ----------- | ---------- | ---------- | | [5, 0, 8, 4, 2, 1, 7, 3, 6] | MANHATTAN | 21 | 0.015625s | 968 | 575 | | [6, 4, 7, 8, 5, 0, 3, 2, 1] | MANHATTAN | 31 | 0.015625s | 23297 | 14511 | | [8, 6, 7, 2, 5, 4, 3, 0, 1] | MANHATTAN | 31 | 0.0s | 19660 | 12244 | | [8, 13, 0, 6, 1, 15, 9, 14, 3, 4, 5, 11, 7, 2, 10, 12] | MANHATTAN | 52 | 0.734375s | 1972902 | 980067 | | [2, 9, 5, 11, 8, 3, 4, 14, 7, 10, 1, 12, 0, 15, 6, 13] | MANHATTAN | 51 | 1.59375s | 5240835 | 2599548 | | [4, 7, 0, 9, 12, 10, 11, 8, 14, 6, 15, 1, 2, 5, 3, 13] | MANHATTAN | 56 | 321.96875s | 874724904 | 453632919 | | [12, 10, 3, 2, 0, 7, 14, 9, 1, 15, 5, 6, 8, 4, 13, 11] | MANHATTAN | 57 | 76.625s | 156105280 | 76605082 | | [12, 1, 5, 6, 2, 11, 7, 9, 14, 10, 0, 4, 15, 3, 13, 8] | MANHATTAN | 50 | 7.1875s | 16646637 | 8258995 | | [4, 6, 15, 13, 12, 9, 10, 2, 8, 0, 7, 3, 14, 5, 1, 11] | MANHATTAN | 61 | 471.578125s | 1409371874 | 733533109 | ### IDAstar 结合曼哈顿距离与线性冲突 | 初始状态 | 启发函数 | 解路径长度 | 执行时间 | 生成节点数 | 扩展节点数 | | ------------------------------------------------------ | --------- | ---------- | ----------- | ---------- | ---------- | | [5, 0, 8, 4, 2, 1, 7, 3, 6] | MANHATTAN | 21 | 0.0s | 512 | 309 | | [6, 4, 7, 8, 5, 0, 3, 2, 1] | MANHATTAN | 31 | 0.03125s | 12597 | 7808 | | [8, 6, 7, 2, 5, 4, 3, 0, 1] | MANHATTAN | 31 | 0.015625s | 10841 | 6728 | | [8, 13, 0, 6, 1, 15, 9, 14, 3, 4, 5, 11, 7, 2, 10, 12] | MANHATTAN | 52 | 2.296875s | 1190087 | 586644 | | [2, 9, 5, 11, 8, 3, 4, 14, 7, 10, 1, 12, 0, 15, 6, 13] | MANHATTAN | 51 | 1.21875s | 563996 | 291157 | | [4, 7, 0, 9, 12, 10, 11, 8, 14, 6, 15, 1, 2, 5, 3, 13] | MANHATTAN | 56 | 126.203125s | 60152007 | 31402590 | | [12, 10, 3, 2, 0, 7, 14, 9, 1, 15, 5, 6, 8, 4, 13, 11] | MANHATTAN | 57 | 25.984375s | 12189299 | 6164828 | | [12, 1, 5, 6, 2, 11, 7, 9, 14, 10, 0, 4, 15, 3, 13, 8] | MANHATTAN | 50 | 3.171875s | 1800715 | 901800 | | [4, 6, 15, 13, 12, 9, 10, 2, 8, 0, 7, 3, 14, 5, 1, 11] | MANHATTAN | 61 | 200.609375s | 119733073 | 62259469 | ### Disjoint pattern | 序号 | 初始状态 | 阶数 | 解路径长 | 用时/s | 生成结点 | 扩展结点 | | ---- | ------------------------------------------------------ | ---- | -------- | -------- | --------- | -------- | | 1 | [8, 13, 0, 6, 1, 15, 9, 14, 3, 4, 5, 11, 7, 2, 10, 12] | 4 | 52 | 0.015625 | 74633 | 35914 | | 2 | [2, 9, 5, 11, 8, 3, 4, 14, 7, 10, 1, 12, 0, 15, 6, 13] | 4 | 51 | 0.296875 | 1482763 | 733377 | | 3 | [4, 7, 0, 9, 12, 10, 11, 8, 14, 6, 15, 1, 2, 5, 3, 13] | 4 | 56 | 3.34375 | 17679094 | 9082515 | | 4 | [12, 10, 3, 2, 0, 7, 14, 9, 1, 15, 5, 6, 8, 4, 13, 11] | 4 | 57 | 0.96875 | 4653566 | 2341723 | | 5 | [12, 1, 5, 6, 2, 11, 7, 9, 14, 10, 0, 4, 15, 3, 13, 8] | 4 | 50 | 0.609375 | 2244480 | 1102055 | | 6 | [4, 6, 15, 13, 12, 9, 10, 2, 8, 0, 7, 3, 14, 5, 1, 11] | 4 | 61 | 0.984375 | 5518958 | 2858198 | | 7 | [15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 1, 2, 0] | 4 | 70 | 22.25 | 110452322 | 58167830 | ## 参考文献 - 《人工智能：一种现代的方法》，作者：Stuart Russell，Peter Norvig - 启发式搜索与路径规划相关文献。 更多细节请参考[完整的研究报告](docs/研究报告.md)。