时间戳

首页 > 解决方案 > 贪心交易最小化算法的最优性

algorithm - 贪心交易最小化算法的最优性

问题描述

最近我一直在阅读有关拆分问题的文章，其中一个人有一群人彼此之间有债务，目标是用最少的交易来解决这些债务。它也可以建模为要减少边的有向加权图。

我最常遇到的解决方案是贪心 迭代 算法，首先计算每个人的净结果（欠他的钱 - 他欠的钱），然后重复以下操作：

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。

我的问题：

标签： algorithmoptimizationminimize

解决方案

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

实际上，我相信所描述的算法的目标是最小化交易的总金额，而不是交易的数量，它确实可以证明（尽管我不会在这里尝试）。

推荐阅读