迭代與最大深度約束深化的Prolog

我已修改以下Prolog程序實現迭代加深DFS在圖上進行搜索：迭代與最大深度約束深化的Prolog

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所以是從起始節點到Node一個目標節點中的溶液路徑，如果Solution長度是輕微或等於Max值。

我試圖做在前面的斷言這種變化，但它有一些問題，不正常工作：

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

如何你可以看到，當它計算Solution（使用path2/3謂語），我把這個解決方案的長度和這個解決方案的長度放到長度變量中，我強加了這個解決方案的長度必須小於或等於變量的值Max

的問題是，如果找到了解決辦法是確定的（其長度爲<=的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有失敗

我可以使用切做到這一點？如果是這樣，怎麼樣？

來源

2013-05-13 AndreaNobili

你可以嘗試

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

，而不是

(Length =< Max).

來源

2013-05-13 14:30:08

It wo rk ...現在很明顯：如果找到了有效的解決方案或者找不到它，那麼最終會失敗並退出程序！ – AndreaNobili 2013-05-13 14:34:53

@AndreaNobili是;當length = 2013-05-13 14:35:52

這就是我前段時間提出的同一個「訣竅」。

廣場前的測試調用訪問：

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

來源

2013-05-13 12:18:11 CapelliC

我已經tryed之前問在這裏，但仍不工作：光標閃爍並且沒有得出結論false – AndreaNobili 2013-05-13 12:32:07

迭代與最大深度約束深化的Prolog

回答

相關問題