贪婪交易最小化算法的最优性

问题描述 投票:0回答:1

最近,我一直在阅读Splitwise问题,在该问题中,一群人之间彼此之间有债务,而目标是以最少的交易数来偿还这些债务。也可以将其建模为要减少边缘的有向加权图。

[我最常遇到的解决方案是greedyiterativealgorithm,它首先计算每个人的净结果(欠他的钱-他欠的钱),然后重复以下步骤:

1. take max. debtor X and max. creditor Y
2. if X owes more than Y is owed
     then X pays Y Y's value
          reduce X's debt by Y's value
          set Y's value to 0
     else X pays Y X's value
          reduce Y's value by X's debt
          set X's debt to 0

...直到每个人的值都是0。

我的问题:

  • 该算法在产生的交易量上是否真的最优?如果是,如何证明?
  • 如果不是,那么该算法的最优性的反例是什么,即,可以用比其输出更少的交易来使债务最小化的情况?
algorithm optimization minimize
1个回答
0
投票

看来此算法不是最佳算法。考虑情况[-3,-2,-2、3、4],其中正表示债权人,负表示债权人。使用所描述的算法,我们需要四个交易操作才能消除所有债务:

>> [-3, -2, -2, 3, 4]
>> [0, -2, -2, 3, 1]    ([0] pays [4])
>> [0, 0, -2, 1, 1]     ([1] pays [3])
>> [0, 0, -1, 1, 0]     ([2] pays [4])
>> [0, 0, 0, 0, 0]      ([2] pays [3])

但是您可以看到可以通过三笔交易来清算债务:欠款$ 3的人支付贷方$ 3,然后两个欠款$ 2的人分别向欠债者$ 4支付。

实际上,我相信所描述的算法的目标是使交易的总金额最小化,而不是使交易的数量最小化,该交易可以做到并且可以证明(尽管我在这里不会尝试)。

© www.soinside.com 2019 - 2024. All rights reserved.