0

私はDFSアルゴリズムを研究していますループを回避するDFSアルゴリズムバージョン、これはコードです 

/* It is TRUE that Solution is the path from the start node Node to a goal state node
   if it is TRUE the depthfirst2/3 predicate where:
   []: it is the of nodes that was already visited (at the beginning is empty)
   Node: is the current node that I am visiting
   Solution: is the path (without cycles) from the start node to the current node Node 
*/
solve2(Node, Solution) :- depthfirst2([], Node, Solution).

/* BASE CASE: [Node|Path] is the Solution path fro the start node to a GOAL node if it
              is TRUE that Path is the list of visited node until reach Node and Node
              is a GOAL state
*/
depthfirst2(Path, Node, [Node|Path]) :- goal(Node).


/* RULE: Else (if Node this is not a GOAL state) and Path is the list of visited node and
         Sol is the path from the start node to the current node Node it is TRUE if it is
         True that:
         Node1 is the successor of Node
         I have not already visited Node1 (Node1 is not in the visited node list)
         Add Node to the list of visited node and execute depthfirst2 searching the path
         to Node1
*/
depthfirst2(Path, Node, Sol) :- s(Node, Node1),             
                            not(member(Node1, Path)),       
                            depthfirst2([Node|Path], Node1, Sol).

私の解釈は正しいですか？

TNX

4

1 に答える 1

2

パスが逆になっていることを除いて、あなたの読みは問題ないようです。3 つの引数の述語を使用することは、通常、目標到達時にパスを逆にすることを意味します。

goal(Node)Else 部分を強制するには、成功後にカットが必要だと思います。それ以外の場合は、おそらくターゲットの後にパスを拡張していますNode。\+ memberこれが一意である場合、後続のテストで除外されるため、実行してもほとんど役に立ちません。

memberchkは選択ポイントを残さず、(SWI-Prolog では) memberよりも低いレベルで効率的に実装されるため、効率のため\+ memberchkに の代わりに呼び出します。\+ member

この基本データで:

s(a, b).
s(b, c).
s(c, d).
s(a, d).
goal(d).

後のカットの違いを見ることができますgoal(Node)：

それなし

?- solve2(a, P).
P = [d, c, b, a] ;
P = [d, a] ;
false.

カットあり

?- solve2(a, P).
P = [d, c, b, a] ;
P = [d, a].
于 2013-05-10T10:21:44.160 に答える