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



最近我读到了关于Splitwise问题的文章,其中有一群人彼此之间有债务,目标是用最少的交易数量来解决这些债务。它也可以被建模为一个有向加权图,其边将被减少。

我最常遇到的解决方案是一种贪婪的迭代算法,它首先计算每个人的净结果(欠他的钱-欠的钱(,然后重复以下步骤:

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。

我的问题:

  • 该算法产生的交易金额真的是最优的吗?如果是,如何证明这一点
  • 如果不是,该算法的最优性的反例是什么,即债务可以通过比其输出的交易更少的交易最小化的情况

看起来这个算法不是最优的。考虑案例[-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美元的人支付。

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

最新更新