Quale algoritmo utilizzare per determinare il numero minimo di azioni necessarie per portare il sistema in stato “Zero”?

Questa è una domanda più generica, non specifica per la lingua. Ulteriori informazioni su idea e algoritmo da utilizzare.

Il sistema è il seguente:

Registra piccoli prestiti tra gruppi di amici. Alice e Bill stanno andando a pranzo, la carta di Bill non funziona, quindi Alice paga il suo pasto, $ 10.
Il giorno dopo Bill e Charles incontrano in una stazione ferroviaria, Chales non ha soldi per il biglietto, quindi Bill lo compra uno, per $ 5. Più tardi quel giorno Alice prende in prestito $ 5 da Charles e $ 1 da Bill per comprare un regalo alla sua amica.

Ora, supponendo che tutti abbiano registrato le transazioni nel sistema, sembra che questo:

 Alice -> Bill $10 Bill -> Alice $1 Bill -> Charles $5 Charles -> Alice $5 

Quindi, ora, l’unica cosa che deve essere fatta è Bill dona ad Alice $ 4 (le ha dato $ 1 e Charlie trasferito i suoi $ 5 ad Alice alredy) e sono allo stato iniziale.

Se lo ridimensioniamo a molte persone diverse, avendo più transazioni, quale sarebbe il miglior algoritmo per ottenere il minor numero ansible di transazioni?

Questo in realtà sembra un lavoro che il concetto di contabilità a partita doppia potrebbe aiutare.

Le tue transazioni potrebbero essere strutturate come voci contabili così:

  Alice Bill Charles Balance Alice -> Bill $10 10 10- 0 0 Bill -> Alice $1 9 9- 0 0 Bill -> Charles $5 9 4- 5- 0 Charles -> Alice $5 4 4- 0 0 

E il gioco è fatto. Ad ogni transazione, accrediti un conto contabile e ne addebiti un altro in modo che il saldo sia sempre zero. Alla fine, devi semplicemente calcolare le transazioni con il numero minimo da applicare a ciascun account per riportarlo a zero.

Per questo semplice caso, è un semplice trasferimento di $ 4 da Bill ad Alice. Quello che devi fare è ridurre a zero almeno un account (ma preferibilmente due) per ogni transazione aggiunta. Diciamo che hai avuto il più complicato:

  Alice Bill Charles Balance Alice -> Bill $10 10 10- 0 0 Bill -> Alice $1 9 9- 0 0 Bill -> Charles $5 9 4- 5- 0 Charles -> Alice $5 4 4- 0 0 Charles -> Bill $1 4 5- 1 0 

Quindi le transazioni necessarie sarebbero:

 Bill -> Alice $4 0 1- 1 0 Bill -> Charles $1 0 0 0 0 

Sfortunatamente, ci sono alcuni stati in cui questa semplice e avida strategia non genera la soluzione migliore (complimenti a j_random_hacker per j_random_hacker indicato). Un esempio è:

  Alan Bill Chas Doug Edie Fred Bal Bill->Alan $5 5- 5 0 0 0 0 0 Bill->Chas $20 5- 25 20- 0 0 0 0 Doug->Edie $2 5- 25 20- 2 2- 0 0 Doug->Fred $1 5- 25 20- 3 2- 1- 0 

Chiaramente, questo potrebbe essere invertito in quattro mosse (dal momento che quattro mosse sono (Edie->Bill $2) per arrivarci) ma, se scegli la tua prima mossa incautamente (Edie->Bill $2) , il cinque è il minimo con cui te la caverai.

Puoi risolvere questo particolare problema con le seguenti regole:

  • (1) se riesci a cancellare due saldi, fallo.
  • (2) altrimenti, se puoi eliminare un saldo e metterti in posizione per eliminarne due nella prossima mossa, fallo.
  • (3) altrimenti, eliminare qualsiasi equilibrio.

Ciò comporterebbe la seguente sequenza:

  • (a) [1] non applicabile, [2] può essere raggiunto con Alan->Bill $5 .
  • (b) [1] può essere fatto con Chas->Bill $20 .
  • (c) e (d), un ragionamento simile con Doug, Edie e Fred, per quattro mosse totali.

Tuttavia, ciò funziona semplicemente a causa del piccolo numero di possibilità. Con l’aumento del numero di persone e l’intreccio tra le relazioni di gruppo, molto probabilmente avrai bisogno di una ricerca esauriente per trovare il numero minimo di mosse richieste (fondamentalmente le regole 1, 2 e 3 sopra ma ampliate per gestire più profondità) .

