Balancing-Algorithmus, um Unterschiede auszugleichen?

Question

Sagen wir, wir haben N Anzahl der Konten mit positiven Salden B_1, ..., B_n.

Wir können eine Überweisung T(from,to,amount) machen, die einen bestimmten Betrag des Guthabens zwischen den Konten verschiebt.

Wir haben Kenntnisse über eine optimale Verteilung von Waagen O_1, ..., O_n.

Die Frage ist: Wie können wir die minimale Anzahl von Übertragungen finden, die die optimale Verteilung erreichen? Können wir immer mit N-1 Übertragungen kommen?

Beispiel:

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

Ja, man kann immer mit nicht mehr als N-1 Transfer wegzukommen. Hier ist ein Beweis durch Induktion:

1. Für N=2 ist es offensichtlich, dass nicht mehr als eine einzige Übertragung erforderlich ist.
2. Für N>2, gibt es zwei Fälle:
   1. Wir sind bereits bei der optimalen Verteilung, wobei in diesem Fall gibt es nichts zu tun.
   2. Dort existieren i und j so dass B_i > O_i und B_j < O_j. Übertragen Sie min(B_i - O_i, O_j - B_j) von Konto i zu Konto j. Dies gleicht einen der beiden Konten aus, wodurch das Problem auf den N-1 Fall reduziert wird.

Der Beweis ist konstruktiv, Sie einen Algorithmus zu geben. Der Algorithmus versucht nicht, die Anzahl der Übertragungen zu minimieren.

Es ist einfach, mit Heuristiken zur Reduzierung der Anzahl der Schritte zu kommen. Es ist ein bisschen spät am Tag, dass ich über Optimalität nachdenke, aber es würde mich nicht überraschen, wenn sich das Problem als NP-hart herausstellen würde.