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).

我的解释正确吗？

肿瘤坏死因子

4

1 回答 1

2

您的阅读似乎没问题，只是路径相反。使用 3 个参数谓词通常意味着在达到目标时反转路径。

为了执行 Else 部分，我认为您需要在goal(Node)成功后进行削减。否则，您将在 target 之后扩展路径 - 可能 - Node。\+ member如果这是唯一的，那么这样做几乎没有用处，因为它将被后续测试排除。

为了提高效率， call\+ memberchk而不是\+ member，因为memberchk不会留下选择点，并且（在 SWI-Prolog 中）在比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 回答