Как найти путь от корня к листу, равный сумме (проблема пути) в Прологе? - PullRequest
Новая
       29

Как найти путь от корня к листу, равный сумме (проблема пути) в Прологе?

1 голос
/ 04 апреля 2019

Конкретная проблема: написать предикат
sum(T,S) означает, что дерево T имеет путь от корня к листу с суммой S.

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

sum(T,S) :- mySum(T,S).

mySum([], S) :- S is 0.

mySum([H|T], S) :-
    nth0(X, H, Elem), 
    S1 is S-Elem,
    mySum(T, S1).

sum([1,2,3],3). is supposed to return yes/true.
sum([1,2,3] 4). is supposed to return yes/true.
sum([1,2,3] 6). is supposed to return no/false.

1 Ответ

1 голос
/ 04 апреля 2019

Как отметил @ User9213, вы не указали ни одного дерева, но список.

На основании ваших примеров дерево 

   1
  / \
 2   3

что будет t(1,2,3) с t(Root,Left,Right)

Обычно вы видите обход дерева, который выполняет как левый, так и правый в одном и том же предикате, но для этого вам нужно сделать либо левый, либо правый, чтобы можно было использовать два предиката, или можно использовать ; , Этот ответ использует два предиката вместо ;. Также для этого нужен базовый случай, чтобы перестать обходить дерево, когда найден листовой узел. 

% Traverse left branch of tree
sum(t(Root,Left,_Right),[left|Path0],Sum) :-
    sum(Left,Path0,Left_sum),
    Sum is Root + Left_sum.

% Traverse right branch of tree
sum(t(Root,_Left,Right),[right|Path0],Sum) :-
    sum(Right,Path0,Right_sum),
    Sum is Root + Right_sum.

% Base case to stop traversing the tree
sum(N,[],N) :-
    N \= t(_Root,_Left,_Right).

Приведенный выше код также включает путь, используемый для получения результата. Даже если это не было запрошено, это хорошо, когда дерево проходит несколько уровней.

Пример с путями. 

?- sum(t(1,2,3),Path,Sum).
Path = [left],
Sum = 3 ;
Path = [right],
Sum = 4 ;
false.

Добавлен предикат для решения вашей конкретной проблемы. 

sum_1(T,V) :-
    sum(T,_Path,V).

Пример выполнения: 

?- sum_1(t(1,2,3),3).
true ;
false.

?- sum_1(t(1,2,3),4).
true ;
false.

?- sum_1(t(1,2,3),6).
false.

false после true связаны с возвратом, но являются правильными результатами.

...