寻找最大最小值集 [英] Finding maximal minimum value set

问题描述

我正在尝试编写一个(天真的或半天真的)程序，该程序给定一组元素，并将其划分为该玩家数量，并且对于每个这样的划分，取最小值(按总和)) 子集.然后，我想计算所有这些最小划分的最大值.

I'm attempting to write a (naive, or semi-naive) program that given a set of elements and a number of players divides it to this number of players, and for each such division takes the minimal value (by sum) subset. Then, I want to calculate the maximum of all these minimal divisions.

这被称为 https://en.wikipedia.org/wiki/Maximin_share .

例如，如果我们查看集合 {1,4,6}，我们可以将其划分为 2 个玩家，使得一个接收 {1,4}，另一个接收 {6}，这里的最小值是 5.对于所有其他划分，很容易看出最小值将小于 5.

For example, if we look at the set {1,4,6} we can divide it for 2 players such that one receives {1,4} and the other {6}, the minimalk value here is 5. For all other divisions, it is easy to see that the minimal value will be less than 5.

我想写一个序言谓词 maximin(+Elements,+Players,-Value) 给出一个 Elements(正整数)列表和一些 Players 返回最大值 Value.

I want to write a prolog predicate maximin(+Elements,+Players,-Value) that given a list of Elements (positive integers) and a number of Players returns the maximin Value.

我尝试了一种非常幼稚的方法:

I tried a very naive approach:

1. 编写了一个计算特定除法的谓词.
2. 使用find all来查找所有的部门.
3. 对于每个分区返回最小子集的值.
4. 计算其中的最大值.

但是，此程序仅针对小输入运行.例如，如果我使用 10 个元素列表 Elements 并尝试将其划分为 3 个玩家，即使我尝试增加尽可能使用 set_prolog_stack 来编程内存.

However, this program runs only for small inputs. For example, if I take a 10 elements list Elements and attempt to divide it to 3 players, I get an error of out of stack, even though I tried to increase the program memory as best as I could with set_prolog_stack.

我的代码:

% returns the smaller item
mini(A,B,B):- A > B.
mini(A,B,A):- A =< B.

% Returns the Sum of the minimal subset in a division (+,-)
min_subset_value([P1],Sum1):-subset_value(P1,Sum1).
min_subset_value([P1|RestP],Min) :-  RestP \= [], min_subset_value(RestP, OtherMin), subset_value(P1,A1)
                                     , mini(A1, OtherMin, Min).


% divide_to_players(+,+,-) : Generate a division of all the Elements to N subsets
divide_to_players([],N,EmptySets):- N>=1, generate_empty_sets(EmptySets,N).
divide_to_players(Elements, 1, [Elements]):-Elements \= [].
divide_to_players(Elements, N, [P1|RestP]):- N>1, Elements \= [], subseti(P1,Elements)
                                             , remove_subset(Elements,P1,OtherElements)
                                             , N1 is N-1
                                             , divide_to_players(OtherElements, N1, RestP).
% Generates all divisions (+,+,-)
generate_all_divisions(Elements,N,AllDivs) :- findall(Div,divide_to_players(Elements,N,Div),AllDivs).

% From all the given divisions, which one has the maximal minimal subset
find_max_division([],0).
find_max_division([Set1|RestSets],Max) :- find_max_division(RestSets, OtherMin)
                                         , min_subset_value(Set1,LocalMin)
                                         , maxi(LocalMin, OtherMin, Max).

% uses the previous functions as described above (+,+,-)
maximin_player(Elements,N,Maximin) :- generate_all_divisions(Elements,N,AllDiv)
                                     , find_max_division(AllDiv,Maximin).

但是，我在徘徊，如果有其他方法可以继续下去吗?也许不用 findall 就能找到最大值?我只使用了 findall，因为我没有更好的方法想法，所以我很高兴听到其他想法或方法来解决这个问题.

However, I am wandering if there is another way to go on it? Maybe finding the maximin value without using findall? I only used findall because I did not have any better idea for an approach, so I'd appreciate to hear other ideas or approaches to this problem.

推荐答案

如果元素都是整数(即没有变量也没有浮点值)，我相信这可以正常工作:

If the elements are all integers (i.e. no variables and no floating point values) I believe this works fine:

maximin(Elements, N, Maximin, LDistribution):-
  sumlist(Elements, Sum),
  TargetMaximin is -Sum//N,
  once(
  (
    between(TargetMaximin, -1, NMaximin),
    Maximin is -NMaximin,
    distribute(Elements, [], n, Maximin, N, 0, [], LDistributionOnce)
  )),
  LDistribution=LDistributionOnce.
  
distribute([], [], _, _, 0, _, _, []).
distribute(Elements, Skipped, y, Maximin, N, Cur, Distribution, [Distribution|LDistribution]):-
  N>0,
  Cur >= Maximin,
  succ(N1, N),
  append(Elements, Skipped, NElements),
  distribute(NElements, [], n, Maximin, N1, 0, [], LDistribution).
distribute([Element|Elements], Skipped, _, Maximin, N, Cur, Distribution, LDistribution):-
  N>0,
  NCur is Cur+Element,
  distribute(Elements, Skipped, y, Maximin, N, NCur, [Element|Distribution], LDistribution).
distribute([Element|Elements], Skipped, _, Maximin, N, Cur, Distribution, LDistribution):-
  N>0,
  distribute(Elements, [Element|Skipped], n, Maximin, N, Cur, Distribution, LDistribution).

该算法的思想是从最大目标最小值(元素总和除以玩家人数的整数除法)开始，并尝试将元素放在 N 个槽中，其中每个槽的总和至少为目标最小值.如果你找到这样的分布，那么你就完成了，否则将目标最小值减 1 并重复.

The idea of the algorithm is to start with the maximum target mininum value (the integer division of the sum of the elements divided by the number of players) and try to fit the elements in N slots where each slot sums at least the target minimum. If you find such distribution then you are done, otherwise decrement the target minimum value by 1 and repeat.

这里的算法也给出了它找到的唯一一个分布.

The algorithm here also gives the only one distribution it finds.

样品运行:

?- maximin([11,17,19],3,Maximin, LDist).
Maximin = 11,
LDist = [[11], [17], [19]].

?- maximin([5,7,1,3,3,7,4,3,8,2,5,1],3,Maximin, LDist).
Maximin = 16,
LDist = [[3, 1, 7, 5], [3, 4, 7, 3], [1, 5, 2, 8]].

这篇关于寻找最大最小值集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！