我有不同的数字,需要通过将每个数字与 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
实现此目标的最佳解决方案是什么。
谢谢
最佳答案
这是著名的 15-puzzle 的简单版本.
解决此类问题的一般方法是将其建模为状态图,然后运行 shortest-path算法,以便找到从源(给定板)到目标(排序板)的路径。
状态图是 G=(V,E)
其中:V= { all possible boards }
and E={(u,v) |可以通过一次交换将板 u 更改为 v }`。
您可以运行 BFS或 bi-directional BFS (因为你有一个来源和一个目标),甚至是 A* Algorithm使用适当的可接受的启发式函数在状态图上找到路径,状态图表示产生解决方案的一系列交换。
关于排序数字的算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/24341845/