图形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(_,_,_,_)-对我来说这似乎不太可能意思是“属于任何四件事。”