标准难题的解决方案

Question

有一块板上有m*m个盒子，每个盒子都分配了一个非零整数，除了一个被标记为0的盒子，并被视为空的.Only空盒子的垂直和水平邻居可以向它移动，离开他们的位置vacant.To解决这个难题，我们必须安排在它们的值递增顺序的盒子(盒子标记为零)来结束(板的右下角).But像所有其他工程师一样，我们非常懒惰，希望在最小的步骤来解决它。

那么，除了回溯之外，我们应该遵循什么方法呢？

M的订单是500..ie 500x500板。

Answer 1

您可以通过简单地对数组进行排序来找到目标状态。假设你的目标状态是g，那么解决这个难题的一个简单但低效的算法是：

void solve()
{
    if(current_state == g)
        return;

    foreach(choice c in shifting_choices)
    {
      // shift neighbour
      apply choice;
      solve();
      undo choice;
    }
}

在上面的算法中，choices基本上是移动被zeroth块包围的块。

为了改进算法，你可以使用A* (最好的优先)。为了找到最佳选择，您可以使用Manhattan Distance。它基本上是在拼图中到达一个块到另一个块所需的步骤。请考虑以下内容：

6 2 1
5 0 3
4 7 8

在上述情况下，您可以移动2, 5, 3, 7，但要找到最佳移动，请考虑目标状态：

8 7 6
5 4 3
2 1 0

将块移动到zeroth块时，将更改两个块的位置。计算这两个街区从它们在目标状态中的位置到曼哈顿距离的总和。最小和中的选择将是最可取的：

Moving 2: 2 + 3 = 5

Moving 3: 1 + 1 = 2

Moving 7: 1 + 1 = 2

Moving 5: 1 + 2 = 3

你可以通过检查他们之前的位置来打破3和7之间的平局，3是正确的位置，因此7是局部最优的选择。