algorithm - 使用什么算法来确定使系统进入 "Zero"状态所需的最少操作数？

Question

这是一个更通用的问题，不是特定于语言的。有关要使用的想法和算法的更多信息。

系统如下:

它记录 friend 组之间的小额贷款。 Alice 和 Bill 要去吃午饭，Bill 的卡坏了，所以 Alice 付了他的餐费，10 美元。
第二天 Bill 和 Charles 在火车站相遇，Charles 没钱买票，所以 Bill 给他买了一张，5 美元.那天晚些时候，Alice 从 Charles 那里借了 5 美元，从 Bill 那里借了 1 美元，给她的 friend 买了一件礼物。

现在，假设他们都在系统中注册了该交易，它看起来像这样:

Alice -> Bill $10
Bill -> Alice $1
Bill -> Charles $5
Charles -> Alice $5

所以，现在，唯一需要做的就是 Bill 给 Alice 4 美元(他给了她 1 美元和 Charles 已经将他的 5 美元转移给 Alice)并且它们处于初始状态。

如果我们将其扩展到许多不同的人，进行多次交易，那么获得尽可能少的交易的最佳算法是什么？

Answer 1

这实际上看起来像是复式记账概念可以提供帮助的工作。

您的交易可以构造为簿记条目，因此:

                          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)，则五步是你能逃脱的最低限度。

您可以使用以下规则解决这个特殊问题:

• (1) 如果你能消除两个余额，那就去做。
• (2) 否则，如果您可以消除一个余额并准备好在下一步中消除两个余额，那就去做吧。
• (3) 否则，清空任何一笔余额。

这将导致以下序列:

• (a) [1] 不适用，[2] 可以通过 Alan->Bill $5 实现。
• (b) [1] 可以用 Chas->Bill $20 完成。
• (c) 和 (d)，与 Doug、Edie 和 Fred 的推理相似，总共有四步。

但是，这只是因为可能性很小。随着人数的增加和团队内部关系变得更加复杂，您很可能需要进行详尽的搜索以找到所需的最少移动次数(基本上是上面的规则 1、2 和 3，但已扩展以处理更深入的问题) .

我认为这是在所有情况下为您提供最少数量交易所需要的。然而，这可能不是最佳答案所必需的(最佳，在这种情况下，意味着最大的“性价比”)。可能即使是基本的 1/2/3 规则集也会为您的目的提供足够好的答案。