В программе Prolog, генерирующей ложные под деревья?

Question

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

Вот код

build_tree3(T):- 
T=t(t(t(nil, -5, nil), 4, t(t(nil, 15, nil), -20, t(nil, 10, nil))), 2, t(nil, -8, t(t(nil, 9, nil),12,t(nil, 10, nil)))). 

get_sol(Tree, List, N):- 
without_root(Tree, List1, N1), 
with_root(Tree, List2, N2),!, 
max_set(List1, N1, List2, N2, List, N). 

max_set(List1, N1, List2, N2, List, N) :- 
    (N1>N2,List=List1,N=N1; 
    N2>N1,List=List2,N=N2; 
    N2=:=N1,N=N1,(List=List1;List=List2)). 

without_root(nil, _, 0). 
without_root(t(L, _, R), List, N):- 
    get_sol(L, LeftList, LeftN), 
    get_sol(R, RightList, RightN), 
    append(LeftList, RightList, List), 
    N is LeftN + RightN. 


with_root(nil, [], 0). 
with_root(t(L, X, R), [X|List], N):- 
    with_root(L, LeftList, LeftN), 
    with_root(R, RightList, RightN), 
    append(LeftList, RightList, List), 
    N is LeftN + RightN + X. 

Вот консоль

build_tree3(T), get_sol(T, L, N). 

Результатом этого является L = [15,10,12,9,10 ], N = 56; , когда он должен быть L = [12,9,10], N = 31;

Answer 1

Ваше решение возвращает L = [15,10,12,9,10], потому что он находит максимальное независимое множество, он не обязан возвращать поддерево. Вы можете изменить некоторые части, как код ниже:

sol_tree(Tree,List,N):- 
    sol_tree_noroot(Tree,L1,N1), 
    sol_tree_withroot(Tree,L2,N2),!, 
    max_set(L1,N1,L2,N2,List,N). 

max_set(List1, N1, List2, N2, List, N) :- 
    (N1>N2,List=List1,N=N1; 
    N2>N1,List=List2,N=N2; 
    N2=:=N1,N=N1,(List=List1;List=List2)).  

sol_tree_noroot(nil,[],0). 
sol_tree_noroot(t(L,_,R),List,N):- 
     sol_tree(L,L1,N1),sol_tree(R,R1,N2),!, 
     max_set(L1, N1, R1, N2, List, N). 

sol_tree_withroot(nil,[],0). 
sol_tree_withroot(t(L,X,R),[X|List],N3):- 
    sol_tree_withroot(L,L1,N1),sol_tree_withroot(R,R1,N2), 
    max_set2(L1,N1,R1,N2,List,N), 
    N3 is N+X. 

max_set2(L1,N1,L2,N2,List,N):- 
    (N1>0,N2>0,N is N1+N2,append(L1,L2,List); 
    N1>=0,N2<0,N is N1 ,List=L1; 
    N1<0,N2>=0,N is N2 ,List=L2; 
    N1<0,N2<0,N1<N2,N is N2 ,List=L2; 
    N1<0,N2<0,N1>N2,N is N1 ,List=L1; 
    N1>0,N2=0,N is N1,(List=L1;append(L1,L2,List)); 
    N1=0,N2>0,N is N2,(List=L2;append(L1,L2,List)); 
    N1=0,N2=0,N is N1,(List=L1;List=L2;append(L1,L2,List))). 

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