15数码问题求解算法及性能比较

本文最后更新于：2024年12月20日 晚上

15 数码问题求解算法及性能比较

摘要

本研究旨在探讨和比较不同求解算法及其启发式函数在解决 15 数码问题时的性能表现。15 数码问题是一个经典的益智游戏，涉及在一个 4x4 网格中通过移动方块达到有序布局。实验的核心是 A* 搜索算法，结合多种启发式函数（海明距离、棋盘距离、曼哈顿距离和欧几里得距离）进行性能评估。实验结果表明，曼哈顿距离和棋盘距离在求解时间和步数上表现优异，而海明距离则效率较低。研究还发现，问题的初始状态与目标状态之间的距离直接影响求解时间和步数。基于实验结果，提出改进建议，包括启发式函数的优化、算法适应性的增强以及并行计算的应用，以提升 15 数码问题求解算法的效率和适用性。

1.引言

15 数码问题是一个经典的益智游戏，起源于 19 世纪末。它由一个 4x4 的网格组成，包含 15 个标有数字的方块和一个空白位置。目标是通过移动方块（只能与空白位置相邻的方块交换位置）将初始的随机布局转变为有序的目标布局。这个问题不仅因其娱乐性而受到欢迎，也因其在计算机科学和人工智能领域的研究价值而备受关注。

15数码问题

图1 15数码问题

15 数码问题的研究意义在于它提供了一个理想的平台来探索和比较不同的搜索算法和启发式函数。由于其状态空间巨大（16! 种可能的布局），但又足够小以允许在合理的时间内进行搜索，因此它成为了评估算法性能的理想测试案例。此外，15 数码问题的求解过程涉及到路径搜索、启发式评估和状态空间表示等关键技术，这些技术在许多其他领域（如机器人路径规划、游戏AI等）中也有广泛应用。

本实验的目的是研究和比较不同的求解方法在解决 15 数码问题时的性能表现。我们将实现并分析多种启发式搜索算法，特别是 A* 算法，并探讨不同启发式函数对算法性能的影响。实验内容包括：设计和实现 15 数码问题的状态表示方法、生成初始状态、实现搜索算法及其启发式函数，并通过实验案例来评估这些算法的效率和有效性。通过这些研究，我希望深入理解启发式搜索算法的工作原理及其在实际问题中的应用潜力。

2. 问题的表示和求解算法

15 数码问题的状态表示方法

15 数码问题的状态表示是求解算法的基础。在一个 4x4 的网格中，有 15 个标有数字的方块和一个空白位置。状态表示需要捕捉每个方块的位置以及空白位置。以下是状态表示的详细方法：

  1. 字符串表示：
    • 使用一个长度为 16 的字符串来表示整个网格的状态。每个字符代表一个方块或空白位置。
    • 数字方块用字符 ‘a’ 到 ‘p’ 表示，分别对应数字 0 到 15。
    • 空白位置用特定字符（如 ‘a’）表示。
  2. 字符映射：
    • 使用一个映射表 unordered_map<int, char> h 将数字映射到字符，方便状态表示和处理。
  3. 目标状态：
    • 目标状态是一个特定的字符串，表示所有方块按顺序排列的状态（例如 “bcdefghijklmnop”）。
1
2
int ha[16] = {15, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14}; // 每个数字的目标位置映射 如0->15, 1->0
int num[16];                      // 初始状态，存储输入的 16 个数字

15 数码问题的求解算法

