프롤로그 프로그램에서 잘못된 하위 트리가 생성됩니까?

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. 

그것의 결과가 L = 15,10,12,9,10이다

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

콘솔이기의 생성이다 ], N = 56; 일 때, L = [12,9,10], N = 31;

Answer 1

귀하의 솔루션은 [15,10,12,9,10] = L를 반환 그것은 최대의 독립적 인 세트를 발견하기 때문에, 하위 트리를 반환하도록 강요되지 않습니다. 당신은 아래의 코드와 같은 일부 변경 될 수 있습니다 :

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

아이디어는 당신이 하위 트리를 찾기 위해 루트를 건너 뛸 수 있습니다 또는 당신이이 경우에 당신이 루트를 건너 뛸 수 있습니다 루트를 유지할 수 있다는 것입니다 주소이기 때문에 그것은하지 않습니다 하위 트리.