序言 - 解决游戏中，实施启发式 [英] Prolog - Solving game, implementing heuristics

问题描述

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

例如：

目标：1,2,3，...，14,15,16 例起始情况：16,15,14，......，3,2,1

我使用BFS。

启发式功能：

 启发式（NextState，目标，H）），
 

功能Desctiption：

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

这相当于报告需要正确定位最差转数最小数目，因此绝不会高估所需的移动次数（因为同时修复所有号码的立场至少需要尽可能多的动作是固定的任何一个他们）。

就应该是这样的容貌？

举例圈答：

<$p$p><$c$c>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).

这是个好主意吗？

解决方案

它看起来像你想实现的可容许启发我提出的这里。

我不能告诉你，你想要做你的榜样圈Acode在所有的东西，我很害怕。计算移动一个特定的数字，我从当前位置到最终的正确位置需要旋转的最小数量的方法是把它当作一种特殊的最短路径问题，其中：

1. 有一个顶点的每个位置上，我可能是（在所有所以16个顶点）。
2. 有一对顶点的x和y之间的边缘每当有可以旋转90度（在任一方向）移动至任何数目是在位置x到位置y的圆形。

有关具体化，让我们的标签的位置（因此顶点）字母AP如下：

  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）与最终的正确位置，我

遍历的边缘相当于旋转一些圈90度，所以要找到移动至9号位置B到位置我需要旋转的最小数目，我们希望找到一个路径连接顶点B和I，它使用的最小边缘尽可能多的。因为所有的边缘有重量1，这可以有效地利用广度优先搜索（如果边缘有各种各样的重量，你可以使用的 Dijkstra算法而不是）。在9的情况下，答案将是3（例如B-> F-> J => I）的

所以，这说明如何计算旋转的最小数目，用于​​移动一个特定数目的家。为了计算启发式，这样做的每个中的初始配置中的数字，和整体挑最大。 （请注意，该图是一样的在各种情况下 - 只有起点和终点的顶点会发生变化）。这是你保证，受理的启发旋转的计数值

I want to solve a 'game'. I have 5 circles, we can rotate circles into left or into right (90 degrees).

Example:

Goal: 1,2,3,....,14,15,16 Ex. of starting situations: 16,15,14,...,3,2,1

I'm using BFS.

Heuristic function:

       heuristic(NextState,Goal,H)),

Desctiption of function:

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.

This amounts to reporting minimum number of rotations needed to position the "worst" number correctly, and will therefore never overestimate the number of moves needed (since fixing all numbers' positions simultaneously requires at least as many moves as fixing any one of them).

How it should be looks?

Example for circle 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).

Is it a good idea?

解决方案

It looks like you're trying to implement the admissible heuristic I suggested here.

I can't tell what you're trying to do with your "example for circle A" code at all, I'm afraid. The way to calculate the minimum number of rotations needed to move a particular number i from its current position to its final, correct position is by treating it as a special kind of shortest-path problem, in which:

1. There is a vertex for each position that i could be in (so 16 vertices in all).
2. There is an edge between a pair of vertices x and y whenever there is a circle that can be rotated 90 degrees (in either direction) to move whatever number is in position x to position y.

For concreteness, let's label the positions (and therefore the vertices) with letters A-P as follows:

ABCD
EFGH
IJKL
MNOP

So for example the edges leaving vertex B are to:

1. A (since rotating the top-left wheel anticlockwise will move whatever is at B to A)
2. F (since rotating the top-left wheel clockwise will move whatever is at B to F)

Rotating any of the other 4 wheels has no effect on the number in position B, so those are the only edges leaving vertex B.

Some other vertices have more edges. E.g. F has edges to:

1. B (rotating the top-left wheel anticlockwise)
2. E (rotating the top-left wheel clockwise)
3. G (rotating the centre wheel clockwise)
4. J (rotating the centre wheel anticlockwise)

Edges are unweighted (or equivalently, have weight 1) and are bidirectional, since every 90-degree rotation can be undone by the reverse rotation.

Suppose we want to calculate the minimum number of rotations needed to get the number 9 from its initial position (let's say B) to its final, correct position, I.

Traversing an edge is equivalent to rotating some circle 90 degrees, so to find the minimum number of rotations needed to move number 9 from position B to position I, we want to find a path connecting vertices B and I that uses the minimum possible number of edges. Because all edges have weight 1, this can be solved efficiently using breadth first search (if edges had various weights, you could use Dijkstra's algorithm instead). In the case of 9, the answer will be 3 (e.g. B->F->J->I).

So, that explains how to calculate the minimum number of rotations for moving a particular number home. To calculate the heuristic, do this for each of the numbers in the initial configuration, and pick the maximum overall. (Notice that the graph is the same in each case -- only the start and destination vertices will change.) This is your guaranteed-admissible heuristic rotation count value.

这篇关于序言 - 解决游戏中，实施启发式的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！