X-Y启发式函数，用于求解N难题 [英] X-Y heuristic function for solving N-puzzle

问题描述

有人可以解释一下这种启发式功能吗，例如下面的4x4拼图布置，XY启发式成本是多少？

Can somebody please explain this heuristic function, for example for the following arrangement of 4x4 puzzle, whats the X-Y heuristic cost?

1  2  3  4 
5  6  7  8
9 10 11 12
0 13 14 15

（0表示空白）

推荐答案

从此处和此处 XY启发式是通过将所有图块相邻的空白相邻列交换的最小数量和与空白相邻列交换的最小行的数量相加得出的

As from here and here the X-Y heuristic is computed by the sum of the minimum number of column-adjacent blank swaps to get all tiles in their destination column and the minimum number of row adjacent blank swaps to get all tiles in their destination row.

因此在这种情况下：

1  2  3  4 
5  6  7  8
9 10 11 12
0 13 14 15

唯一放错位置的图块是 13 ， 14 和 15 ，assu设定目标状态为

the only misplaced tiles are 13 , 14 and 15, assuming the goal state is

1  2  3  4 
5  6  7  8
9 10 11 12
13 14 15 0

因此在这种情况下，我们必须首先计算列交换空白，以使所有图块都位于正确的位置。这等效于 3 ，因为空白板必须移动三遍到正确的列以位于正确的位置（并使所有磁贴处于正确的位置）

So in this case the we have to compute at first the number of column swaps the blank has to do to get all the tiles in the correct position. This is equivalent to 3, since the blank has to move three times to the the right column to be in the right position (and to have all the tiles in the right position)

然后，我们必须计算空白必须执行的行交换次数。这是 0 ，这是因为所有图块都已经在正确的行上了。

Then we have to compute the number of row swaps the blank has to do. This is 0 thanks to the fact that all the tiles are already on the correct row.

最后 h（n）= 3 + 0 = 3 。

这篇关于X-Y启发式函数，用于求解N难题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！