Сокращение в конце утверждения Пролога - PullRequest
Новая
       41

Сокращение в конце утверждения Пролога

0 голосов
/ 20 января 2019

Я столкнулся с этим разрезом, который должен возвращать true, если существует ребро A-B или B-A для некоторого узла B графа Graph. 

node(A,Graph) :- adjacent(A,_,Graph),!.

Проблема в том, что я не понимаю, почему удаление этого среза повлияет на возвращаемые решения.

Насколько я понимаю, единственное использование для сокращения в конце оператора Prolog - это когда есть другой оператор с таким же именем [другой узел (...)], который мы не делаем хочу позвонить, если первый удастся Примером может служить функция, которая принимает X и Y и возвращает большую в качестве третьего параметра. 

max1(X, Y, X) :- X > Y, !.
max1(_X, Y, Y).

Однако нет другого оператора, называемого node (...), поэтому я не вижу, как сокращение может повлиять на решения.

Это мой код. Это должно найти остовное дерево. Это подробно объясняется здесь . Компилятор SWI-Prolog 7.6.4 для Linux. 

:- op(900, fy, not).

stree1( Graph, Tree)  :-
    subset( Graph, Tree),  tree( Tree),  covers( Tree, Graph).

tree( Tree)  :-
    connected( Tree),  not hasacycle( Tree).

connected( Graph)  :-
    not ( node( A, Graph), node( B, Graph), not path( A, B, Graph, _) ).

hasacycle( Graph)  :-
     adjacent( Node1, Node2, Graph),
     path( Node1, Node2, Graph, [Node1, X, Y | _] ). 

covers( Tree, Graph)  :-
    not ( node( Node, Graph), not node( Node, Tree) ).

subset( [], [] ). 
subset( [X | Set], Subset)  :-  subset( Set, Subset).
subset( [X | Set], [X | Subset])  :-  subset( Set, Subset).

adjacent( Node1, Node2, Graph)  :-
      member( Node1-Node2, Graph)
      ;
      member( Node2-Node1, Graph).

node( Node, Graph)  :-  adjacent( Node, _, Graph). 

path( A, Z, Graph, Path)  :-
      path1( A, [Z], Graph, Path).

path1( A, [A | Path1], _, [A | Path1] ).

path1( A, [Y | Path1], Graph, Path)  :-
      adjacent( X, Y, Graph),
      not member( X, Path1), 
      path1( A, [X, Y | Path1], Graph, Path).

Решения возвращены без разреза (правильно) 

?- stree1([a-b, b-c, b-d, c-d], Tree).
Tree = [a-b, b-d, c-d] ;
Tree = [a-b, b-c, c-d] ;
Tree = [a-b, b-c, b-d] ;
false.

Решения, возвращенные с разрезом (неверно) 

?- stree1([a-b, b-c, b-d, c-d], Tree).
Tree = [a-b] ;
Tree = [a-b, c-d] ;
Tree = [a-b, b-d] ;
Tree = [a-b, b-d, c-d] ;
Tree = [a-b, b-c] ;
Tree = [a-b, b-c, c-d] ;
Tree = [a-b, b-c, b-d] ;
false.

1 Ответ

0 голосов
/ 20 января 2019

"Насколько я понимаю, единственное использование для сокращения в конце оператора Prolog - это когда есть другой оператор с таким же именем [другой узел (...)], который мы не хотим вызывать, если первый последует. "

Что ж, это не относится к вашему состоянию, так как вы используете предикат member/2, который будет работать с возвратом. В этой ситуации использование сокращений приведет к удалению дерева решений, которое Prolog использует при возврате, и может привести к изменению полученных результатов. Чтобы пояснить пример, см. Слегка измененный код вашего исходного поста здесь: 

node( Node, Graph , Target)  :-  adjacent( Node, Target, Graph),!.

adjacent( Node1, Node2, Graph)  :-
  member( Node1-Node2, Graph)
  ;
  member( Node2-Node1, Graph).

Когда вы выполните этот запрос в консоли, вы увидите вывод: 

?- node(l,[l-x,l-y],Target).
Target = x

Почему? Потому что в начале есть два листа вашего дерева поиска. Либо пара (l-x), либо (l-y) удовлетворяет условию adjacent/3. Затем, в соответствии с поиском по глубине, выбирается пара (l-x), и, поскольку в вашем коде есть оператор !, остальная часть дерева поиска теперь сокращается. Следовательно, вы получите результат как Target = x

Однако, если вы удалите оператор ! из кода, вы увидите: 

?- node(l,[l-x,l-y],Target).
Target = x ;
Target = y ;
false.

Здесь вы видите, что оба листа дерева поиска выполняются последовательно, согласно порядку глубины в первую очередь, и вы видите два результата. Это то, что заставляет вас видеть разные результаты, когда ! существует или нет.

...