Prolog解题游戏，实现启发式

Question

我想解决一个‘游戏’。我有5个圆，我们可以把圆圈转到左或右(90度)。

示例：

​

​

​

​

目标: 1,2,3，....,14,15,16 Ex。开始情况: 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

看起来，您正在尝试实现我建议的这里允许的启发式。

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

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

为了具体起见，让我们用字母as标记位置(因此是顶点)如下：

ABCD
EFGH
IJKL
MNOP

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

1. A(因为左上轮逆时针旋转，任何在B到A的位置都会移动)
2. F(因为左上轮顺时针旋转时，B到F处的任何东西都会移动)

转动其他四个轮子对位置B中的数没有影响，所以这些是唯一离开顶点B的边。

其他一些顶点有更多的边。例如，F有边沿：

1. 逆时针旋转左上轮
2. E(顺时针旋转左上轮)
3. 按顺时针方向旋转中心轮
4. 逆时针旋转中心轮

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

假设我们想要计算出从初始位置(假设B)到最后的正确位置所需的最小旋转次数，I。

遍历一个边相当于旋转某个圆圈90度，所以为了找到从位置B到位置I的9移动所需的最小旋转数，我们想要找到一条连接点B和i的路径，它使用尽可能少的边数。因为所有边都有权重1，所以可以使用宽度优先搜索有效地解决这个问题(如果边有不同的权重，则可以使用迪克斯特拉算法 )。在9的情况下，答案是3(例如B->F->J->I)。

因此，这解释了如何计算移动一个特定数字回家的最小旋转次数。要计算启发式，对初始配置中的每个数字执行此操作，并从总体上选择最大值。(请注意，图在每种情况下都是相同的--只有起始点和目标顶点会改变。)这是你的保证-允许的启发式旋转计数值。