使用 A*（A Star）算法实现 8/15 拼图，C#

• 下载 15Puzzle.zip - 16.7 KB

引言

A* 算法

A*（“A Star”）算法是一种启发式搜索策略——即使用问题特定的知识，从问题本身派生出来的策略。

换句话说，它是一种最佳优先搜索算法，它根据总的估计成本来评估下一个可能的路径。它总是寻找可能路径中最经济的路径，并尝试朝着目标前进。

背景

那么 A* 是如何知道哪条路径是最经济的呢？让我们通过一个例子来看看。

在下图中，一个人需要从德里前往海得拉巴。我们知道一个人从一个城市到另一个城市必须实际覆盖的距离（绿色数字）。

所以，德里 -> 孟买的旅行距离是 12，德里 -> 勒克瑙是 7，孟买 -> 海得拉巴是 8，勒克瑙 -> 加尔各答是 6，加尔各答 -> 海得拉巴是 9。

在现实世界中，你可能会知道从所有可能的路径到达海得拉巴的总距离，并选择你看到需要覆盖的最小距离的路径。当人拥有从起点到终点的所有状态的信息时，这很容易。

挑战在于，当你对下一个目的地一无所知，直到你实际到达那里，也就是说，当你必须实际发现从一个点到另一个点的路径，并且你不知道状态，除非你处于那个状态。这种搜索被称为无信息搜索——除了问题定义本身之外，没有其他信息。

例如，除非你到达孟买，否则你不知道有从孟买到海得拉巴的路径。

现在，除了德里和孟买之间的实际距离，我们还知道每个城市到海得拉巴的直线距离——最短路径：始终小于或等于当前城市到海得拉巴的实际距离（称为 A* 算法的启发式函数）。

为方便表示，我们将一个城市到另一个城市的实际距离称为 g。

而海得拉巴到任何其他城市的直线距离称为 h。

正如你注意到的，启发式成本 h 没有高估成本 g（h <= g；这是 A* 收敛的一个非常重要的因素）。

现在，我们将从一个城市移动到另一个城市的距离称为实际距离 (g) 和直线距离 (h) 的总和。

f = g + h。

这个距离 (f) 被算法用来确定最经济的路径。因此，f 值较低的路径将优先于 f 值较高的路径。

现在，使用上述距离公式，我们可以弄清楚 A* 将如何搜索从德里到海得拉巴的最优路径。

到海得拉巴的直线距离

• 德里：20，孟买：12，勒克瑙：16，加尔各答：8，海得拉巴：0
• f(德里 -> 孟买) = 20 + 12 = 32
• f(德里 -> 勒克瑙) = 20 + 7 = 27

由于德里到勒克瑙的 f 值较低，下一个要扩展的路径是勒克瑙到加尔各答。

f(勒克瑙 -> 加尔各答) = 27 + 16 + 6 = 49。

现在我们有两个开放状态（德里 -> 孟买）和（勒克瑙 -> 加尔各答）。f 值最低的一个将进一步被探索（32 - 德里 -> 孟买）。

f(孟买 -> 海得拉巴) = 32 + 12 + 8 = 52

下一个要检查的路径是（德里 -> 勒克瑙 -> 加尔各答）。

f(加尔各答 -> 海得拉巴)：49 + 8 + 9 = 66

现在它已经到达目的地，并且它拥有可能的路径中最经济的一条，即德里 -> 孟买 -> 海得拉巴。它将回溯并将此路径声明为最优路径。

值得一提的是，它不会展开所有可能的路径到目的地。

它总是展开那些看起来最优的路径。例如，如果有一条从加尔各答 -> 布巴内斯瓦尔 -> 海得拉巴的路径，并且到达加尔各答 -> 布巴内斯瓦尔的总成本 > 52，A* 根本不会去考虑这条路径。它知道存在一条到最终目的地的路径，其 f 值为 52，而到布巴内斯瓦尔的 f 值大于 52。

8/15 拼图

那么如何使用这个路径查找算法来解决 8/15 拼图呢？

让我们来谈谈 8 拼图——一个简单的 3x3 网格上的滑动方块。你一次只能沿着空白块移动一步。当数字按顺序排列时，拼图就算解决了。

所以你有一个起始状态（一些随机排列），然后有一个要到达的最终状态。

这就是你开始解决拼图的方式

1. 获取第一个状态，这是你的起始状态。
2. 获取拼图可能存在的所有状态。
3. 将这些新状态添加到开放状态列表中。
4. 将已处理的状态添加到关闭列表中。
5. 从开放列表中选择成本最低的下一个状态。
6. 开始重复步骤 1 到 6，直到你达到最终状态，或者没有更多状态可检查（在这种情况下，不存在解决方案）。
7. 一旦你有了最终状态，就回溯到起始节点，那就是找到解决方案的最优路径。

那么这个问题应该有什么样的 g 和 h 成本呢？

因为每次你只移动一个方块——你可以说从一个状态移动到另一个状态的实际移动成本 (g) 是 1。

对于 8 拼图，网格可能存在的总状态数是 !9/2 = 181,440。所以你真的需要一种最优的方法来确定你是否正在接近目标，并且不会探索不必要的状态。

有两个常见的 h 成本（称为启发式成本）。

1. 错位方块的数量——你可以计算一个特定状态下错位方块的数量。当你处于最终状态时，h = 0。
2. 方块与其实际位置距离的总和（曼哈顿距离）——每个方块的水平和垂直距离的总和。

第二种启发式函数比第一种收敛得更快。

对于实现——

1. 你需要维护父节点信息来维护树，以便能够回溯。
2. 此外，你需要维护一个开放节点和关闭节点的列表，这样你就可以避免检查已经检查过的节点，并避免陷入循环。
3. 你可能希望使用最小优先队列数据结构来维护开放节点，以便能够快速获取要检查的下一个状态。不使用最小优先队列也可以做到——但那样会非常慢。
4. 你还需要哈希表来快速查找关闭/开放节点。

我使用 C# 实现了这个功能。你需要安装 .NET 4.0 才能运行该应用程序。

你可以从菜单中随机打乱排列并更改启发式函数。平均而言，它需要大约 44 秒（使用错位方块启发式函数）来判断一个排列是否无解（即，这个拼图无法解决）。
我的一位朋友告诉我，这种情况大约需要 9 秒才能收敛，所以我猜我的系统很糟糕。

最后一点——我添加 15 拼图到列表中时并没有撒谎。可以使用相同的代码。事实上，你只需要将网格从 3x3 更改为 4x4。但对于 15 拼图来说，这太慢了。15 拼图可能有 10^13 个状态，对于 A* 算法来说，处理起来太慢了。有一个更好的版本，我会在拥有它的时候再讨论。

修订后的代码

我已经优化了代码，使用了索引最小优先队列。这是为了加快从最小优先队列中查找和删除状态的速度。

当拼图无解时，这段代码需要大约 3.85 秒才能收敛，比以前的版本快了约 11 倍。