Wer schuldet wem Geld Optimierung

Ich erstellt habe, eine Android-app die dieses problem löst. Sie können die input-Kosten während der Reise, er empfiehlt sogar, das Sie "wer soll das bezahlen weiter". Am Ende wird berechnet ", der senden sollte, wie viel an wen". Mein Algorithmus berechnet minimale erforderliche Anzahl von Transaktionen, und Sie können setup "Transaktion " Toleranz", um Transaktionen noch weiter (Sie kümmern sich nicht um die 1 $ - Transaktionen) Probieren Sie es aus, es heißt zu Begleichen:

https://market.android.com/details?id=cz.destil.settleup

Beschreibung meines Algorithmus:

Habe ich grundlegende Algorithmus löst das problem mit n-1 Geschäfte, aber es ist nicht optimal. Es funktioniert wie folgt: Aus-Zahlungen berechne ich die balance für jedes Mitglied. Gleichgewicht ist, was er bezahlt, minus dem, was er zahlen soll. Ich Sortiere die Mitglieder nach balance immer. Dann habe ich immer die ärmsten und die reichsten und die Transaktion durchgeführt wird. Mindestens einer von Ihnen landet mit null-Saldo und der ist ausgeschlossen von den weiteren Berechnungen. Mit dieser, die Anzahl der Transaktionen kann nicht schlimmer sein als n-1. Es minimiert auch die Menge des Geldes in Transaktionen. Aber es ist nicht optimal, weil es nicht erkennen Untergruppen, die können abrechnen intern.

Finden Untergruppen, die können abrechnen intern ist schwer. Ich es lösen durch die Erzeugung aller Kombinationen von Elementen und die Prüfung, ob die Summe der Salden in der Untergruppe gleich null. Ich beginne mit der 2-Paare, dann 3-pair-Mädchen ... (n-1)Paare. Implementierungen der Kombination Generatoren sind verfügbar. Wenn ich eine Untergruppe, berechne ich Transaktionen in der Untergruppe mit basic-Algorithmus wie oben beschrieben. Für jede Gefundene Untergruppe, eine Transaktion verschont.

Die Lösung optimal ist, aber die Komplexität steigt auf O(n!). Dies sieht schrecklich aus, aber der trick ist, es gibt nur kleine Anzahl von Mitgliedern in der Realität. Ich habe es getestet auf Nexus One (1 Ghz procesor) und die Ergebnisse sind: bis zu 10 Mitglieder: <100 ms, 15 Mitglieder: 1 s, 18 Mitglieder: 8 s, 20 Mitglieder: 55 s. Also bis 18 Mitgliedern, die Ausführungszeit ist in Ordnung. Workaround für >15 Mitglieder kann nur der grundlegende Algorithmus (es ist schnell und korrekt, aber nicht optimal).

Source code:

Source-code verfügbar ist, in einem Bericht über den Algorithmus geschrieben in Tschechisch. Source code ist am Ende und es ist in Englisch:

http://settleup.destil.cz/report.pdf

for each debt in debts
  debt.creditor.owed -= debt.amount
  debt.deptor.owed += debt.amount
end

for each person in persons
  if person.owed > 0 then
    deptors.add person
  else if person.owed < 0 then
    creditors.add person
  end
end

deptors.sort_by_owed_desc
creditor.sort_by_owed_asc

for each debtor in deptors
  while debtor.owed > 0
    creditor = creditors.top
    amount = min( debtor.owed, -creditor.owed)
    creditor.owed += amount
    debtor.owed -= amount
    if creditor.owed == 0 then
      creditors.remove_top
    end
    write debtor.name " owes " creditor.name " " amount "€"
  end
end

Hier ist die Python-Lösung, die ich verwendet; es ist die gleiche Idee, als Gunner ' s post, mit ein paar änderungen:

for i in N:
    for j in N:
        if i!=j and owes[i][j] > owes[j][i]:
            owes[i][j] -= owes[j][i]
            owes[j][i] = 0
for k in N:
    for i in N:
        for j in N:
            if k == i or i == j or k == j:
                continue
            if owes[j][k] > owes[i][j]:
                owes[i][k] += owes[i][j]
                owes[j][k] -= owes[i][j]
                owes[i][j] = 0;

Arbeitet ein Genuss.

Können Sie es testen mit also:

owes = [[0,2,11], [4,0,7], [2,3,0]]
N = range(len(owes))

Diesem problem begegnet werden kann mit dem Warshall-Algorithmus.

for(i=0;i<n;i++)
  for(j=0;j<n;j++)
    if ( i!= j && owes[i][j] > owes[j][i] )
owes[i][j] -= (owes[i][j] - owes[j][i]), owes[j][i] = 0;

for(k=0;k<n;k++)
 for(i=0;i<n;i++)
  for(j=0;j<n;j++)
  {
if( k == i || i == j || k == j ) continue;
if ( owes[j][k] > owes[i][j] )
{
int diff = owes[j][k] - owes[i][j]; 
owes[i][j] = 0;
owes[i][k ] += diff;
owes[j][k] -= diff;
} 
}

Nachdem der Algorithmus beendet ist, wird die Gesamtzahl der Transaktionen, die erforderlich wäre, die Anzahl der positiven Einträge in der schuldet Tabelle.

Habe ich noch nicht verifiziert, ob der Algorithmus funktioniert, basiert auf der Natur des Problems kann es funktionieren. Lösung ist O(N^3).

Habe ich eine Lösung für das problem in matlab geschrieben. Es basiert auf einer matrix, wer schuldet wem was. Die Zahl in der (i,j) bedeutet, dass person j schuldet person, mit der ich die Anzahl. E. g.

B schuldet A 2
und A schuldet B 1

natürlich in diesem Fall ist es trivial, dass B nur Ein 1 geben

Diese wird komplexer, mit mehr Einträgen. Jedoch mit dem Algorithmus, den ich schrieb, ich kann garantieren, dass nicht mehr als N-1 Transaktionen erfolgt, wobei N die Anzahl der persones 2 in diesem Fall.

Hier ist der code, den ich schrieb.

function out = whooweswho(matrix)
%input sanitation
if ~isposintscalar(matrix)
    [N M] = size(matrix);
    if N ~= M
        error('Matrix must be square');
    end

    for i=1:N
        if matrix(N,N) ~= 0
            error('Matrix must have zero on diagonals');
        end
    end
else
    %construction of example matrix if input is a positive scalar
    disp('scalar input: Showing example of NxN matrix randomly filled');
    N = matrix;
    matrix = round(10*N*rand(N,N)).*(ones(N,N)-eye(N))
end

%construction of vector containing each persons balance
net = zeros(N,1);
for i=1:N
  net(i) = sum(matrix(i,:))-sum(matrix(:,i));
end

%zero matrix, so it can be used for the result
matrix = zeros(size(matrix));

%sum(net) == 0 always as no money dissappears. So if min(net) == 0 it
%implies that all balances are zero and we are done.
while min(net) ~= 0
  %find the poorest and the richest.
  [rec_amount reciever] = max(net);
  [give_amount giver] = min(net);
  %balance so at least one of them gets zero balance.
  amount =min(abs(rec_amount),abs(give_amount));
  net(reciever) = net(reciever) - amount;
  net(giver) = net(giver) + amount;
  %store result in matrix.
  matrix(reciever,giver) = amount;
end
%output equivalent matrix of input just reduced.
out = matrix;

Ende