8 拼图 - WPF

• 下载源代码 - 1.18 MB

引言

本文 75% 的重点在于状态空间搜索算法。另外 25% 展示了如何在 Windows Presentation Foundation (也称为 WPF) 中使用动画。我希望通过视觉化方式来呈现一个计算机 (AI) 使用不同的搜索算法解决 8 拼图问题。不同的搜索算法包括：深度优先搜索；迭代深度优先搜索和 A*。

背景

159.302 人工智能 - 作业 1！我还需要多说什么吗？这是我参加 AI 课程时的一个作业。这个作业本来要求用 C/C++ 完成，但我用了 C#，因为重要的是实现搜索算法，而不是选择用什么语言来实现。而且我当时对 WPF 的动画支持非常感兴趣，想用它来更好地可视化每个算法如何影响 8 拼图的解决过程。我认为我提出的解决方案相当不错，所以没有什么比分享到 CodeProject 更好的方式了 =)。

不过请记住，和大多数（如果不是全部）学生一样，我大部分作业都是在截止日期前不久完成的。我将把注释的缺乏以及代码可能不是最佳组织方式归咎于此...

搜索算法简介

搜索算法在 AI 中非常重要。可以说，它们是系统探索各种可能性的基础。一个问题被表示为一个图，该图至少包含一个节点和若干条路径，如下图所示：

有状态（如奥克兰、汉密尔顿等）和连接不同状态的边（线）。这就是问题域，它包含一组可能的解决方案。给定从奥克兰到拉格兰的路径查找任务，使用搜索算法，您可以逐个节点地搜索和检查，从而系统地遍历所有可能的路径。有很多不同的算法，各有优缺点，但它们之间都大同小异。总之，如果您正在阅读本文，我假设您已经了解图和树，并且对搜索算法有一个基本的概念，但我还是会复习一下。

深度优先搜索

这是最基本的搜索算法，也被归类为任意路径非知晓型算法。因此，DFS 可能找不到最优解（如果找到的话）。它会检查所有可能的节点，直到找到目标。可以使用“已访问列表”（注意：已访问而非已扩展）来优化，以避免单向图中的循环。

使用堆栈实现 DFS 非常直接。当您检查一个节点是否有子节点时，将子节点添加到堆栈中，弹出堆栈并检查堆栈顶部的节点。没有比这更简单的了 =)。DFS 不能保证找到最浅的解决方案，或者如果陷入无限循环且未使用已访问列表，则可能找不到任何解决方案。

迭代深度优先搜索

IDFS，也是一种任意路径非知晓型算法，其扩展节点或找到解决方案的方式几乎与广度优先搜索完全相同。但是，BFS 的内存需求随着搜索深度的增加呈指数级增长。BFS 使用队列（先进后出，FILO）实现。IDFS 的内存需求与 DFS 相同，但与 DFS 不同的是，它会像 BFS 算法一样，在最浅的深度找到目标。

A* (读作 A Star)

被认为是最佳搜索算法之一，它被归类为最优知晓型算法。该算法使用启发式函数，该函数是搜索空间中到目标的直线距离的估计值。它必须是直线距离，因为只有当启发式函数（估计值）可接受时，A* 才能找到到目标的最佳路径；可接受意味着小于或等于到目标的实际距离。

Using the Code

所有算法的编程方式都差不多，我将只解释第一个也是最简单的 DFS。如您所知，DFS 是使用堆栈实现的。检查一个状态，然后将所有可以从该状态导出的可能状态添加到堆栈中。然后弹出堆栈以检索最先压入的最上面的状态，检查它是否是目标状态，如果不是，则检查通向其他状态的任何路径，依此类推。

//I store a state as a 2-dimensional double array. Each element can be thought of as
//a square on the 8 puzzle. 
class State
{
    public Double[][] xPuzzle = new Double[3][];    
    public Double[][] yPuzzle = new Double[3][];    
}

static public void initializeArray()
{
    for (int i = 0; i < 3; i++)
    {
        xPuzzle[i] = new Double[3];
        yPuzzle[i] = new Double[3];
    }
}

WPF 画布（8 拼图图像的容器）为 300px 正方形。每个方块为 100px。因此，数组 `xPuzzle` 和 `yPuzzle` 中的每个元素都存储了方块位置的 x 和 y 值。可能的值只能是集合 {0, 100, 200} 中的值，所以每个方块只能在画布上的 9 个可能位置中的 1 个位置上。这构成了存储表示 8 拼图特定状态的基础。我希望我已妥善解释了这一点。

