algorithm - Prolog - 解决游戏，实现启发式

Question

我想解决一个“游戏”。我有 5 个圆圈，我们可以将圆圈向左或向右旋转(90 度)。

例子:

目标:1,2,3,....,14,15,16前任。起始情况:16,15,14,...,3,2,1

我正在使用 BFS。

启发式函数:

       heuristic(NextState,Goal,H)),

功能说明:

For each number 1 <= i <= 16, find the minimum number of rotations needed to put i back in its correct position (disregarding all other numbers)
Take the maximum over all these minimums.

这相当于报告正确定位“最差”数字所需的最小旋转次数，因此永远不会高估所需的移动次数(因为同时固定所有数字的位置至少需要与固定任何一个数字一样多的移动次数他们)。

它应该是什么样子？

A 圈示例:

heuristic(tiles([A,_,_,_],[_,_,_,_],[_,_,_,_],[_,_,_,_]),tiles([A,_,_,_],[_,_,_,_],[_,_,_,_],[_,_,_,_]),0).
heuristic(tiles([A,_,_,_],[_,_,_,_],[_,_,_,_],[_,_,_,_]),tiles([_,A,_,_],[_,_,_,_],[_,_,_,_],[_,_,_,_]),1).
heuristic(tiles([A,_,_,_],[_,_,_,_],[_,_,_,_],[_,_,_,_]),tiles([_,_,A,_],[_,_,_,_],[_,_,_,_],[_,_,_,_]),4).
heuristic(tiles([A,_,_,_],[_,_,_,_],[_,_,_,_],[_,_,_,_]),tiles([_,_,_,A],[_,_,_,_],[_,_,_,_],[_,_,_,_]),5).
heuristic(tiles([A,_,_,_],[_,_,_,_],[_,_,_,_],[_,_,_,_]),tiles([_,_,_,_],[A,_,_,_],[_,_,_,_],[_,_,_,_]),1).
heuristic(tiles([A,_,_,_],[_,_,_,_],[_,_,_,_],[_,_,_,_]),tiles([_,_,_,_],[_,A,_,_],[_,_,_,_],[_,_,_,_]),2).
heuristic(tiles([A,_,_,_],[_,_,_,_],[_,_,_,_],[_,_,_,_]),tiles([_,_,_,_],[_,_,A,_],[_,_,_,_],[_,_,_,_]),3).
heuristic(tiles([A,_,_,_],[_,_,_,_],[_,_,_,_],[_,_,_,_]),tiles([_,_,_,_],[_,_,_,A],[_,_,_,_],[_,_,_,_]),4).
heuristic(tiles([A,_,_,_],[_,_,_,_],[_,_,_,_],[_,_,_,_]),tiles([_,_,_,_],[_,_,_,_],[A,_,_,_],[_,_,_,_]),4).
heuristic(tiles([A,_,_,_],[_,_,_,_],[_,_,_,_],[_,_,_,_]),tiles([_,_,_,_],[_,_,_,_],[_,A,_,_],[_,_,_,_]),3).
heuristic(tiles([A,_,_,_],[_,_,_,_],[_,_,_,_],[_,_,_,_]),tiles([_,_,_,_],[_,_,_,_],[_,_,A,_],[_,_,_,_]),4).
heuristic(tiles([A,_,_,_],[_,_,_,_],[_,_,_,_],[_,_,_,_]),tiles([_,_,_,_],[_,_,_,_],[_,_,_,A],[_,_,_,_]),5).
heuristic(tiles([A,_,_,_],[_,_,_,_],[_,_,_,_],[_,_,_,_]),tiles([_,_,_,_],[_,_,_,_],[_,_,_,_],[A,_,_,_]),5).
heuristic(tiles([A,_,_,_],[_,_,_,_],[_,_,_,_],[_,_,_,_]),tiles([_,_,_,_],[_,_,_,_],[_,_,_,_],[_,A,_,_]),4).
heuristic(tiles([A,_,_,_],[_,_,_,_],[_,_,_,_],[_,_,_,_]),tiles([_,_,_,_],[_,_,_,_],[_,_,_,_],[_,_,A,_]),5).
heuristic(tiles([A,_,_,_],[_,_,_,_],[_,_,_,_],[_,_,_,_]),tiles([_,_,_,_],[_,_,_,_],[_,_,_,_],[_,_,_,A]),6).

这是个好主意吗？

Answer 1

看起来您正在尝试实现我建议的可接受启发式 here .

恐怕我根本不知道你想用你的“A 圈示例”代码做什么。计算将特定数字 i 从其当前位置移动到其最终正确位置所需的最小旋转次数的方法是将其视为一种特殊的最短路径问题，其中:

1. 我可能处于的每个位置都有一个顶点(所以总共有 16 个顶点)。
2. 只要有一个圆可以旋转 90 度(向任一方向)以将位置 x 中的任何数字移动到位置 y，则一对顶点 x 和 y 之间就有一条边。

为了具体起见，让我们用字母 A-P 标记位置(以及顶点)，如下所示:

ABCD
EFGH
IJKL
MNOP

例如，离开顶点 B 的边是:

1. A(因为逆时针旋转左上角的轮子会将 B 处的任何东西移动到 A)
2. F(因为顺时针旋转左上角的轮子会将 B 处的任何东西移动到 F)

旋转其他 4 个轮子中的任何一个都不会影响位置 B 的数字，因此这些是唯一离开顶点 B 的边。

其他一些顶点有更多的边。例如。 F 的边为:

1. B(逆时针旋转左上轮)
2. E(顺时针旋转左上角的轮子)
3. G(顺时针旋转中心轮)
4. J(逆时针旋转中心轮)

边没有加权(或等效地，权重为 1)并且是双向的，因为每个 90 度旋转都可以通过反向旋转来取消。

假设我们要计算将数字 9 从其初始位置(假设为 B)到最终正确位置 I 所需的最小旋转次数。

遍历一条边相当于将某个圆旋转 90 度，因此要找到将数字 9 从位置 B 移动到位置 I 所需的最小旋转次数，我们要找到一条连接顶点 B 和 I 的路径，该路径使用最小值可能的边数。因为所有边的权重都是 1，所以可以使用广度优先搜索有效地解决这个问题(如果边具有不同的权重，您可以使用 Dijkstra's algorithm 代替)。在 9 的情况下，答案将是 3(例如 B->F->J->I)。

因此，这解释了如何计算将特定数字移动到家的最小旋转次数。要计算启发式，请对初始配置中的每个数字执行此操作，然后选择最大值。 (请注意，每种情况下的图形都是相同的——只有起始顶点和目标顶点会发生变化。)这是您保证允许的启发式旋转计数值。