1

我必须修改以下 Prolog 程序，该程序在图上实现迭代深化 dfs 搜索：

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

goal(d).

/* Solution is the inverse list of the visited node 
           from the start node Node and a goal node
           if it is TRUE that:

   path/3 predicate is TRUE (Solution is the inverse list 
           from the start node Node and a GoalNode)
           and it is TRUE that GoalNode is a goal 
*/
depth_first_iterative_deepening(Node, Solution) :- 
    path(Node, GoalNode, Solution),
    goal(GoalNode).

/* Path/3 predicate generate, for the given initial node, 
           all the possibles acyclic paths of increasing
           length
*/

/* BASE CASE: The shorter path from a node X to itself is Path=[X] */
path(Node, Node, [Node]).

/* GENERAL CASE: If I have to go from a start node X 
           to an end node Y and X != Y
   [LastNode|Path] is the path from FirstNode and LastNode 
           if it is TRUE that:

   1) Path is the path from FirstNode and OneButLast node
   2) Exist an edge from OneButLast and LastNode
   3) I have yet never visited LastNode
*/
path(FirstNode, LastNode, [LastNode|Path]) :- 
    path(FirstNode, OneButLast, Path),
    s(OneButLast, LastNode),
    not(member(LastNode, Path)).

对于给定的初始节点，path/3谓词生成所有可能的长度增加的非循环路径，因此使用depth_first_iterative_deepening/2谓词生成从开始节点到按长度排序的结束节点的所有解（从最短的到最长的）。

好的，所以我必须以对解决方案的长度施加限制的方式修改这个程序

我必须有这样的depth_first_iterative_deepening2/3谓词：

depth_first_iterative_deepening2(Node, Max, Solution)

其中Max是访问节点的最大数量，因此这Solution是可以接受的。

如果长度较小或等于值，则从起始节点到目标节点Solution的解决方案路径也是如此。NodeSolutionMax

我曾尝试在上一个谓词中进行此更改，但它存在一些问题并且效果不佳：

depth_first_iterative_deepening2(Node, Max, Solution) :- 
    path2(Node, GoalNode, Solution),
    goal(GoalNode),
    length(Solution, Length),
    write(Length),
    (Length =< Max).

当它计算一个带入目标节点的Solution（使用谓词）时，您如何看到，我将这个解决方案的长度放入 Length 变量中，并且我强制这个解决方案的长度必须小于或等于多变的path2/3Max

问题是，如果找到的解决方案是好的（它的长度是<=值Max）它工作得很好但是如果解决方案发现它不是好​​的（有长度>然后是Max值）就会出错：

[debug]  ?- depth_first_iterative_deepening2(a,1,Solution).
24
ERROR: Out of local stack
   Exception: (1,597,352) path2(a, _G4793274, _G4792038) ?

查看跟踪似乎问题在于，当(Length =< Max)失败时它再次调用path2/3谓词以找到另一个解决方案（它是相同的，因为path2/3 总是找到到第一个调用的最短路径，所以它会找到相同的解决方案，从而引入失败）

我希望如果(Length =< Max)检查失败，那么depth_first_iterative_deepening2/3必须失败

我可以使用切割来做到这一点吗？如果是这样，怎么做？

4

2 回答 2

4

你可以试试

( (Length =< Max) ; (Length > Max), !, fail).

代替

(Length =< Max).
于 2013-05-13T14:30:08.730 回答
0

这与我前段时间提出的“技巧”相同。

在调用访问之前放置测试：

depth_first_iterative_deepening2(Node, Max, Solution) :-
   length(Solution, Length),
   Length =< Max,
   path2(Node, GoalNode, Solution),
   goal(GoalNode).
于 2013-05-13T12:18:11.083 回答