Chi deve l'ottimizzazione del denaro

Question

Supponiamo che tu abbia n persone, ognuna delle quali si deve dei soldi. In generale dovrebbe essere possibile ridurre la quantità di transazioni che devono essere effettuate. cioè se X deve Y £ 4 e Y deve X £ 8, allora Y deve solo pagare X £ 4 (1 transazione invece di 2).

Questo diventa più difficile quando X deve Y, ma Y deve anche Z che deve anche X. Posso vedere che puoi facilmente calcolare un ciclo particolare. Mi aiuta quando lo considero un grafo completamente connesso, con i bordi come la somma che ogni persona deve.

Il problema sembra essere NP-completo, ma che tipo di algoritmo di ottimizzazione posso fare, tuttavia, per ridurre la quantità totale di transazioni ? Non deve essere così efficiente, dato che N è abbastanza piccola per me.

Edit:

Lo scopo di questo problema sarebbe quello di essere in grado di avere nel sistema contabile qualcosa che può dire a ogni persona, quando il log-in "È possibile rimuovere M quantità di transazioni, semplicemente pagando qualcuno X importo e qualcun altro importo Y ". Quindi la soluzione bancaria (anche se ottimale se tutti pagano allo stesso tempo) non può essere realmente utilizzata qui.

Answer 1

Penso che sia necessario creare una struttura dati diversa (un albero, ogni volta che una persona è il nodo radice) che verificherà per ciascuna persona quante "transazioni" puoi "uccidere", quindi scegli la migliore , crea il ciclo e ricostruilo di nuovo. no is (N), penso che sia N^2, e non ti darà il risultato migliore. è solo una strategia.

Answer 2

Le persone sono obbligate a liquidare i loro debiti pagando qualcuno a cui sono debitori di soldi? In caso contrario, il seguente sembra funzionare in modo sospetto:

Per ogni persona, calcolare l'importo netto che dovrebbero pagare o che dovrebbero ricevere.

Avere qualcuno che deve denaro netto paga qualcuno che dovrebbe ricevere denaro netto minimo (importo dovuto, importo da ricevere). Dopo questo, almeno uno dei due partecipanti non deve nulla e non dovrebbe ricevere nulla, e quindi può essere rimosso dal problema.

Supponendo che mi sia sfuggito qualcosa, quali sono i limiti applicabili (o errore grossolano)?

Answer 3

Solo a pensarci inizierei osservando ciascun ciclo nel grafico diretto e riducendo ogni spigolo nel ciclo per il valore del bordo minimo nel ciclo, quindi rimuovo del tutto il margine minimo. Risciacqua e ripeti.

Answer 4

Nomina arbitrariamente una persona per essere il banchiere.

Ogni altra persona trasferisce la somma di tutte le transazioni in uscita meno le transazioni in entrata (quindi depositi o prelievi) a quella persona.

Ci sarà un massimo di (n-1) transazioni, che è piuttosto piccola. È veloce. È semplice.

Dato che tutti coloro che trasferisce il denaro dovrà essere coinvolto in una transazione in ogni caso *, si è limitato ad essere nel peggiore dei casi due volte il caso ottimale. **

* L'eccezione è il banchiere se stessi. Una rapida ottimizzazione è quella di garantire che il banchiere designato non sia qualcuno che detiene una posizione neutrale.

** Spiegazione mia logica limite superiore ulteriormente:

Supponiamo il caso ottimale è A dà $ 1 a B, e C dà $ 1 a D, e E è neutro = due operazioni.

Quindi con questa logica, se E è il banchiere designato, A dà $ 1 a E, E dà $ 1 a B, C dà $ 1 a E ed E dà $ 1 a D = quattro transazioni.

Con l'ottimizzazione, assicurandosi di non scegliere una persona neutrale per banchiere, selezionare A invece. A dà $ 1 a B, C dà $ 1 a A. A dà $ 1 a D = tre transazioni.

Answer 5

Questo problema può essere risolto con l'algoritmo di Warshall.

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; 
} 
} 

