prolog - 寻找最大最小值集
问题描述
我正在尝试编写一个(幼稚或半幼稚)程序,该程序给定一组元素,并且将许多玩家划分为这个玩家数量,并且对于每个这样的划分都取最小值(按总和)子集。然后,我想计算所有这些最小除法的最大值。
这被称为https://en.wikipedia.org/wiki/Maximin_share。
例如,如果我们查看集合 {1,4,6},我们可以将它划分为 2 个玩家,一个接收 {1,4},另一个接收 {6},这里的最小值是 5。对于所有其他划分,很容易看出最小值会小于 5。
我想写一个序言谓词maximin(+Elements,+Players,-Value)
,给出一个Elements
(正整数)列表和一个Players
返回 maximin的数量Value
。
我尝试了一种非常天真的方法:
- 写了一个计算某个除法的谓词。
- 用于
find all
查找所有部门。 - 对于每个除法返回最小子集的值。
- 计算它们的最大值。
但是,该程序仅针对少量输入运行。例如,如果我使用 10 个元素的列表Elements
并尝试将其划分给3
玩家,我会收到 out of stack 的错误,即使我尝试尽可能地增加程序内存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
因为我没有更好的方法来使用,所以我很高兴听到其他想法或方法来解决这个问题。
解决方案
如果元素都是整数(即没有变量也没有浮点值),我相信这可以正常工作:
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 并重复。
这里的算法也给出了它找到的唯一一个分布。
样品运行:
?- 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]].
推荐阅读
- python - 如何从 python 中的列表中计算数学问题?
- android - 从 strings.xml 转移到 MainActivity.xml 时不起作用
- vue.js - 如何在 Element UI 中使用 Font Awesome 5 图标
- excel - 如何在引用 ListBox 选项时执行 DataSeries 填充?
- java - 如何在 Eclipse 的主(顶部)菜单中添加菜单?
- wordpress - Wordpress 更改向左移动侧边栏
- c# - C# 方法更改“图片框”
- sprite-kit - 测量 SKShapeNotes 之间的碰撞
- python - 更改为 PostgreSQL raise django.db.utils.OperationalError: no such table 错误
- javascript - 不能在 map() 内使用 if