프롤로그의 그래프

Question

프롤로그를 처음 사용하여 도움이 필요합니다. D

재귀를 배웠고 사용 방법을 알고 있습니다. 그래프에 문제가 있습니다. 나는 배낭 문제를 푸는 중이므로 한 걸음 씩하고 있습니다.

내 문제 : 유형 목록이 있으며 길이가 n 인 모든 하위 목록 (= 3)을 만들고 가장 큰 값을 가진 하위 목록을 만들고 싶습니다. 유형 목록의 머리를 빼내어 재귀 적으로 "아들"을 계산하는 다른 함수로 전달하는 함수가 필요하다고 생각합니다. 내 생각은 다음과 같습니다.

append([],L2,L2):- !. 
append([T|C],L2,[T|L3]):- 
    append(C,L2,L3). 

genera_ext(_,[],_). 

genera_ext(Padre,[TT|CT],Figlio):- 
    genera(Padre,TT,[TT|CT],Figlio), 
    genera_ext(Padre,CT,[]). 

genera(Padre,Elem,L_tipi,Figlio):- 
    append(Padre,[Elem],Base), 
    copy_term(Figlio,Base), 
    length(Base,Lun), 
    Lun =< 3, 
    genera_ext(Base,L_tipi,Temp), 
    total_ing(Temp,I_Temp), 
    total_ing(Base,I_Base), 
    I_Temp >= I_Base, 
    copy_term(Figlio,Temp), 
    nl,write("Figlio = "),write(Figlio). 

genera(_,_,_,_). 

분명히 잘못된 것이 있습니다. 당신이 나를 도울 수? 감사 :( MR

편집 :

내가 가진 몇 가지 사실

art(xxx,weight_xxx). 

이것은

total_ing([],0). 
total_ing([X|C],I0):- 
    art(X,N), 
    total_ing(C,I1), 
    I0 is I1 + N. 

I을 xxx는 요소로리스트의 무게를 계산하는 기능입니다 그것을

genera_ext([],L_tipi, Figlio) 

여기서 L_tipi는 선택할 수있는 요소 xxx의 목록입니다.

길이가 3 인 요소 xxx의 가능한 모든 하위 목록을 생성하고 가장 큰 가중치를 갖는 것을 선택하고 싶습니다.

Answer 1

나는 길이가 3 인 요소 xxx의 가능한 모든 하위 목록을 생성하고 가장 큰 가중치를 가진 것을 선택하고 싶습니다.

이것은 고전적인 "생성 및 테스트"질문입니다. 그리고이 같은과, 예술의 모든 가능한 순열을 생성하여, 순진 방법의 종류를 해결할 수 :이 비효율적 호출

inefficient([A1,A2,A3], Sum) :- 
    art(A1, X), 
    art(A2, Y), A2 \= A1, 
    art(A3, Z), A3 \= A2, A3 \= A1, 
    Sum is X+Y+Z. 

inefficient_best(L, Sum) :- 
    inefficient(L, Sum), 
    \+ (inefficient(L2, Sum2), L2 \= L, Sum2 > Sum). 

은 매우 친절; 그것은 정말로 다른 모든 순열에 대해 모든 순열을 여러 번 시도하고 있으며, 순열이 동일한 동일한 여러 솔루션을 생성합니다. 그러나 그것은 "일한다".

다음으로 고려해야 할 점은 더 효율적으로 만드는 방법입니다. 테스트를 더 빨리 수행하기위한 뚜렷한 일은 아니지만 생성 단계는 분명히 많은 수의 조합을 만들어냅니다. 우리가 할 수있는 첫 번째 작업은 findall/3을 사용하여 데이터베이스를 목록으로 구체화 한 다음 permutation/2을 사용하여 시도 할 순열을 생성하는 것입니다. 그러나 이것은 나쁘다고 생각합니다. 나는 최선의 방법은 특정 길이의 조합을 생성하기위한 술어를 만드는 것이라고 생각하기 시작했다.나는이 내장 된 술어를 사용하여이 작업을 수행 할 수있는 더 좋은 방법이 생각하지 못했습니다 (어쩌면이 난 그냥 영리 충분히되지 않는 해요)하지만이 함께했다 :

combination(0, _, []) :- !. 
combination(N, [X|Xs], [X|Ys]) :- 
    succ(N0, N), 
    combination(N0, Xs, Ys). 
combination(N, [_|Xs], Ys) :- 
    combination(N, Xs, Ys). 

이는 결과를 같은 :이 작품

?- combination(3, [a,b,c,d,e], X). 
X = [a, b, c] ; 
X = [a, b, d] ; 
X = [a, b, e] ; 
X = [a, c, d] ; 
X = [a, c, e] ; 
X = [a, d, e] ; 
X = [b, c, d] ; 
X = [b, c, e] ; 
X = [b, d, e] ; 
X = [c, d, e] ; 
false. 

방법은 목록에서 현재 항목을 하나에 의해 우리는 여전히 필요 길이를 줄이거 나 현재 항목을 복용하지 않고 재발하는 중 기본적으로. member/2과 매우 흡사합니다.

이제 데이터베이스를 구체화하고 모든 순열을 시도해 볼 필요가 없습니다. 사실 우리는 당신이 하나 개의 결과를 원하는 가정, 승자를 찾기 위해 sort/2를 사용할 수 있지만, 우리는 먼저 도우미 기능이 필요합니다 :

art_cost(ArtList, Cost-ArtList) :- 
    maplist(art, ArtList, CostList), 
    sumlist(CostList, Cost). 

art_cost/2 예술의 목록의 총 비용을 계산을하지만, 한 쌍을 반환 : 실제 예술 작품 비용. 이런 종류의 일이 몹시 드문 일이 아니다, 우리는 높은 비용을 찾기 위해 우리의 조건에 대한 다음 단계에 의존 :

best(ArtList, Cost) :- 
    % materialize the list of all artworks 
    findall(A, art(A,_), Art), 

    % materialize the list of candidate combinations 
    findall(Candidate, combination(3, Art, Candidate), Candidates), 

    % compute the cost+list for all the candidate lists 
    maplist(art_cost, Candidates, CostsWithArtLists), 

    % sort the list, which will put them in order of cost 
    % but lowest-to-highest 
    sort(CostsWithArtLists, CostsLowToHigh), 

    % flip the list around and deconstruct the highest 
    % as our result 
    reverse(CostsLowToHigh, [Cost-ArtList|_]). 

이 library(aggregate)이 작업을 수행 할 수있는보다 효율적인 방법은 아마도,하지만 난 년후 그것을 이해할 수는 없다.

제쳐두고 코드에서 copy_term/2이 필요하지 않다고 생각합니다. 익명의 변수처럼 보이는 용어를 볼 때 항상 의심 스럽습니다. genera(_,_,_,_) - 내게는 "어떤 4 가지에 대한 속 (gena)"을 의미합니다.