以特定方式对3x3矩阵进行排序的最小步骤数

Question

所以我在大学开始之前开始练习一些算法和编程,我遇到了这个问题:

给定包含0到8之间数字的3x3矩阵,找到以下列格式对矩阵进行排序所需的最小步骤数:

1 2 3
4 5 6
7 8 0

在一次移动中,只允许选择与包含0的单元相邻的单元并交换这两个单元.

现在,我真的很困惑这个,不知道如何开始.任何提示我开始的提示和想法都表示赞赏.

这不是家庭作业,如果有人这么想,我只是想锻炼,而且我遇到了更困难的问题.我不是在寻找任何人为我编写代码,我只需要一个正确的方向,因为我真的想了解这背后的算法.谢谢.

Answer 1

注意：这实际上是一个人工智能问题，而不是一个简单的数据结构/算法问题。

这个问题就叫做n-puzzle问题。你问题中的例子就是8-puzzle问题所在。

解决这个问题的方法是尝试以每一步都让你更接近最终目标的方式洗牌。将此视为贪婪方法 ( Best-first search)。这里使用的最佳算法是A* 算法。

我们将游戏的状态定义为棋盘位置、到达棋盘位置的移动次数以及之前的状态。首先，将初始状态（初始棋盘、0 次移动和空先前状态）插入优先级队列。然后，从优先级队列中删除具有最小优先级的状态，并将所有相邻状态（一次性可以到达的状态）插入到优先级队列中。重复此过程，直到出列的状态成为目标状态。这种方法的成功取决于国家优先职能的选择。我们考虑两个优先功能：

• 汉明优先函数。处于错误位置的方块数量，加上迄今为止到达该状态的移动次数。直观上，在错误位置上有少量块的状态接近目标状态，并且我们更喜欢使用少量移动达到的状态。

• 曼哈顿优先功能。从方块到目标位置的距离总和（垂直距离和水平距离的总和），加上到目前为止到达该状态的移动次数。

例如，下面初始状态的汉明优先级和曼哈顿优先级分别为5和10。

 8  1  3        1  2  3     1  2  3  4  5  6  7  8    1  2  3  4  5  6  7  8
 4     2        4  5  6     ----------------------    ----------------------
 7  6  5        7  8        1  1  0  0  1  1  0  1    1  2  0  0  2  2  0  3

 initial          goal         Hamming = 5 + 0          Manhattan = 10 + 0

我们做了一个关键的观察：要从优先级队列上的给定状态解决难题，我们需要执行的移动总数（包括已经执行的移动）至少是其优先级，使用汉明或曼哈顿优先级函数。（对于汉明优先级，这是正确的，因为每个不合适的块必须至少移动一次才能到达其目标位置。对于曼哈顿优先级，这是正确的，因为每个块必须将其曼哈顿距离移动到其目标位置。请注意，我们计算汉明或曼哈顿优先级时不要计算空白图块。）

因此，一旦我们将一个状态出队，我们不仅发现了从初始棋盘到与该状态相关的棋盘的一系列移动，而且还发现了移动次数最少的移动序列。

（来源）