圖形Prolog中

Question

我是新來的Prolog，我需要一些幫助：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). 

，這是計算由元素組成的列表XXX的

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

我的權重函數稱之爲

genera_ext([],L_tipi, Figlio) 

其中L_tipi是我可以選擇的元素xxx的列表。

我想生成元素xxx的所有可能的子列表長度爲3，並選擇最大的權重。

Answer 1

我想生成元素xxx的所有可能的子列表長度爲3，並選擇最大的權重。

這是一個經典的「生成和測試」問題。你可以解決這個問題的一種幼稚的方式，通過產生藝術的所有可能的排列，像這樣的東西：

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(_,_,_,_)-對我來說這似乎不太可能意思是「屬於任何四件事。」