求解 15 数码问题的核心是搜索算法和启发式函数的结合。以下是求解算法的详细描述：

  1. 搜索算法：
    • 使用 A* 搜索算法，这是一种启发式搜索算法，结合了最佳优先搜索和 Dijkstra 算法的特点。
    • A* 算法通过优先队列管理待搜索的状态，优先选择估价函数值最小的状态进行扩展。
  2. 启发式函数：
    • 海明距离 (hamming_distance)：计算当前状态与目标状态不同的块的数量。这个函数衡量的是有多少个方块不在正确的位置。
    • 棋盘距离 (chessboard_f)：计算每个方块到其目标位置的最大单轴距离。
    • 曼哈顿距离 (manhattan_f)：计算每个方块到其目标位置的曼哈顿距离之和。这个函数考虑了方块的行和列位置。
    • 欧几里得距离 (euclidean_f)：计算每个方块到其目标位置的欧几里得距离之和。这个函数考虑了方块的直线距离。
  3. 状态扩展：
    • 在搜索过程中，每个状态通过移动空白位置的相邻方块进行扩展，生成新的状态。
    • 每个新状态的估价函数值由启发式函数计算，并根据这个值决定其在优先队列中的位置。
  4. 路径回溯：
    • 通过记录每个状态的前驱状态，实现路径回溯。一旦找到目标状态，就可以通过回溯前驱状态来重建解路径。
  5. 可解性判断：
    • 在开始搜索之前，通过计算逆序数和空格位置来判断初始状态是否有解。这一步确保了搜索不会在无解的状态上浪费资源。

通过上述状态表示和求解算法的设计，15 数码问题的求解过程被有效地组织和优化。A* 算法结合多种启发式函数，能够在合理的时间内找到问题的解。

3. 实验设计

实验目标

实验的主要目标是研究和比较不同求解算法在解决 15 数码问题时的性能表现。具体目标包括：

  1. 算法性能评估：通过实验评估不同搜索算法及其启发式函数在解决 15 数码问题时的效率和有效性。
  2. 启发式函数比较：比较不同启发式函数（如海明距离、曼哈顿距离、欧几里得距离）对 A* 算法性能的影响。
  3. 问题难度分析：通过设计不同难度级别的 15 数码问题实例，分析算法在不同难度下的表现。
  4. 可视化展示：以可视化方式呈现搜索过程，帮助理解算法的工作原理和性能差异。

评价指标

为了全面评估算法性能，实验采用以下评价指标：

  1. 求解时间：记录算法找到解决方案所需的时间。这是衡量算法效率的关键指标。
  2. 步数：记录从初始状态到目标状态所需的最少移动步数。这是衡量算法有效性的重要指标。

设计难度不同的 15 数码问题实例

下面给出16种不同的样例（总体难度递增）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
5 1 2 4 9 6 3 8 13 15 10 11 0 14 7 12
5 1 2 3 0 6 8 4 9 10 7 11 13 14 15 12
5 1 3 4 2 0 7 8 10 6 11 12 9 13 14 15
1 0 3 4 5 2 7 8 9 6 11 12 13 10 14 15
1 2 3 0 5 6 7 4 9 10 11 8 13 14 15 12
0 1 2 3 5 6 7 4 9 10 11 8 13 14 15 12
1 2 3 4 5 6 7 8 9 10 11 12 13 0 14 15
1 2 3 4 5 6 7 8 9 10 11 12 0 13 14 15
5 1 2 4 9 6 3 8 13 15 10 11 0 14 7 12
1 2 6 4 5 10 11 8 13 9 15 0 7 12 3 14
1 2 3 4 5 10 6 8 0 9 7 12 13 14 11 15
2 5 1 3 7 11 6 4 10 14 9 8 13 0 12 15
5 3 7 8 1 2 11 4 13 6 15 14 0 10 9 12
11 9 4 15 1 3 0 12 7 5 8 6 13 2 10 14
0 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
1 3 5 7 9 11 13 15 2 4 6 8 10 12 14 0

选择并实现不同的搜索算法

本实验采用A*算法，通过更换不同的启发函数来对比不同启发函数下算法的有效性和效率。

  • 海明距离
  • 棋盘距离
  • 曼哈顿距离
  • 欧几里得距离

4. 实验结果

选取了六种难易不同的初始状态进行在不同启发函数下的对比实验，结果如下表所示：

