algorithm - 存在哪些算法可以最大限度地减少图中节点之间的交易数量？

Question

这个标题可能没有意义。假设如下:

• A欠B $5
• C欠B $10
• B欠D $15

在这种基本情况下，有三个事务，但可以减少为两个事务:

• A 给 D $5
• C 给 D $10

给定一个复杂得多的图，存在哪些算法可以最小化交易总数？

Answer 1

在我看来，在所有交易发生后，您首先必须弄清楚每个人的涨跌幅度。对于您的示例，这将是:

A :  -5
B :   0
C : -10
D : +15

一旦你有了它，你只需要让它们都为零。获得最高 yield ，并开始增加损失。在这一点上，它基本上是一个装箱问题。