使用哪种算法确定使系统进入“零”状态所需的最少操作数？

Question

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

系统如下：

它在一群朋友之间登记小额贷款。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美元，然后Charlie 将 5 美元 转给
了Alicealredy），它们就处于初始状态。

如果我们将其扩展到具有多个事务的许多不同的人，那么获得最少事务的最佳算法是什么？

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）如果可以消灭两个天平，请html" target="_blank">执行此操作。
• （2）否则，如果您可以消灭一个天平并设置自己以下一步消灭两个天平，请执行此操作。
• （3）否则，请清除任何一种余额。

这将导致以下顺序：

• （a）[1]不适用，[2]可通过实现Alan->Bill $5。
• （b）[1]可以用完成Chas->Bill $20。
• （c）和（d），与道格，伊迪和弗雷德类似的推理，总共进行了四步。

但是，这仅是因为可能性很小。随着人数的增加和小组之间的相互关系变得越来越复杂，您很可能需要进行详尽的搜索，以找到所需的最小移动次数（基本上是上述规则1、2和3，但已扩展以处理更多的深度）
。

我认为这是在所有情况下为您提供最少数量交易的条件。但是，可能不需要 最佳
答案（在这种情况下，最好的意思是最大“每单位成本”）。可能即使是基本的1/2/3规则集也可以为您的目的提供足够好的答案。