表1 不同样例在不同方法下的求解结果(TLE表示超出规定求解时间)
初始状态A* (海明距离)A* (棋盘距离)A* (曼哈顿距离)A* (欧几里得距离)
5 1 2 4 9 6 3 8 13 15 10 11 0 14 7 12TLE时间：0.000188218秒，步数：15时间：0.000174202秒，步数：15时间：0.000294349秒，步数：15
1 0 3 4 5 2 7 8 9 6 11 12 13 10 14 15TLE时间：3.4887e-05秒，步数：5时间：4.0557e-05秒，步数：5时间：5.268e-05秒，步数：5
1 2 3 4 5 6 7 8 9 10 11 12 0 13 14 15TLE时间：1.9928e-05秒，步数：3时间：3.0228e-05秒，步数：3时间：3.3814e-05秒，步数：3
2 5 1 3 7 11 6 4 10 14 9 8 13 0 12 15TLE时间：1.85473秒，步数：32时间：0.182626秒，步数：32时间：2.17753秒，步数：32
5 3 7 8 1 2 11 4 13 6 15 14 0 10 9 12TLE时间：76.0207秒，步数：39时间：3.7021秒，步数：39时间：84.4167秒，步数：39
11 9 4 15 1 3 0 12 7 5 8 6 13 2 10 14TLE时间：16.3697秒，步数：41时间：0.108953秒，步数：41时间：18.5989秒，步数：41

从表中可以发现，海明距离作为启发函数的A*算法求解效率极低，在规定时间基本无法求解出正确结果。而棋盘距离，曼哈顿距离和欧几里得距离均可求得正确答案。但其中曼哈顿距离的优势较为明显，求解速度很快，在困难的任务中尤其突出。

5. 实验分析与讨论

通过上述实验，可以得出以下结论：

  1. 海明距离的局限性：
    • 在所有测试案例中，使用海明距离作为启发函数的 A* 算法均未能在合理时间内找到解决方案。这表明海明距离在这种类型的问题中可能不够有效，因为它没有充分利用方块位置的具体信息。
  2. 棋盘距离的优势：
    • 棋盘距离在大多数情况下表现出了较好的性能，尤其是在较难的实例中（如第四个和第五个示例）。它通常能够在较短的时间内找到解决方案，尽管在某些情况下步数可能较多。
  3. 曼哈顿距离的稳定性：
    • 曼哈顿距离在所有测试案例中均表现出稳定的性能，提供了较好的时间效率和步数。它在处理不同难度的实例时都能保持较好的表现，显示出其作为启发函数的可靠性。
  4. 欧几里得距离的效率：
    • 欧几里得距离在某些情况下（如第一个和第三个示例）提供了最快的求解时间，但在其他更复杂的实例中可能不如棋盘距离或曼哈顿距离有效。这表明欧几里得距离在某些特定情况下可能更优。

可视化分析：

在求解过程通过打印棋盘状态来进行过程的可视化分析

1
2
3
4
5
6
7
8
// 输出棋盘的函数，将状态字符串输出为 4x4 格局
void print_board(string s) {
    for (int i = 0; i < 16; i++) {
        cout << int(s[i]-'a') << " ";
        if ((i + 1) % 4 == 0) cout << "\n"; // 每4个数换行
    }
    cout << "\n";
}

例如选取初始状态1 0 3 4 5 2 7 8 9 6 11 12 13 10 14 15，运行结果如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
1 0 3 4 
5 2 7 8 
9 6 11 12 
13 10 14 15 

1 2 3 4 
5 0 7 8 
9 6 11 12 
13 10 14 15 

1 2 3 4 
5 6 7 8 
9 0 11 12 
13 10 14 15 

1 2 3 4 
5 6 7 8 
9 10 11 12 
13 0 14 15 

1 2 3 4 
5 6 7 8 
9 10 11 12 
13 14 0 15 

