在 Prolog 程序中，生成假子树？

Question

我正在学习一门课程的序言。作为练习，我需要部分地生成给定树的所有子树。问题是它会生成错误的子树

这是代码

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).

结果是大号 = [15,10,12,9,10] , N = 56 ; 当它应该是大号 = [12,9,10] , N = 31;

Answer 1

你的解决方案returns L=[15,10,12,9,10]因为它找到了最大独立集，所以它没有被强制return一个子树。您可以更改部分代码如下：

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))).

想法是您可以跳过根来查找子树，或者您可以保留根，在这种情况下您可以跳过根，因为那样它就不是子树了。

在 Prolog 程序中，生成假子树？

In Prolog program, generating false sub trees?

tree

prolog

subtree