什么样的启发对BFS的使用来解决这个“游戏”（找到路径）？(What kind of heurist

我要解决一个“游戏”。 我有5个圈，我们可以旋转圈成向左或向右成（90度）。

例：

目标：1,2,3，...，14,15,16例。 的启动情况：16,15,14，......，3,2,1

我使用BFS找到路径，但我不能发明启发式功能（我的每一个解决方案并不好）。 我试图曼哈顿距离和其他...（也许想法是好的，但有点毛病我的解决方案）。 请帮忙！

Answer 1:

一个窍门，你可以尝试是从目标状态做一个广度优先搜索落后。 早制止。 然后，你可以（从初始状态向前）搜索，一旦你已经打了由向后搜索看到的状态终止您。

从块到他们的目标曼哈顿距离的总和是正向A *搜索一个体面的基准启发。 你可以通过添加最多获得1-8到他们的地方，以获得9-16到他们的地方需要的圈数所需的圈数相当好; 这些状态空间是足够小（半十亿状态左右）预先计算。

Answer 2:

你可以使用一个启发是累积的圈数，它需要每一个人分段移动到指定的位置。 各个值将范围从零（该项目是在其点）到五（移动角到角）。 为目标配置的总为零。

一个具有使用此启发式，因为从初始配置要所需的配置可能需要步骤时，线匝的累积数量移动后增加要小心。

找到一个解决方案可能需要穷尽搜索。 您需要memoize的或使用其它DP技术来避免多次解决同一个位置。

Answer 3:

一个简单的保守（受理）启发是：

1. 对于每个编号1 <= I <= 16，发现把我回到其正确的位置所需的旋转的最小数目（不考虑所有其它号码）
2. 取最大值在所有这些最低。

这等于报告正确定位“最差”号需要转最小数量，因此绝不会高估所需的移动次数（因为固定所有数字位置同时至少需要尽可能多的移动的固定它们中的任何一个）。

它可能，但是，低估的一个很长的路需要移动次数。 可以通过计算获得更复杂的，对于每个编号1 <= I <= 16和用于每个车轮1 <= j的<= 5，通过移动任何序列所需车轮j的旋转的最小数目能够正确位置i。 对于每个车轮Ĵ，然后你可以接管所有的数字我单独的最高，最后加在一起这5个最大值，因为它们都是独立的。 （这可能小于之前的启发，但你总是获准参加两个更大，所以这不会是一个问题。）

文章来源: What kind of heuristics for BFS use to solve this 'game' (find path)?