您现在应该知道 DFS 的工作原理以及我如何在 C# 中实现 8 拼图状态了。

我使用 `System.Windows.Media.Animation` 命名空间中的 `DoubleAnimation` 类来动画化方块。

protected void UpdatePuzzle()
{
    DoubleAnimation xBox1 = new DoubleAnimation(PuzzleData.xPuzzle[0][0],
        TimeSpan.FromMilliseconds(AnmSpeed));
    DoubleAnimation xBox2 = new DoubleAnimation(PuzzleData.xPuzzle[0][1],
        TimeSpan.FromMilliseconds(AnmSpeed));
    DoubleAnimation xBox3 = new DoubleAnimation(PuzzleData.xPuzzle[0][2],
        TimeSpan.FromMilliseconds(AnmSpeed));
    DoubleAnimation xBox4 = new DoubleAnimation(PuzzleData.xPuzzle[1][0],
        TimeSpan.FromMilliseconds(AnmSpeed));
    DoubleAnimation xBox5 = new DoubleAnimation(PuzzleData.xPuzzle[1][1],
        TimeSpan.FromMilliseconds(AnmSpeed));
    DoubleAnimation xBox6 = new DoubleAnimation(PuzzleData.xPuzzle[1][2],
        TimeSpan.FromMilliseconds(AnmSpeed));
    DoubleAnimation xBox7 = new DoubleAnimation(PuzzleData.xPuzzle[2][0],
        TimeSpan.FromMilliseconds(AnmSpeed));
    DoubleAnimation xBox8 = new DoubleAnimation(PuzzleData.xPuzzle[2][1],
        TimeSpan.FromMilliseconds(AnmSpeed));
    DoubleAnimation xBox9 = new DoubleAnimation(PuzzleData.xPuzzle[2][2],
        TimeSpan.FromMilliseconds(AnmSpeed));
                
    DoubleAnimation yBox1 = new DoubleAnimation(PuzzleData.yPuzzle[0][0],
        TimeSpan.FromMilliseconds(AnmSpeed));
    DoubleAnimation yBox2 = new DoubleAnimation(PuzzleData.yPuzzle[0][1],
        TimeSpan.FromMilliseconds(AnmSpeed));
    DoubleAnimation yBox3 = new DoubleAnimation(PuzzleData.yPuzzle[0][2],
        TimeSpan.FromMilliseconds(AnmSpeed));
    DoubleAnimation yBox4 = new DoubleAnimation(PuzzleData.yPuzzle[1][0],
        TimeSpan.FromMilliseconds(AnmSpeed));
    DoubleAnimation yBox5 = new DoubleAnimation(PuzzleData.yPuzzle[1][1],
        TimeSpan.FromMilliseconds(AnmSpeed));
    DoubleAnimation yBox6 = new DoubleAnimation(PuzzleData.yPuzzle[1][2],
        TimeSpan.FromMilliseconds(AnmSpeed));
    DoubleAnimation yBox7 = new DoubleAnimation(PuzzleData.yPuzzle[2][0],
        TimeSpan.FromMilliseconds(AnmSpeed));
    DoubleAnimation yBox8 = new DoubleAnimation(PuzzleData.yPuzzle[2][1],
        TimeSpan.FromMilliseconds(AnmSpeed));
    DoubleAnimation yBox9 = new DoubleAnimation(PuzzleData.yPuzzle[2][2],
        TimeSpan.FromMilliseconds(AnmSpeed));
    
    //The statement below is basically an eventhandler for when the blank square's
    //animation stops. The Event handler is called the method Shuffle_Complete is
    //ShuffleDonw flag is not set and shuffleOn flag is set. This is how it loops
    //however many number of times defined in the Shuffle class. Look at Shuffle
    //Class for more info.
    if ((!Shuffle.shuffleDone)&&(Shuffle.shuffleOn)) {
        xBox9.Completed += new EventHandler(Shuffle_Completed); }

    //The statements below start the horizontal animation for each box.
    Box1.BeginAnimation(Canvas.LeftProperty, xBox1);
    Box2.BeginAnimation(Canvas.LeftProperty, xBox2);
    Box3.BeginAnimation(Canvas.LeftProperty, xBox3);
    Box4.BeginAnimation(Canvas.LeftProperty, xBox4);
    Box5.BeginAnimation(Canvas.LeftProperty, xBox5);
    Box6.BeginAnimation(Canvas.LeftProperty, xBox6);
    Box7.BeginAnimation(Canvas.LeftProperty, xBox7);
    Box8.BeginAnimation(Canvas.LeftProperty, xBox8);
    Box9.BeginAnimation(Canvas.LeftProperty, xBox9);
    
    //The statements below start the vertical animation for each box.
    Box1.BeginAnimation(Canvas.TopProperty, yBox1);
    Box2.BeginAnimation(Canvas.TopProperty, yBox2);
    Box3.BeginAnimation(Canvas.TopProperty, yBox3);
    Box4.BeginAnimation(Canvas.TopProperty, yBox4);
    Box5.BeginAnimation(Canvas.TopProperty, yBox5);
    Box6.BeginAnimation(Canvas.TopProperty, yBox6);
    Box7.BeginAnimation(Canvas.TopProperty, yBox7);
    Box8.BeginAnimation(Canvas.TopProperty, yBox8);
    Box9.BeginAnimation(Canvas.TopProperty, yBox9);
}

