Итеративное углубление с максимальной глубиной ограничением на Прологе

Question

я изменить следующую программу 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 должны потерпеть неудачу

Могу ли я использовать разрез, чтобы сделать это? Если да, то как?

Answer 1

вы можете попробовать

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

вместо

(Length =< Max). 

Answer 2

Это тот же «трюк», который я предложил некоторое время назад.

Поместите тест перед тем вызвать визит:

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