有一个棋盘,其中有 m*m 个盒子,每个盒子都分配了一个非零整数,除了一个被标记为 0 并被视为空置的盒子。只有空置盒子的垂直和水平邻居可以朝它移动,留下它们的位置作为空置.为了解决这个难题,我们必须按照它们的价值升序排列盒子,最后是空盒子(标记为零的盒子)(板的右下角)。但是像所有其他工程师一样,我们非常懒惰并且想要以最少的步骤解决它。
那么除了回溯,我们应该遵循什么方法。
m 为 500.. 即 500x500 板。
您可以通过简单地对数组进行排序来找到目标状态。假设你的目标状态是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 之间的平局,3 位于正确的位置,因此 7 是局部最优的选择。