这就是我动画化方块的方式。每个方块的 x 和 y 位置都存储在一个数组中，我会在每次迭代中动画化所有这些方块。所以，如果一个方块的位置没有移动，它显然就不会被动画化。我将一个动画完成事件处理程序附加到了其中一个方块上。这个事件会启动当前使用的算法的下一个迭代，以此类推。

我如何实现搜索算法

以 DFS 算法为例。解决算法需要使用某些数据结构，例如队列、堆栈列表等。对于 DFS，我们将使用堆栈，因为我们需要一个先进先出 (FIFO) 的数据结构来存储我们的状态。

以我们之前的图为例：如果我们试图找到从奥克兰到陶朗加的路径，我们将从奥克兰节点开始。我们可以看到有一条连接到汉密尔顿和拉格兰的路径。所以我们将汉密尔顿和拉格兰节点添加到我们的堆栈中。接下来，我们从堆栈中弹出一个节点进行仔细检查。我们发现有一条路径连接汉密尔顿到拉格兰节点。所以我们将拉格兰添加到我们的堆栈中。*非常重要：但我们不会就此停止。我们不会因为已经访问了目标状态就停止搜索。我们只有在将目标节点从堆栈中弹出时才停止搜索。所以，在接下来的几次迭代中，拉格兰最终会被从堆栈中弹出。如果您通过简单地将您从堆栈中弹出的节点添加到列表中来跟踪它们，那么当您遍历列表时，最终会得到一条通过汉密尔顿从奥克兰到陶朗加的路径。记住，只有当您将目标节点从堆栈中弹出时，您才完成算法的迭代，而不是在将其放入堆栈时。因此，再次总结：

1. 将起始节点压入堆栈
2. 弹出节点进行检查并将节点附加到列表中
3. 如果从堆栈中弹出的节点是目标节点，那么从开始到结束的列表就代表了一条从开始到目标的路径
4. 检查节点并将任何连接的节点压入堆栈
5. 转到步骤 2

您可能已经注意到，目前的算法可能会出现无限循环。您可以通过使用已扩展列表来跟踪您已检查过的所有节点，从而稍微修改该算法。这就是我在这个应用程序中做的事情。

我应用程序中的一个节点或状态是存储 8 个方块位置的两个二维数组的组合。

所以，是的，只需下载应用程序并尝试一下。您可以通过看到实际情况来更好地理解。

关注点

WPF 是利用显卡功能在日常应用程序中最酷的东西，您不觉得吗？我丢失了我所有的 A* 算法更新（该死的糟糕源代码管理），所以它根本不像应该的那样工作……如果您能在我恢复它之前修复它，请这样做并发布一个更新。谢谢。

另外，正如我之前提到的，我想展示不同的算法是如何以不同的方式解决这个谜题的。我认为我做得很好。如果您尝试 DFS 和渐进式 DFS，您就能真正看到使用不同算法对达到目标所采取步骤的影响。顺便说一句，我对 DFS 使用了已扩展列表，因为 8 拼图在其搜索空间中可能存在无限循环。

结束

这是我的第一篇文章，我只是想分享一些我认为很酷的东西，并希望有人觉得它有用。我知道这很简略，但我只是想发布一些东西。您可以随意使用这些想法，并对源代码做任何您想做的事情，我唯一的要求是请注明出处。如果您真的很喜欢这篇文章，请投我一票并给我留言（这没什么难的 =P）。非常感谢...

历史

纠正了一些拼写错误和语义错误。感谢 Manuel & Ravi。感谢您指出这些错误 =)。