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

Question

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

给定一个包含从 0 到 8 的数字的 3x3 矩阵，找到按以下格式对矩阵进行排序所需的最少步数:

1 2 3
4 5 6
7 8 0

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

现在，我真的被这个问题困住了，不知道如何开始。感谢任何帮助我入门的提示和想法。

如果有人这样想，这不是家庭作业，我只是想练习，通过转向更难的问题，我陷入了困境。我不是在寻找任何人为我编写代码，我只需要一个正确的方向，因为我真的很想了解这背后的算法。谢谢。

Answer 1

注意:这实际上是一个人工智能问题，而不是一个微不足道的数据结构/算法问题。

这个问题叫做n-puzzle 问题。您问题中的示例是 8-puzzle 问题。

解决此问题的方法是尝试以每一步都让您更接近最终目标的方式来洗牌。将此视为贪婪方法(最佳优先搜索)。此处使用的最佳算法是 A* algorithm .

We define a state of the game to be the board position, the number of moves made to reach the board position, and the previous state. First, insert the initial state (the initial board, 0 moves, and a null previous state) into a priority queue. Then, delete from the priority queue the state with the minimum priority, and insert onto the priority queue all neighboring states (those that can be reached in one move). Repeat this procedure until the state dequeued is the goal state. The success of this approach hinges on the choice of priority function for a state. We consider two priority functions:

• Hamming priority function. The number of blocks in the wrong position, plus the number of moves made so far to get to the state. Intutively, a state with a small number of blocks in the wrong position is close to the goal state, and we prefer a state that have been reached using a small number of moves.

• Manhattan priority function. The sum of the distances (sum of the vertical and horizontal distance) from the blocks to their goal positions, plus the number of moves made so far to get to the state.

For example, the Hamming and Manhattan priorities of the initial state below are 5 and 10, respectively.

 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

We make a key oberservation: to solve the puzzle from a given state on the priority queue, the total number of moves we need to make (including those already made) is at least its priority, using either the Hamming or Manhattan priority function. (For Hamming priority, this is true because each block that is out of place must move at least once to reach its goal position. For Manhattan priority, this is true because each block must move its Manhattan distance from its goal position. Note that we do not count the blank tile when computing the Hamming or Manhattan priorities.)

Consequently, as soon as we dequeue a state, we have not only discovered a sequence of moves from the initial board to the board associated with the state, but one that makes the fewest number of moves.

( Source )