1 2 3 4 
5 6 7 8 
9 10 11 12 
13 14 15 0 

Time taken: 5.4303e-05 seconds
Steps: 5
DDDRR

6. 结论

通过对 15 数码问题的多种求解算法及其启发式函数的实验比较，我们得出以下结论：

  1. 启发式函数的重要性：
    • 启发式函数的选择对 A* 算法的性能有显著影响。曼哈顿距离和棋盘距离通常提供了较好的性能，而海明距离在这种情况下可能不够有效。
  2. 算法效率的差异：
    • A* 算法结合适当的启发式函数（如曼哈顿距离和棋盘距离）在求解时间和步数上表现优异，尤其是在处理较难的实例时。
  3. 问题难度的影响：
    • 初始状态与目标状态之间的距离（如逆序数）直接影响求解时间和步数。更复杂的问题需要更高效的启发式函数来指导搜索。

改进建议

基于实验结果，提出以下对改进 15 数码问题求解算法的思考和建议：

  1. 启发式函数的优化：
    • 继续研究和开发更高效的启发式函数，以进一步提高 A* 算法的性能。可以考虑结合多种启发式函数的优点，设计新的复合启发式函数。
  2. 算法的适应性：
    • 改进算法以适应不同难度的问题。对于更复杂的问题，可以考虑使用更高级的搜索策略，如迭代深化搜索或双向搜索。
  3. 并行计算的应用：
    • 利用并行计算技术来加速搜索过程。通过多线程或分布式计算，可以同时探索多个搜索路径，从而提高求解速度。
  4. 算法的泛化能力：
    • 研究算法在其他类似问题（如更大规模的数码问题）中的应用潜力，以验证其泛化能力。

参考文献

[1] Johnson, W. W., & Story, W. E. (1879). Notes on the “15” puzzle. American Journal of Mathematics, 2(4), 397-404.

[2] Story, W. E. (1879). Notes on the” 15” Puzzle. American Journal of Mathematics, 2(4), 397-404.

[3] Culberson, J., & Schaeffer, J. (1994). Efficiently searching the 15-puzzle.

[4] Tang, G., Tang, C., Claramunt, C., Hu, X., & Zhou, P. (2021). Geometric A-star algorithm: An improved A-star algorithm for AGV path planning in a port environment. IEEE access, 9, 59196-59210.

[5] Erke, S., Bin, D., Yiming, N., Qi, Z., Liang, X., & Dawei, Z. (2020). An improved A-Star based path planning algorithm for autonomous land vehicles. International Journal of Advanced Robotic Systems, 17(5), 1729881420962263.

[6] https://www.geeksforgeeks.org/a-search-algorithm/

[7] https://en.wikipedia.org/wiki/15_puzzle

[8] https://blog.csdn.net/qq_44174803/article/details/109901611

附录

代码

astar.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
#include <iostream>
#include <cmath>
#include <vector>
#include <queue>
#include <unordered_map>
#include <chrono> // 用于计时
using namespace std;

unordered_map<int, char> h;                // 数字到字符的映射（方便状态表示）
unordered_map<string, int> dist;           // 当前状态的步数
unordered_map<string, string> pre;         // 当前状态的前一个状态，用于路径回溯
typedef pair<int, string> PIS;             // 优先队列元素：估价函数值和状态字符串

#define x first
#define y second

int ha[16] = {15, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14}; // 每个数字的目标位置映射 如0->15, 1->0
int num[16];                      // 初始状态，存储输入的 16 个数字

// 海明距离
int hamming_distance(string s) {
    int cnt = 0;
    for (int i = 0; i < 16; i++) {
        if (s[i] != 'a' && s[i] != h[i]) {  // 如果当前块不等于目标位置的块
            cnt++;
        }
    }
    return cnt;
}

