2

这是我到目前为止所写的。

goal(g).

arc(a,b).
arc(a,c).
arc(a,d).
arc(c,k).
arc(c,f).
arc(d,g).
arc(d,h).
arc(d,i).
arc(f,l).
arc(h,m).


dfs_start(InititalState,Goal,Solution) :-
                                        dfs([InititalState],[],Goal,Solution).

dfs([H|_],_,Goal,[H]):-
                         Check =.. [Goal,H],
                         call(Check).

dfs([H|T], Explored, Goal, Solution):-
           findall( X, (arc(H,X), \+ member(X,Explored), \+ member(X,[H|T]) ), Children),
           append(Children,T,OpenList),
           dfs(OpenList, [H|Explored], Goal, Solution).

我正在使用 Russel-Norvig 中描述的算法。我不知道如何创建整个路径。我在这里遗漏了一些东西。对我来说，Russel-Norvig 真的很神秘。

4

1 回答 1

4

因此，在 dfs_start/3 中，您希望引用在 dfs/4 中探索过的所有节点，但 dfs/4 没有引用这些节点的参数。因此，您应该引入一个可用于此的附加参数：

dfs_start(InititalState, Goal, Es, Solution) :-
        dfs([InititalState], [], Es, Goal, Solution).

dfs([H|_], Es0, Es, Goal, H) :- call(Goal, H), reverse(Es0, Es).
dfs([H|T], Es0, Es, Goal, Solution):-
        findall(X, (arc(H, X),
                       \+ member(X, Es0),
                       \+ member(X, [H|T]) ), Children),
        append(Children, T, OpenList),
        dfs(OpenList, [H|Es0], Es, Goal, Solution).

示例查询：

?- dfs_start(a, goal, Path, Solution).
Path = [a, b, c, k, f, l, d],
Solution = g ;
false.

编辑：从您的评论中，我现在看到您想要什么。这很简单：只需按照到达的方式关联到打开列表中的每个节点：

dfs_start(Start, Goal, Path, Solution) :-
        dfs([Start-[]], [], Goal, Path, Solution).

dfs([H-Path0|_], _, Goal, Path, H) :- call(Goal, H), reverse([H|Path0], Path).
dfs([H-Path0|T], Es, Goal, Path, Solution):-
        findall(X-[H|Path0], (arc(H, X),
                       \+ member(X, Es),
                       \+ member(X-_, [H-_|T]) ), Children),
        append(Children, T, OpenList),
        dfs(OpenList, [H|Es], Goal, Path, Solution).

示例查询：

?- dfs_start(a, goal, Path, Solution).
Path = [a, d, g],
Solution = g ;
false.

还要考虑深度优先搜索在 Prolog 中通过内置的时间回溯提供，因此虽然有时将其明确化（例如，作为更高级搜索策略的起点）可能有用，但您也可以使用：

dfs_start(Start, Goal, Path) :- phrase(dfs(Start, [], Goal), Path).

dfs(Node, _, Goal)   --> [Node], { call(Goal, Node) }.
dfs(Node0, Es, Goal) --> [Node0],
        { arc(Node0, Node1), \+ member(Node1, Es) },
        dfs(Node1, [Node0|Es], Goal).

示例查询：

?- dfs_start(a, goal, Path).
Path = [a, d, g] ;
false.
于 2011-03-12T23:40:32.120 回答