8

これで私を助けてくれることを願っています。

Prolog で深さ優先検索アルゴリズムについて学習しようとしていますが、次のコードに出くわしました

go(Start, Goal) :-
   empty_stack(Empty_been_list),
   stack(Start, Empty_been_list, Been_list),
   path(Start, Goal, Been_list).

% path implements a depth first search in PROLOG

% Current state = goal, print out been list
path(Goal, Goal, Been_list) :-
    reverse_print_stack(Been_list).

path(State, Goal, Been_list) :-
    mov(State, Next),
    % not(unsafe(Next)),
    not(member_stack(Next, Been_list)),
    stack(Next, Been_list, New_been_list),
    path(Next, Goal, New_been_list), !.

reverse_print_stack(S) :-
    empty_stack(S).
reverse_print_stack(S) :-
    stack(E, Rest, S),
    reverse_print_stack(Rest),
    write(E), nl.

何が起こっているのかはある程度理解できますが、それで使用できるいくつかの事実を見つけたり発明したりすることは一生できません.

助けてください。たとえそれが本当に単純な事実のセットであっても、どこかで始める必要があるだけです

前もって感謝します

4

2 に答える 2

3

以下は、プロローグ コードで使用される DFS の例です。

% solve( Node, Solution):
%    Solution is an acyclic path (in reverse order) between Node and a goal

solve( Node, Solution)  :-
  depthfirst( [], Node, Solution).

% depthfirst( Path, Node, Solution):
%   extending the path [Node | Path] to a goal gives Solution

depthfirst( Path, Node, [Node | Path] )  :-
   goal( Node).

depthfirst( Path, Node, Sol)  :-
  s( Node, Node1),
  \+ member( Node1, Path),                % Prevent a cycle
  depthfirst( [Node | Path], Node1, Sol).

depthfirst2( Node, [Node], _)  :-
   goal( Node).

depthfirst2( Node, [Node | Sol], Maxdepth)  :-
   Maxdepth > 0,
   s( Node, Node1),
   Max1 is Maxdepth - 1,
   depthfirst2( Node1, Sol, Max1).


goal(f).
goal(j).
s(a,b).
s(a,c).
s(b,d).
s(b,e).
s(c,f).
s(c,g).
s(d,h).
s(e,i).
s(e,j).

このコードをテストするには、Swish SWI プロローグに移動し、これをターミナルに貼り付けます。

次に、コードを照会し、右側に次のように入力します: solve(a, Sol)

解は次のようになります: Sol = [j, e, b, a]

trace, (solve(a, Sol)) と入力して、このコードをデバッグできます。

以下は、プロローグ コードで使用される BFS の例です。

前と同じ手順を使用して、スウィッシュしてクエリを実行します

解は次のようになります: Sol = [f, c, a]

% solve( Start, Solution):
%    Solution is a path (in reverse order) from Start to a goal

solve( Start, Solution)  :-
  breadthfirst( [ [Start] ], Solution).

% breadthfirst( [ Path1, Path2, ...], Solution):
%   Solution is an extension to a goal of one of paths

breadthfirst( [ [Node | Path] | _], [Node | Path])  :-
  goal( Node).

breadthfirst( [Path | Paths], Solution)  :-
  extend( Path, NewPaths),
  append( Paths, NewPaths, Paths1),
  breadthfirst( Paths1, Solution).

extend( [Node | Path], NewPaths)  :-
  bagof( [NewNode, Node | Path],
         ( s( Node, NewNode), \+ member( NewNode, [Node | Path] ) ),
         NewPaths),
  !.

extend( Path, [] ).              % bagof failed: Node has no successor
s(a,b).
s(a,c).
s(b,d).
s(b,e).
s(c,f).
s(c,g).
s(d,h).
s(e,i).
s(e,j).
goal(j).
goal(f).

これが DFS と BFS の理解に役立つことを願っています

この図を使用して、ツリーを理解してください。

ここに画像の説明を入力

于 2018-02-25T19:46:30.017 に答える
0

グラフで有効な動きを説明する事実を作成するだけです。

たとえば、ノード A、B、C、および D がある場合、グラフのすべてのエッジに mov() ファクトがあります。A が B および C に対してエッジを持ち、B が D に対してエッジを持っている場合、事実は次のようになります。

mov(A, B).
mov(A, C).
mov(B, D).

基本的には、あるノードから別のノードへのパスごとにグラフを描いて上記のような事実を書きます。

于 2014-11-28T17:39:25.623 に答える