用Prolog的Best-First搜索法解决8个难题

Question

正如标题所说，我必须编写一个prolog程序，使用最佳优先搜索解决8个难题，我对Prolog和人工智能是新手，所以我遇到了一段艰难的时期。

现在我有的是移动规则：

%% move left in the top row
move([X1,0,X3, X4,X5,X6, X7,X8,X9],
     [0,X1,X3, X4,X5,X6, X7,X8,X9]).
move([X1,X2,0, X4,X5,X6, X7,X8,X9],
     [X1,0,X2, X4,X5,X6, X7,X8,X9]).

%% move left in the middle row
move([X1,X2,X3, X4,0,X6,X7,X8,X9],
     [X1,X2,X3, 0,X4,X6,X7,X8,X9]).
move([X1,X2,X3, X4,X5,0,X7,X8,X9],
     [X1,X2,X3, X4,0,X5,X7,X8,X9]).

%% move left in the bottom row
move([X1,X2,X3, X4,X5,X6, X7,0,X9],
     [X1,X2,X3, X4,X5,X6, 0,X7,X9]).
move([X1,X2,X3, X4,X5,X6, X7,X8,0],
     [X1,X2,X3, X4,X5,X6, X7,0,X8]).

%% move right in the top row 
    move([0,X2,X3, X4,X5,X6, X7,X8,X9],
     [X2,0,X3, X4,X5,X6, X7,X8,X9]).
move([X1,0,X3, X4,X5,X6, X7,X8,X9],
     [X1,X3,0, X4,X5,X6, X7,X8,X9]).

%% move right in the middle row 
move([X1,X2,X3, 0,X5,X6, X7,X8,X9],
     [X1,X2,X3, X5,0,X6, X7,X8,X9]).
move([X1,X2,X3, X4,0,X6, X7,X8,X9],
     [X1,X2,X3, X4,X6,0, X7,X8,X9]).

%% move right in the bottom row
move([X1,X2,X3, X4,X5,X6,0,X8,X9],
     [X1,X2,X3, X4,X5,X6,X8,0,X9]).
move([X1,X2,X3, X4,X5,X6,X7,0,X9],
     [X1,X2,X3, X4,X5,X6,X7,X9,0]).

%% move up from the middle row
move([X1,X2,X3, 0,X5,X6, X7,X8,X9],
     [0,X2,X3, X1,X5,X6, X7,X8,X9]).
move([X1,X2,X3, X4,0,X6, X7,X8,X9],
     [X1,0,X3, X4,X2,X6, X7,X8,X9]).
move([X1,X2,X3, X4,X5,0, X7,X8,X9],
     [X1,X2,0, X4,X5,X3, X7,X8,X9]).

%% move up from the bottom row
move([X1,X2,X3, X4,X5,X6, X7,0,X9],
 [X1,X2,X3, X4,0,X6, X7,X5,X9]).
move([X1,X2,X3, X4,X5,X6, X7,X8,0],
     [X1,X2,X3, X4,X5,0, X7,X8,X6]).
move([X1,X2,X3, X4,X5,X6, 0,X8,X9],
     [X1,X2,X3, 0,X5,X6, X4,X8,X9]).

%% move down from the top row
move([0,X2,X3, X4,X5,X6, X7,X8,X9],
     [X4,X2,X3, 0,X5,X6, X7,X8,X9]).
move([X1,0,X3, X4,X5,X6, X7,X8,X9],
     [X1,X5,X3, X4,0,X6, X7,X8,X9]).
move([X1,X2,0, X4,X5,X6, X7,X8,X9],
     [X1,X2,X6, X4,X5,0, X7,X8,X9]).

%% move down from the middle row
move([X1,X2,X3, 0,X5,X6, X7,X8,X9],
     [X1,X2,X3, X7,X5,X6, 0,X8,X9]).
move([X1,X2,X3, X4,0,X6, X7,X8,X9],
     [X1,X2,X3, X4,X8,X6, X7,0,X9]).
move([X1,X2,X3, X4,X5,0, X7,X8,X9],
     [X1,X2,X3, X4,X5,X9, X7,X8,0]).

(我知道使用列表有一种更简单的方法，但这就是对我有效的方法)

我在互联网上找到的最好的第一个代码是：http://www.cs.unm.edu/~luger/ai-final/code/PROLOG.best.html

但是在最好的第一个代码中，有一个启发式函数不能运行：

go(Start, Goal) :- 
   empty_set(Closed),
   empty_sort_queue(Empty_open),
   heuristic(Start, Goal, H),
   state_record(Start, nil, 0, H, H, First_record),
   insert_sort_queue(First_record, Empty_open, Open),
   path(Open,Closed, Goal).

我假设是因为它不是在任何地方定义的，我需要自己定义它，因为启发式会根据问题而变化。

因此，我考虑将“瓦片错位”启发式用于8字谜，因为它听起来比曼哈顿距离或其他任何东西更容易编码。但现在我被困在如何编程上了，我到处搜索如何比较列表和如何添加变量，我做了这个，我不知道它是否有效：

heuristic([],[],H).
heuristic([Head1|Tail1],[Head2|Tail2], H):-
   not(samePlace(Head1,Head2))->H1 is H + 1,
   heuristic(Tail1, Tail2, H1).

我的想法是，它搜索开始列表的每个元素，并将其与目标列表进行比较，然后如果它们不同，则将H加1，H是错位的瓦片数量。

我还定义了"tiles in the same place rules"：

samePlace([X,_,_,_,_,_,_],[X,_,_,_,_,_,_]).
samePlace([_,X,_,_,_,_,_],[_,X,_,_,_,_,_]). 
samePlace([_,_,X,_,_,_,_],[_,_,X,_,_,_,_]).
samePlace([_,_,_,X,_,_,_],[_,_,_,X,_,_,_]).
samePlace([_,_,_,_,X,_,_],[_,_,_,_,X,_,_]).
samePlace([_,_,_,_,_,X,_],[_,_,_,_,_,X,_]).
samePlace([_,_,_,_,_,_,X],[_,_,_,_,_,_,X]). 
(etc...)

但当然我得到了一个"ERROR: heuristic/3:参数没有充分实例化“，我认为这意味着我从未初始化过H。

我不知道其余的代码实际上是如何工作的，尽管我知道最好的first algorythm类似于广度优先，但它根据启发式对队列进行排序，而不仅仅是添加。

我的问题是：-我是在正确的轨道上，还是我完全误解了“启发式”函数的含义？-我如何初始化H？-我的“启发式”函数代码在语法上是正确的吗？

很抱歉发了这么长的帖子，但是规则确实说我应该提供大量的信息。我希望你能在这方面帮助我，任何帮助都是感激不尽的，所以如果你知道任何其他的方法，请随时张贴，我是一个新手。

提前谢谢。

Answer 1

引入了Prolog中的(->)/2来简化if..then..else建模。逻辑，但与命令式语言有一个重要的区别:没有'else‘分支，当条件失败时它就会失败。

现在你错过了启发式/3中的else分支。这可能是故意的，但我认为如果samePlace(Head1，Head2)在某个地方为真，这将无法返回值，从而开始回溯调用代码。根据我的经验，这通常是随后出现奇怪错误消息的原因，就像您报告的那样。

另一个问题是，即使谓词成功，您也无法“返回”值：

heuristic([],[],0).
heuristic([Head1|Tail1],[Head2|Tail2], H):-
   heuristic(Tail1, Tail2, H1),
   (   not(samePlace(Head1,Head2))
   ->  H is H1 + 1
   ;   H is H1
   ).