Al termine algoritmo, il numero totale di transazioni richieste sarebbe il numero di voci positive nella tabella deve.

Non ho ancora verificato se l'algoritmo funzionerà, in base alla natura del problema che potrebbe funzionare. La soluzione è O (N^3).

Answer 6

Penso che sia necessario rimuovere tutti i cicli riducendo gli spigoli con il valore minimo del bordo e rimuovendo il valore 0. Dopo di esso si otterrà il grafico senza cicli. Penso che tu debba trovare i vertici, che non hanno alcun riferimento a loro (l'uomo deve solo soldi agli altri). Quest'uomo deve pagare soldi, perché non c'è nessuno che paghi i soldi per loro. Quindi il mio punto è che devi trovare in qualche modo chi devono pagare.

Answer 7

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 

Answer 8

Ecco la soluzione Python che ho utilizzato; è la stessa idea del post di Gunner, con alcune modifiche di riga:

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; 

Funziona a meraviglia.

È possibile verificare con cioè .:

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

Answer 9

ho una soluzione al problema scritto in MATLAB. Si basa su una matrice di chi deve chi cosa. Il numero nel (i, j) significa che la persona deve la persona il numero. Per esempio.

B deve A 2 e A deve B 1

naturalmente in questo caso è banale che B deve solo dare A 1

Questo diventa più complesso con più ingressi. Tuttavia, con l'algoritmo che ho scritto, posso garantire che non si verificano più transazioni N-1 dove N è il numero di persone 2 in questo caso.

Ecco il codice che ho scritto.

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; 

fine

Answer 10

ho creato un app Android, che risolve questo problema. Puoi inserire le spese durante il viaggio, ti consiglia anche "chi dovrebbe pagare il prossimo". Alla fine calcola "chi deve inviare quanto a chi".Il mio algoritmo calcola il numero minimo richiesto di transazioni ed è possibile l'installazione di "tolleranza transazione" che può ridurre le transazioni ancora di più (non si cura circa $ 1 transazioni) Provalo, si chiama Settle Up:

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

Descrizione del mio algoritmo:

Ho un algoritmo di base che risolve il problema con le transazioni n-1, ma non è ottimale. Funziona così: dai pagamenti, calcolo il saldo per ogni membro. L'equilibrio è ciò che ha pagato meno quello che dovrebbe pagare. Ordino sempre più membri in base all'equilibrio. Poi prendo sempre il più povero e il più ricco e la transazione è fatta. Almeno uno di essi finisce con zero saldo ed è escluso da ulteriori calcoli. Con questo, il numero di transazioni non può essere peggiore di n-1. Inoltre riduce al minimo l'ammontare di denaro nelle transazioni. Ma non è ottimale, perché non rileva sottogruppi che possono stabilirsi internamente.

Trovare i sottogruppi che possono stabilirsi internamente è difficile. Lo risolvo generando tutte le combinazioni di membri e controllando se la somma dei saldi nel sottogruppo è uguale a zero. Comincio con coppie a 2 coppie, quindi a 3 coppie ... (n-1). Sono disponibili implementazioni di generatori combinati. Quando trovo un sottogruppo, calcolo le transazioni nel sottogruppo usando l'algoritmo di base descritto sopra. Per ogni sottogruppo trovato, viene risparmiata una transazione.

La soluzione è ottimale, ma la complessità aumenta a O (n!). Questo sembra terribile, ma il trucco è che ci sarà solo un piccolo numero di membri nella realtà. L'ho provato su Nexus One (1 Ghz procesor) ei risultati sono: fino a 10 membri: < 100 ms, 15 membri: 1 s, 18 membri: 8 s, 20 membri: 55 s. Quindi fino a 18 membri il tempo di esecuzione va bene. Una soluzione alternativa per> 15 membri può essere quella di utilizzare solo l'algoritmo di base (è veloce e corretto, ma non ottimale).

Codice sorgente:

codice sorgente è disponibile all'interno di un rapporto su un algoritmo scritto in ceco. Il codice sorgente è alla fine ed è in inglese:

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