ken*_*der 37 language-agnostic algorithm graph
这是一种更通用的问题,不是特定于语言的.更多关于使用的想法和算法.
系统如下:
它在朋友群之间登记小额贷款.Alice并且Bill要去吃午饭,比尔的卡不工作,所以爱丽丝支付他的餐费,10美元.
第二天Bill,Charles在火车站相遇,Chales没有钱买票,所以Bill买了一个,5美元.那天晚些时候从她和朋友那里Alice借了5美元Charles和1美元Bill购买礼物.
现在,假设他们都在系统中注册了这些事务,它看起来像这样:
Alice -> Bill $10
Bill -> Alice $1
Bill -> Charles $5
Charles -> Alice $5
所以,现在,唯一需要做的就是Bill给Alice4美元(他给了她1美元并将他的5 美元Charlie 转移到Alicealredy)并且他们处于初始状态.
如果我们将这个扩展到许多不同的人,拥有多个事务,那么获得尽可能少的事务的最佳算法是什么？
pax*_*blo 25
这实际上看起来像双重会计会计概念可以帮助的工作.
您的交易可以构建为簿记条目,因此:
Alice Bill Charles Balance
Alice -> Bill $10 10 10- 0 0
Bill -> Alice $1 9 9- 0 0
Bill -> Charles $5 9 4- 5- 0
Charles -> Alice $5 4 4- 0 0
你有它.在每笔交易中,您贷记一个分类帐帐户并借记另一个帐户,以便余额始终为零.最后,您只需计算出应用于每个帐户的最小数量的事务,以将其返回到零.
对于这个简单的案例,这是从Bill到Alice的简单4美元转账.您需要做的是为每个添加的事务将至少一个帐户(但最好是两个)减少到零.让我们说你有更复杂的:
Alice Bill Charles Balance
Alice -> Bill $10 10 10- 0 0
Bill -> Alice $1 9 9- 0 0
Bill -> Charles $5 9 4- 5- 0
Charles -> Alice $5 4 4- 0 0
Charles -> Bill $1 4 5- 1 0
那么所需的交易将是:
Bill -> Alice $4 0 1- 1 0
Bill -> Charles $1 0 0 0 0
不幸的是,在某些州,这种简单的贪婪策略并没有产生最好的解决方案(值得称赞j_random_hacker).一个例子是:
Alan Bill Chas Doug Edie Fred Bal
Bill->Alan $5 5- 5 0 0 0 0 0
Bill->Chas $20 5- 25 20- 0 0 0 0
Doug->Edie $2 5- 25 20- 2 2- 0 0
Doug->Fred $1 5- 25 20- 3 2- 1- 0
显然,这可以在四个动作中反转(因为到达那里只需要四个动作)但是,如果你选择不明智的第一步,那么你可以选择(Edie->Bill $2)五个最小的动作.
您可以使用以下规则解决此特定问题:
这将导致以下顺序:
Alan->Bill $5.Chas->Bill $20.然而,这仅仅是因为可能性很小.随着人数的增加以及群体间关系变得更加复杂,您很可能需要进行详尽的搜索才能找到所需的最小移动次数(基本上是上面的规则1,2和3,但扩展到处理更深度) .
我认为这是在所有情况下为您提供最少数量的交易所需要的.然而,最好的答案可能不是必需的(最好的,在这种情况下,意味着最大的"每次降压").可能即使是基本的1/2/3规则集也能为您提供足够好的答案.
jwo*_*ard 20
直觉上,这听起来像一个NP完全问题(它减少到一个非常像bin包装的问题),但是下面的算法(bin包装的修改形式)应该是相当不错的(没有时间进行证明,对不起).
净出每个人的立场,即从上面的例子:
Alice = $ 4 Bill = $ -4 Charles = $ 0
将所有净债权人从最高到最低排序,所有债务人从最低到最高排序,然后通过迭代列表进行匹配.
在某些时候,你可能需要将一个人的债务分成两部分 - 这里最好分成可能的最大块(即进入剩余空间最多的箱子).
这将采取类似O(n log n)的东西(再次,需要适当的证据).
有关详细信息,请参阅分区问题和二进制包装(前者是一个非常类似的问题,如果您将自己局限于固定精度事务,则它是等效的 - 当然需要证明).
Dav*_*vra 13
我创建了一个Android应用程序来解决这个问题.您可以在旅行期间输入费用,甚至建议您"谁应该下次付款".最后计算"谁应该向谁发送多少".我的算法计算最小所需的交易数量,你可以设置"交易容忍度",这可以进一步减少交易(你不关心1美元的交易)尝试一下,它叫做定居:
https://market.android.com/details?id=cz.destil.settleup
我的算法描述:
我有基本算法解决n-1事务的问题,但它不是最优的.它的工作原理如下:从付款开始,我为每个成员计算余额.平衡就是他付出的代价,减去他应该付出的代价.我越来越平衡地对成员进行排序.然后我总是把最贫穷和最富有的人交易完成.其中至少有一个以零余额结束,并被排除在进一步计算之外.有了这个,交易数量不能比n-1差.它还最大限度地减少了交易中的金额.但它并不是最优的,因为它不会检测可以在内部稳定的子组.
找到可以在内部解决的子群很难.我通过生成所有成员组合并检查子组中的余额总和是否等于零来解决它.我从2对开始,然后是3对......(n-1)对.可以使用组合生成器的实现.当我找到一个子组时,我使用上面描述的基本算法计算子组中的事务.对于每个找到的子组,都可以节省一个事务.
解决方案是最佳的,但复杂性增加到O(n!).这看起来很糟糕,但诀窍是现实中只有少数成员.我在Nexus One(1 Ghz处理器)上进行了测试,结果是:直到10名成员:<100 ms,15名成员:1 s,18名成员:8 s,20名成员:55 s.因此,直到18名成员执行时间很好.> 15个成员的解决方法可以是仅使用基本算法(它快速且正确,但不是最佳).
源代码:
有关用捷克语编写的算法的报告中提供了源代码.源代码在最后,它是英文的:
http://www.settleup.info/files/master-thesis-david-vavra.pdf
我发现了一个在Excel中实现的实用解决方案:
找出最多的人
让那个人支付他应该得到最多的人的全部金额
这使得第一个人为零
重复这个过程,考虑到(n-1)个人中有一个人的数量发生了变化
它应该导致最多(n-1)次转移,而关于它的好处是没有人进行多次付款.以jrandomhacker的(修改)示例为例:
a = -5 b = 25 c = -20 d = 3 e = -2 f = -1(总和应为零!)
c - > b 20.结果:a = -5 b = 5 c = 0 d = 3 e = -2 f = -1
a - > b 5结果:a = 0 b = 0 c = 0 d = 3 e = -2 f = -1
e - > d 2结果a = 0 b = 0 c = 0 d = 1 e = 0 f = -1
f - > d 1
现在,每个人都感到满意,并且没有人因为支付两笔或更多钱而感到困扰.如您所见,一个人可能会收到多个付款(本例中为d人).