// 棋盘距离作为启发函数，计算状态字符串到目标状态的距离
int chessboard_f(string s) {
    int cnt = 0;
    for (int i = 0; i < 16; i++) {
        int p = s[i] - 'a';       // 将字符映射回数字
        if (!p) continue;         // 'a' 表示空格，跳过
        int sx = i % 4, sy = i / 4;                // 当前数字位置的坐标
        int tx = ha[p] % 4, ty = ha[p] / 4;      // 目标位置坐标
        cnt += max(abs(sx - tx), abs(sy - ty));  // 棋盘距离
    }
    return cnt;
}

// 曼哈顿距离作为启发函数，计算状态字符串到目标状态的距离
int manhattan_f(string s) {
    int cnt = 0;
    for (int i = 0; i < 16; i++) {
        int p = s[i] - 'a';       // 将字符映射回数字
        if (!p) continue;         // 'a' 表示空格，跳过
        int sx = i % 4, sy = i / 4;                // 当前数字位置的坐标
        cnt += abs(sx - ha[p] % 4) + abs(sy - ha[p] / 4); // 曼哈顿距离
    }
    return cnt;
}

// 欧几里得距离作为启发函数，计算状态字符串到目标状态的距离
int euclidean_f(string s) {
    int cnt = 0;
    for (int i = 0; i < 16; i++) {
        int p = s[i] - 'a';       // 将字符映射回数字
        if (!p) continue;         // 'a' 表示空格，跳过
        int sx = i % 4, sy = i / 4;                // 当前数字位置的坐标
        int tx = ha[p] % 4, ty = ha[p] / 4;      // 目标位置坐标
        cnt += sqrt(pow(sx - tx, 2) + pow(sy - ty, 2));  // 欧几里得距离
    }
    return cnt;
}

// 判断数码问题是否有解，通过计算逆序数和空格位置校验
bool solvable() {
    int cnt = 0;
    for (int i = 0; i < 16; i++) {
        if (!num[i]) cnt += 3 - i / 4;  // 空格所在行到目标状态行的距离
        else {
            for (int j = 0; j < i; j++) {
                if (num[j] && num[j] > num[i]) cnt++;  // 计算逆序数
            }
        }
    }
    return cnt % 2 == 0;  // 可解当且仅当逆序数为偶数
}

// 输出棋盘的函数，将状态字符串输出为 4x4 格局
void print_board(string s) {
    for (int i = 0; i < 16; i++) {
        cout << int(s[i]-'a') << " ";
        if ((i + 1) % 4 == 0) cout << "\n"; // 每4个数换行
    }
    cout << "\n";
}

// A* 搜索主算法
int Astar(string sta, int (*f)(string)) {
    auto start_time = chrono::high_resolution_clock::now(); // 开始计时
    priority_queue<PIS, vector<PIS>, greater<PIS>> q; // 小顶堆，按估价函数排序
    q.push({f(sta), sta});                           // 初始状态入队
    dist[sta] = 0;                                   // 初始状态步数为 0

    while (q.size()) {
        auto t = q.top();
        q.pop();
        string s = t.y;
        int step = t.x;

        // 输出每一步的棋盘矩阵，计时时注释掉，减少IO时间
        // print_board(s);

        if (!f(s) && dist[s] <= 45) {
            auto end_time = chrono::high_resolution_clock::now(); // 结束计时
            chrono::duration<double> elapsed = end_time - start_time;
            cout << "Time taken: " << elapsed.count() << " seconds\n";
            return dist[s]; // 找到目标状态
        }
        if (step > 45) break;                      // 超过搜索步数限制，认为无解

        int zero;                                  // 记录空格位置
        for (int i = 0; i < 16; i++) {
            if (s[i] == 'a') {
                zero = i;
                break;
            }
        }

        // 四个方向的状态转移
        vector<int> directions = {-4, 4, -1, 1};   // 上下左右
        for (int d : directions) {
            int newZero = zero + d;
            if (newZero < 0 || newZero >= 16) continue;    // 越界检测
            if ((zero % 4 == 0 && d == -1) || ((zero + 1) % 4 == 0 && d == 1)) continue; // 水平越界检测

            string ss = s;
            swap(ss[zero], ss[newZero]);                   // 交换空格和目标位置
            if (!dist.count(ss) && ss != sta) {            // 新状态未被访问过
                dist[ss] = dist[s] + 1;                    // 更新步数
                q.push({dist[ss] + f(ss), ss});            // 入队
                pre[ss] = s;                               // 记录前驱状态
            }
        }
    }
    return -1; // 搜索失败，返回无解
}

