正如标题所说,我必须制作一个 prolog 程序,使用最佳优先搜索解决 8 个难题,我是 Prolog 和 AI 的新手,所以我很难过。
现在我所拥有的是移动规则:
%% 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).
我的想法是它搜索开始列表的每个元素并将其与目标列表进行比较,然后如果它们不同,则将 1 添加到 H,即 H 表示不合适的瓷砖数量。
对于我还定义了“在同一个地方的瓷砖规则”:
samePlace([X,_,_,_,_,_,_],[X,_,_,_,_,_,_]).
samePlace([_,X,_,_,_,_,_],[_,X,_,_,_,_,_]).
samePlace([_,_,X,_,_,_,_],[_,_,X,_,_,_,_]).
samePlace([_,_,_,X,_,_,_],[_,_,_,X,_,_,_]).
samePlace([_,_,_,_,X,_,_],[_,_,_,_,X,_,_]).
samePlace([_,_,_,_,_,X,_],[_,_,_,_,_,X,_]).
samePlace([_,_,_,_,_,_,X],[_,_,_,_,_,_,X]).
(etc...)
但当然我得到一个“错误:启发式/3:参数没有充分实例化”,我认为这意味着我从未初始化 H.
我不知道其余代码实际上是如何工作的,尽管我知道最好的第一个算法就像广度优先,但它根据启发式对队列进行排序,而不是仅仅添加它。
我的问题是: - 我是在正确的轨道上,还是我完全看错了那里的“启发式”功能是什么意思?- 如何初始化 H?- 我的“启发式”函数代码在语法上是否正确?
很抱歉发了这么长的帖子,但规则确实说我应该提供大量信息。我希望你能帮助我,感谢任何帮助,所以如果你知道这样做的任何其他方式,请随时发布它们,我是菜鸟。
提前致谢。