Penso che sia quello che sarà richiesto per darti il ​​minor numero di transazioni in tutte le circostanze. Tuttavia, potrebbe essere che non è necessario per la migliore risposta (meglio, in questo caso, che significa “bang per buck” massimo). Può darsi che anche il set di regole 1/2/3 di base ti dia una risposta abbastanza buona per i tuoi scopi.

Intuitivamente, questo suona come un problema NP-completo (si riduce a un problema molto simile alla compressione bin), tuttavia il seguente algoritmo (una forma modificata di packing bin) dovrebbe essere abbastanza buono (non c’è tempo per una dimostrazione, mi dispiace).

  1. Elimina le posizioni di tutti, ad esempio dal tuo esempio sopra:

    Alice = $ 4 Bill = $ -4 Charles = $ 0

  2. Ordina tutti i creditori netti dal più alto al più basso, e tutti i debitori dal più basso al più alto, quindi confronta ripetendo gli elenchi.

  3. Ad un certo punto potrebbe essere necessario dividere i debiti di una persona per cancellare tutto – qui è probabilmente meglio dividere i pezzi più grandi possibili (cioè nei cassonetti con lo spazio più restante prima).

Ciò richiederà qualcosa come O (n log n) (di nuovo, è necessaria una prova adeguata).

Vedere il problema della partizione e l’ imballaggio del contenitore per ulteriori informazioni (il primo è un problema molto simile, e se ci si limita a transazioni di precisione fisse, allora è equivalente – ovviamente è necessaria la prova).

Ho creato un’app per 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 di transazioni richiesto e puoi impostare la “tolleranza delle transazioni” che può ridurre ulteriormente le transazioni (non ti importa delle transazioni di $ 1) 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 sottogruppi che possano sistemarsi internamente è difficile. Lo risolvo generando tutte le combinazioni di membri e controllando se la sum 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 (Processore 1 Ghz) 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:

Il codice sorgente è disponibile all’interno di un report sull’algoritmo scritto in ceco. Il codice sorgente è alla fine ed è in inglese:

http://www.settleup.info/files/master-thesis-david-vavra.pdf

Ho trovato una soluzione pratica che ho implementato in Excel:

  • scopri chi è il più

  • lascia che quella persona paghi l’intero importo che deve a colui che dovrebbe ottenere il massimo

  • ciò rende la prima persona zero

  • ripetere questo processo tenendo conto che una delle persone (n-1) ha una quantità modificata

Dovrebbe comportare un massimo di (n-1) trasferimenti e la cosa bella è che nessuno sta facendo più di un pagamento. Prendi l’esempio (modificato) di jrandomhacker:

a = -5 b = 25 c = -20 d = 3 e = -2 f = -1 (la sum dovrebbe essere zero!)

  1. c -> b 20. risultato: a = -5 b = 5 c = 0 d = 3 e = -2 f = -1

  2. a -> b 5 risultato: a = 0 b = 0 c = 0 d = 3 e = -2 f = -1

  3. e -> d 2 risultato a = 0 b = 0 c = 0 d = 1 e = 0 f = -1

  4. f -> d 1

Ora, tutti sono soddisfatti e nessuno si preoccupa di fare due o più pagamenti. Come puoi vedere, è ansible che una persona riceva più di un pagamento (persona d in questo esempio).

Bene, il primo passo è ignorare completamente le transazioni. Basta aggiungerli. Tutto quello che devi sapere è l’ammontare netto di debito che una persona deve / possiede.

È facile trovare le transazioni creando un grafico di stream pazzo e trovando il stream massimo. Quindi un taglio minimo …

Alcune elaborazioni parziali: c’è un nodo sorgente, un nodo sink e un nodo per ogni persona. Ci sarà un confine tra ogni coppia di nodes eccetto che nessun confine tra il nodo sorgente e il nodo sink. I bordi tra le persone hanno capacità infinita in entrambe le direzioni. I bordi provenienti da un nodo di origine a una persona hanno una capacità pari al debito netto della persona (0 se non hanno un debito netto). I bordi che vanno dal nodo persona al nodo sink hanno una capacità pari alla quantità netta di denaro di cui la persona è debitrice (0 se non hanno una rete dovuta).

Applicare il stream massimo e / o il taglio minimo ti daranno una serie di trasferimenti. L’importo del stream effettivo sarà la quantità di denaro che verrà trasferito.

Ho progettato una soluzione utilizzando un approccio un po ‘diverso rispetto a quelli che sono stati menzionati qui. Usa una formulazione di programmazione lineare del problema, attingendo alla letteratura di Compressed Sensing, specialmente da questo lavoro di Donoho e Tanner (2005) .

Ho scritto un post sul blog che descrive questo approccio, insieme a un piccolo pacchetto R che lo implementa. Mi piacerebbe ricevere un feedback da questa community.

