Ricerca della transazione minima

1

Dato un elenco di transazioni come:

A -> 10 to B
B -> 10 to C

Il modo ingenuo di regolare la transazione sarebbe:

C owes 10 to B
B owes 10 to A

Ma la stessa transazione potrebbe essere risolta con:

C owes 10 to A

Sto rappresentando ogni transazione come un oggetto:

{
  amount: Number,
  account: Object,
  linkId: Object  
}

Quindi, per una transazione come: A da 10 a B ci sarebbe un oggetto come:

{amount: +10, account: B, linkId: A}

Quindi, se visualizzo le transazioni, anche ciascun nodo potrebbe avere cicli. Sto cercando di trovare un algoritmo efficiente ma non mi sento sicuro.

    
posta CodeYogi 29.11.2016 - 18:56
fonte

1 risposta

3

Sembra che minimizzi il problema del flusso di cassa .

Funziona così: crediti e debiti totali di ogni A, B, C ... per ottenere un valore netto per loro. Trova i due estremi (massimo al credito e massimo al debito) e fallo negoziare. Il minimo dei due avrà la sua rete andare a zero. Ora fallo di nuovo con quelli rimasti.

Funziona ma purtroppo questo è O (n 2 ).

    
risposta data 29.11.2016 - 22:21
fonte

Leggi altre domande sui tag