什么算法存在，以减少交易节点之间以图形的数量？ [英] What algorithms exist to minimize the number of transactions between nodes in a graph?

问题描述

这标题可能是没有意义的。假设如下：

That title probably doesn't make sense. Assume the following:

• 系统欠B $ 5
• ç欠B $ 10个
• 乙欠D $ 15个

在此基本情况有三种交易，但它可以被减少到两个交易：

In this basic situation there are three transactions but it can be reduced to two transactions:

• A给出了D $ 5
• C给出D $ 10个

给出一个更复杂的图形，有什么算法存在，以尽量减少交易总数？

Given a much more complicated graph, what algorithms exist to minimize the total number of transactions?

推荐答案

在我看来，你要搞清楚每个人有多少是向上/向下后，所有交易发生的第一件事情。对于你的榜样，这将是：

It seems to me the first thing you have to figure out how much each person is up/down after all transactions take place. For your example, that would be:

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

一旦你有，你就必须让他们全部为零。把你的最高增益，并开始增加损失吧。在这一点上它基本上是一个装箱问题。

Once you have that, you just have to make them all zero. Take your highest gain, and start adding losses to it. At this point it's basically a bin-packing problem.

这篇关于什么算法存在，以减少交易节点之间以图形的数量？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！