平衡算法以均衡差异？

Question

比如说,我们有N多个账户有正余额B_1, ..., B_n.

我们可以进行转账T(from,to,amount),在账户之间取得一定的余额.

我们了解最佳的余额分配O_1, ..., O_n.

问题是:我们如何找到实现最佳分配的最小转移集？我们N-1最多可以获得转账吗？

例:

Balances  {0}: 10, {1}: 40, {2}: 50
Optimal   {0}: 20, {1}: 60, {2}: 20

T(2,0,10) => {0}: 20, {1}: 40, {2}: 40
T(2,1,20) => {0}: 20, {1}: 60, {2}: 20

Answer 1

是的,你可以随时获得N-1转移.以下是归纳证明:

1. 因为N=2,显然只需要一次转移.
2. 对于N>2,有两种情况:
   1. 我们已经处于最佳分布状态,在这种情况下无关紧要.
   2. 存在i和j那样B_i > O_i和B_j < O_j.转移min(B_i - O_i, O_j - B_j)从账户i到账户j.这平衡了两个帐户中的一个,从而减少了N-1案件的问题.

证明是建设性的,给你一个算法.该算法不会尝试最小化传输次数.

很容易想出用于减少步骤数的启发式方法.对于我来说,在最佳状态下进行思考是有点晚了,但如果问题证明是NP难的话,我也不会感到惊讶.