2

我正在尝试实现8-puzzle的求解器。拼图板表示为一个列表。例如，目标状态：

1 | 2 | 3
---------
4 | 5 | 6
---------
7 | 8 | 0

表示为[1,2,3,4,5,6,7,8,0]，其中0表示空白空间。

我已经实现move(+Board,-Move)了成功，Move因为董事会的所有可能状态都远离Board. 此外，我已经实施solvable(+Board)了true是否false可以解决董事会的问题。

我还实现了两个启发式方法manhattan(+Board,+Goal,-H)和hamming(+Board,+Goal,-H)，它计算从Board到的启发式方法成本Goal。例如：

?- hamming([1,2,3,8,0,4,7,6,5],[1,2,3,8,0,4,7,6,5],H).
H = 0.

?- hamming([1,2,3,4,0,8,7,6,5],[1,2,3,8,0,4,7,6,5],H).
H = 2.

?- manhattan([1,2,3,8,0,4,7,6,5],[1,2,3,8,0,4,7,6,5],H).
H = 0.

?- manhattan([1,2,3,4,0,8,7,6,5],[1,2,3,8,0,4,7,6,5],H).
H = 4.

我想将solve(+Board,+Heuristic,-Solution)其作为使用给定Solution解决方案的一种最佳解决方案来实现，并且它必须以精确的一种解决方案确定性地终止。例如：BoardHeuristic

?- solve([0,1,3,4,2,5,7,8,6],manhattan,Solution).
Solution = [
    [0, 1, 3, 4, 2, 5, 7, 8, 6],
    [1, 0, 3, 4, 2, 5, 7, 8, 6],
    [1, 2, 3, 4, 0, 5, 7, 8, 6],
    [1, 2, 3, 4, 5, 0, 7, 8, 6],
    [1, 2, 3, 4, 5, 6, 7, 8, 0]
].

我写了 A* 算法的伪代码：

For each Child of Board do:
    If Child in Closed do:
        Continue
    If Child not in Closed or G(Board) + 1 < G(Child) do:
        G(Child) := G(Board) + 1
        F(Child) := G(Child) + Heuristic(Child,Goal)
        If Child not in Open do:
            Open := Open + {Child}

其中G(Board)是 的实际成本Board，定义为Board从初始板到最佳路径的长度。F(Board)是 的组合成本Board，定义为 的总和G(Board)和估计的成本Board（由启发式函数定义）。当然Closed和Open是由 A* 算法维护的两个集合，Closed包含已访问Open的板，包含未访问的板。

问题是我不知道如何在 Prolog 中执行此操作。我认为维护这两个列表需要一些堆数据结构，但不知道是什么或如何。任何帮助都会很棒。

4

0 回答 0