排序数字的算法

Question

我有不同的数字，需要按升序排序，每个数字都用0交换。

结果数只能通过将每个数与0交换得到。

例如，我有3x3矩阵

   3    4     1
   2    5     0
   6    8     7

在上面的矩阵中，需要将数字与0交换以升序排列。从上面来看，在第一步中只有5、7和1与0交换。最终输出应该如下所示

   1    2     3
   4    5     6
   7    8     0

实现这一目标的最佳解决方案是什么?

谢谢

Answer 1

这是著名的15-puzzle的简单版本

处理这类问题的一般方法是将其建模为状态图，并运行最短路径算法以找到从源(给定板)到目标(排序板)的路径。

状态图为G=(V,E)，其中:V= { all possible boards }和E={(u,v) |可以通过一次交换将u板变为v} '。

您可以运行BFS或双向BFS(因为您有一个源和一个目标)，甚至可以使用带有适当的可接受启发式函数的A*算法来找到状态图上的路径，该路径表示产生解决方案的一系列交换。