algorithm - 平衡算法以消除差异？

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-hard，我也不会感到惊讶。