// 根据两个状态的空格位置，返回操作方向
char check(string a, string b) {
    int d1, d2;
    for (int i = 0; i < a.size(); i++)
        if (a[i] == 'a') {
            d1 = i;
            break;
        }
    for (int i = 0; i < b.size(); i++)
        if (b[i] == 'a') {
            d2 = i;
            break;
        }
    if (d1 - 4 == d2) return 'U';
    if (d1 == d2 - 4) return 'D';
    if (d1 - 1 == d2) return 'L';
    if (d1 + 1 == d2) return 'R';

    return '?'; // 不应发生
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    for (int i = 0; i <= 15; i++) h[i] = 'a' + i; // 初始化字符映射

    int T = 1;
    cin >> T;
    while (T--) {
        string s;
        dist.clear();
        pre.clear();

        for (int i = 0, x; i < 16; i++) {
            cin >> x;
            num[i] = x;
            s += h[x];
        }

        if (!solvable()) {  // 判断是否有解
            cout << "This puzzle is not solvable.\n";
            continue;
        }

        int res = Astar(s, chessboard_f); // 启发函数
        if (res == -1){
            cout << "No answer for search" << endl;
            continue;
        }
        cout << "Steps: " << res << endl;

        // 回溯找到解路径
        string ss = "bcdefghijklmnopa", ans;
        while (ss != s) {  
            string sss = pre[ss];
            ans += check(sss, ss);
            ss = sss;
        }

        for (int i = ans.size() - 1; i >= 0; i--) cout << ans[i]; // 逆序输出路径
        cout << "\n";
    }

    return 0;
}

数据表

表1 不同样例在不同方法下的求解结果(TLE表示超出规定求解时间)
初始状态A* (海明距离)A* (棋盘距离)A* (曼哈顿距离)A* (欧几里得距离)
5 1 2 4 9 6 3 8 13 15 10 11 0 14 7 12TLE时间：0.000188218秒，步数：15时间：0.000174202秒，步数：15时间：0.000294349秒，步数：15
1 0 3 4 5 2 7 8 9 6 11 12 13 10 14 15TLE时间：3.4887e-05秒，步数：5时间：4.0557e-05秒，步数：5时间：5.268e-05秒，步数：5
1 2 3 4 5 6 7 8 9 10 11 12 0 13 14 15TLE时间：1.9928e-05秒，步数：3时间：3.0228e-05秒，步数：3时间：3.3814e-05秒，步数：3
2 5 1 3 7 11 6 4 10 14 9 8 13 0 12 15TLE时间：1.85473秒，步数：32时间：0.182626秒，步数：32时间：2.17753秒，步数：32
5 3 7 8 1 2 11 4 13 6 15 14 0 10 9 12TLE时间：76.0207秒，步数：39时间：3.7021秒，步数：39时间：84.4167秒，步数：39
11 9 4 15 1 3 0 12 7 5 8 6 13 2 10 14TLE时间：16.3697秒，步数：41时间：0.108953秒，步数：41时间：18.5989秒，步数：41
AI
#AI
15数码问题求解算法及性能比较
https://furthur509.github.io/2024/12/20/15 数码问题求解算法及性能比较/
作者
Yang Mingxin
发布于
2024年12月20日
许可协议