Saluti.

Solo se qualcuno deve più di 2 persone, che devono anche lo stesso set, puoi ridurre il numero di transazioni dal set semplice.

Cioè, il set semplice è solo trovare ogni equilibrio e ripagarlo. Questo non è più di N! transazioni.

Se A deve B e C, e alcuni sottoinsiemi di BC devono reciproci, quindi B deve C, quindi anziché: A -> B, A -> C (3 transazioni). Dovresti usare: A -> B, B -> C (2 transazioni).

In altre parole, stai costruendo un grafico diretto e vuoi tagliare i vertici in ordine per massimizzare la lunghezza del percorso e minimizzare i bordi totali.

Scusa, non ho un algoritmo per te.

Dovresti essere in grado di risolverlo in O (n) determinando innanzitutto quanto deve o è dovuto a ciascuna persona. Trasferisci i debiti di chi deve meno di quanto è dovuto ai suoi debitori (trasformando così quella persona in un punto finale). Ripeti finché non riesci a trasferire altri debiti.

Questo è il codice che ho scritto per risolvere questo tipo di problema in Java. Non sono sicuro al 100% se questo dà il minor numero di transazioni. La chiarezza e la struttura del codice possono essere migliorate molto.

In questo esempio:

  • Sarah ha speso $ 400 per il noleggio di un’auto. L’auto è stata utilizzata da Sarah, Bob, Alice e John.
  • John ha speso $ 100 sulla spesa. I generi alimentari furono consumati da Bob e Alice.

     import java.util.*; public class MoneyMinTransactions { static class Expense{ String spender; double amount; List consumers; public Expense(String spender, double amount, String... consumers){ this.spender = spender; this.amount = amount; this.consumers = Arrays.asList(consumers); } } static class Owed{ String name; double amount; public Owed(String name, double amount){ this.name = name; this.amount = amount; } } public static void main(String[] args){ List expenseList = new ArrayList<>(); expenseList.add(new Expense("Sarah", 400, "Sarah", "John", "Bob", "Alice")); expenseList.add(new Expense("John", 100, "Bob", "Alice")); //make list of who owes how much. Map owes = new HashMap<>(); for(Expense e:expenseList){ double owedAmt = e.amount/e.consumers.size(); for(String c : e.consumers){ if(!e.spender.equals(c)){ if(owes.containsKey(c)){ owes.put(c, owes.get(c) + owedAmt); }else{ owes.put(c, owedAmt); } if(owes.containsKey(e.spender)){ owes.put(e.spender, owes.get(e.spender) + (-1 * owedAmt)); }else{ owes.put(e.spender, (-1 * owedAmt)); } } } } //make transactions. // We need to settle all the negatives with positives. Make list of negatives. Order highest owed (ie the lowest negative) to least owed amount. List owed = new ArrayList<>(); for(String s : owes.keySet()){ if(owes.get(s) < 0){ owed.add(new Owed(s, owes.get(s))); } } Collections.sort(owed, new Comparator() { @Override public int compare(Owed o1, Owed o2) { return Double.compare(o1.amount, o2.amount); } }); //take the highest negative, settle it with the best positive match: // 1. a positive that is equal to teh absolute negative amount is the best match. // 2. the greatest positive value is the next best match. // todo not sure if this matching strategy gives the least number of transactions. for(Owed owedPerson: owed){ while(owes.get(owedPerson.name) != 0){ double negAmt = owes.get(owedPerson.name); //get the best person to settle with String s = getBestMatch(negAmt, owes); double posAmt = owes.get(s); if(posAmt > Math.abs(negAmt)){ owes.put(owedPerson.name, 0.0); owes.put(s, posAmt - Math.abs(negAmt)); System.out.println(String.format("%s paid %s to %s", s, Double.toString((posAmt - Math.abs(negAmt))), owedPerson.name)); }else{ owes.put(owedPerson.name, -1 * (Math.abs(negAmt) - posAmt)); owes.put(s, 0.0); System.out.println(String.format("%s paid %s to %s", s, Double.toString(posAmt), owedPerson.name)); } } } } private static String getBestMatch(double negAmount, Map owes){ String greatestS = null; double greatestAmt = -1; for(String s: owes.keySet()){ double amt = owes.get(s); if(amt > 0){ if(amt == Math.abs(negAmount)){ return s; }else if(greatestS == null || amt > greatestAmt){ greatestAmt = amt; greatestS = s; } } } return greatestS; } } 

Se prendi gli stati come nodes del grafico , sarai in grado di utilizzare l’algoritmo del percorso più breve per conoscere la risposta.