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

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

系统如下:

它在一群 friend 之间登记小额贷款。 Alice和Bill正要吃午饭，Bill的卡不起作用，所以Alice付了他的饭菜10美元。
第二天，Bill和Charles在火车站相遇，查尔斯(Chales)没钱买票，所以Bill用5美元买了他。
那天晚些时候，Alice向Charles借了5美元，从Bill借了1美元，给她的 friend 买了礼物。

现在，假设他们都在系统中注册了该交易，则如下所示:

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

因此，现在，唯一需要做的就是Bill给Alice $ 4(他给了她$ 1，而Charlie将他的$ 5转移到了Alice alredy)，它们处于初始状态。

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

最佳答案

实际上，这看起来像是双重录入会计概念可以帮助完成的工作。

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

                          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相似的推理，总共进行了四步 Action 。

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

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

关于algorithm - 使用哪种算法确定使系统进入 “Zero”状态所需的最少操作数？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/877728/