首页 文章

Prolog：编写代码来操作图形，以便在目标节点深度为3时找到深度为2的解决方案

提问于
浏览 次
0

我正在尝试编写深度有限的代码，它将操纵图形here并找到深度为2的解决方案节点G.我也试图让代码返回解决方案路径的成本 .

到目前为止我已经得到了这个：

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

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

depthfirst( Path, Node, Sol)  :-
  s( Node, Node1, Cost),
  \+ 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(g).
s(a,b,4).
s(a,c,5).
s(b,d,4).
s(b,e,2).
s(d,e,2).
s(d,g,1).
s(e,g,3).
s(c,e,5).
s(c,f,4).
s(f,g,7).

我知道这将执行我的标准深度优先搜索，但是，我不知道如何操作它来找到深度为2的解决方案 . 我甚至不确定我的代码是否部分正确或是否代码只是完整的意大利面条 .

任何帮助都会很棒，谢谢 .

search graph prolog artificial-intelligence depth-first-search

1 回答

  • 1

    节点 g 如何"solution at a depth of 2"？您感兴趣的查询是什么，以及如何定义深度？

    如果我将"depth"作为解决方案列表的长度（也许你的意思是这个长度 - 1）并开始在节点 a 搜索，那么你的代码会正确枚举所有解决方案：

    ?- solve(a, Solution).
Solution = [g, e, d, b, a] ;
Solution = [g, d, b, a] ;
Solution = [g, e, b, a] ;
Solution = [g, e, c, a] ;
Solution = [g, f, c, a] ;
false.

    您可以通过将路径长度增加到某个限制来进行搜索，如下所示：

    ?- between(0, 10, N), length(Solution, N), solve(a, Solution).
N = 4,
Solution = [g, d, b, a] ;
N = 4,
Solution = [g, e, b, a] ;
N = 4,
Solution = [g, e, c, a] ;
N = 4,
Solution = [g, f, c, a] ;
N = 5,
Solution = [g, e, d, b, a] ;
false.

    但是没有长度为2的解决方案 .

    回复于

相关问题