algorithm - 在没有 findall 和过滤器的情况下找到最佳结果

Question

我对 Prolog 有点困惑。

我有一个对象集合。这些物体具有一定的尺寸，因此具有重量。

我想将这些物体分成两组(它们一起构成了整个集合)，以使它们的总重量差异最小。

我首先尝试的是以下(伪代码):

-> findall with predicate createSets(List, set(A, B))
-> iterate over results while
---> calculate weight of both
---> calculate difference
---> loop with current difference and compare to current difference
       till end of list of sets

这很简单。这里的问题是我有一个包含 +/- 30 个对象的列表。创建所有可能的集合会导致堆栈溢出。

辅助谓词:

sublist([],[]).
sublist(X, [_ | RestY]) :-
  sublist(X,RestY).
sublist([Item|RestX], [Item|RestY]) :-
  sublist(RestX,RestY).

subtract([], _, []) :-
  !.
subtract([Head|Tail],ToSubstractList,Result) :-
  memberchk(Head,ToSubstractList),
  !,
  subtract(Tail, ToSubstractList, Result).
subtract([Head|Tail], ToSubstractList, [Head|ResultTail]) :-
  !,
  subtract(Tail,ToSubstractList,ResultTail).

generateAllPossibleSubsets(ListToSplit,sets(Sublist,SecondPart)) :-
  sublist(Sublist,ListToSplit),
  subtract(ListToSplit, Sublist, SecondPart).

然后可以按如下方式使用它们:

:- findall(Set, generateAllPossibleSubsets(ObjectList,Set), ListOfSets ),
   findMinimalDifference(ListOfSets,Set).

因为我认为这是一种错误的方法，所以我想我会以一种迭代的方式尝试它。这是我目前所拥有的:

totalWeightOfSet([],0).
totalWeightOfSet([Head|RestOfSet],Weight) :-
  objectWeight(Head,HeadWeight),
  totalWeightOfSet(RestOfSet, RestWeight),
  Weight is HeadWeight + RestWeight.

findBestBalancedSet(ListOfObjects,Sets) :-
  generateAllPossibleSubsets(ListOfObjects,sets(A,B)),
  totalWeightOfSet(A,WeightA),
  totalWeightOfSet(B,WeightB),
  Temp is WeightA - WeightB,
  abs(Temp, Difference),
  betterSets(ListOfObjects, Difference, Sets).

betterSets(ListOfObjects,OriginalDifference,sets(A,B)) :-
  generateAllPossibleSubsets(ListOfObjects,sets(A,B)),
  totalWeightOfSet(A,WeightA),
  totalWeightOfSet(B,WeightB),
  Temp is WeightA - WeightB,
  abs(Temp, Difference),
  OriginalDifference > Difference,
  !,
  betterSets(ListOfObjects, Difference, sets(A, B)).
betterSets(_,Difference,sets(A,B)) :-
  write_ln(Difference).

这里的问题是它返回了更好的结果，但它没有遍历整个解决方案树。我觉得这是我在这里缺少的默认 Prolog 方案。

所以基本上我想让它告诉我“这两组差异最小”。

编辑:

What are the pros and cons of using manual list iteration vs recursion through fail

这是一个可能的解决方案(通过失败递归)，除了它不能失败，因为它不会返回最佳集合。

Answer 1

我会生成 30 个对象列表，按权重降序排序，然后将对象从排序列表中一个一个弹出，并将每个对象放入两个集合中的一个或另一个中，这样我就可以得到两者之间的最小差异设置在每一步。每次我们将一个元素添加到集合中时，只需将它们的权重加在一起，以跟踪集合的权重。从两个空集开始，每个空集的总权重为 0。

它可能不是最好的分区，但可能接近它。

一个非常简单的实现:

pair(A,B,A-B).

near_balanced_partition(L,S1,S2):-
  maplist(weight,L,W),      %// user-supplied predicate weight(+E,?W).
  maplist(pair,W,L,WL),
  keysort(WL,SL),
  reverse(SL,SLR),
  partition(SLR,0,[],0,[],S1,S2).

partition([],_,A,_,B,A,B).
partition([N-E|R],N1,L1,N2,L2,S1,S2):-
   (    abs(N2-N1-N) < abs(N1-N2-N)
   ->   N3 is N1+N,
        partition(R,N3,[E|L1],N2,L2,S1,S2)
   ;    N3 is N2+N,
        partition(R,N1,L1,N3,[E|L2],S1,S2)
   ).

---

如果您坚持要找到精确的答案，则必须将列表的所有分区生成两个集合。然后在生成时，您将保留当前最好的。

剩下最重要的事情就是找到迭代生成它们的方法。

给定的对象要么包含在第一个子集中，要么包含在第二个子集中(您没有提到它们是否完全不同；让我们假设它们是不同的)。因此，我们有一个代表分区的 30 位数字。这允许我们独立地枚举它们，所以我们的状态是最小的。对于 30 个对象，将生成 2^30 ~= 10^9 个分区。

exact_partition(L,S1,S2):-
  maplist(weight,L,W),      %// user-supplied predicate weight(+E,?W). 
  maplist(pair,W,L,WL),
  keysort(WL,SL),           %// not necessary here except for the aesthetics 
  length(L,Len), length(Num,Len), maplist(=(0),Num),
  .....

您将必须执行二进制算法，在每一步将 Num 加 1，并根据新的 Num< 从 SL 生成两个子集，可能在一个融合操作中。对于每个新生成的子集，很容易计算它的权重(这个计算也可以融合到同一个生成操作中):

  maplist(pair,Ws,_,Subset1),
  sumlist(Ws,Weight1),
  .....

这个二进制数 Num 与不变的列表 SL 一起表示我们在搜索空间中的当前位置。因此搜索将是迭代的，即在恒定空间中运行。