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 で説明されているアルゴリズムを使用しています。パス全体を作成する方法がわかりません。ここで何かが欠けています。私にとって、ラッセル・ノーヴィグはそれについて本当に不可解です。

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 に答える