Diciamo che abbiamo un gruppo di N persone, e ogni persona potrebbe voler vendere o comprare uno degli oggetti M, come trovare un percorso chiuso tra loro per uno scambio?

Invece di una matrice sparsa andrei con un Grafico diretto , dove ogni nodo è una persona e ogni link è una potenziale transazione.

Ogni ciclo nel grafico è un potenziale scambio. Vedi Miglior algoritmo per il rilevamento dei cicli in un grafico diretto per ulteriori informazioni.

Penso che un buon modo per rappresentare il problema sia come bipartito , diretto .

Per creare il grafico, fai questo:

• Disegna un nodo per ogni persona.
• Disegna anche un nodo per ogni elemento.
• Ogni volta che una persona ha un oggetto, disegna una freccia da quella persona a quell'elemento . (L'idea è: se la persona è felice, allora possiamo ottenere l'oggetto.)
• Ogni volta che una persona vuole un oggetto, disegna una freccia da quell'elemento a quella persona . (L'idea è: se abbiamo l'oggetto, allora possiamo rendere felice la persona.)

Il tuo obiettivo è semplicemente quello di trovare un circuito in questo grafico.

Questo significa che la tua domanda può essere riformulata come, "Come posso trovare i circuiti in un grafico diretto bipartito?" Gli algoritmi descritti in queste domande e risposte possono essere utili:

• link
• link

(La differenza tra un circuito e un ciclo è che un circuito può visitare lo stesso nodo più volte (anche se non può usare la stessa freccia più volte), mentre un ciclo può visitare ogni nodo una volta sola. Nel contesto del tuo problema, un ciclo significherebbe che ogni persona partecipa a una sola operazione e ogni elemento partecipa a una sola operazione.)

Modifica: La mia altra risposta è migliore di questa; guarda invece quello.

Il problema può essere rappresentato creando una griglia piena di punti. La griglia ha:

• N righe, una per ogni persona.
• M colonne, una per ogni articolo.
• Un punto verde ogni volta che una persona è disposta a dare un elemento (perché "dare" inizia con "G" per "verde"). Ad esempio, se Bob è disposto a scambiare fino a tre mele, quindi inserisci 3 punti verdi nella cella della griglia che si trova nella riga che rappresenta Bob e la colonna che rappresenta le mele.
• Un punto rosso ogni volta che una persona desidera ricevere un elemento.

(In termini matematici, sarebbero due matrici N × M , chiamate G e R . )

Ecco un algoritmo per risolvere il tuo problema. Probabilmente non è l'algoritmo migliore , ma è un algoritmo an .

In primo luogo, trasforma la griglia in un grafico orientato seguendo questi due passaggi:

• Disegna una freccia da ogni punto verde a ogni punto rosso nella stessa colonna (a indicare che una persona può dare un oggetto e un'altra la persona può riceverlo).
• Disegna una freccia da ogni punto rosso a ogni punto verde nella stessa riga (a indicare che una persona può ricevere un oggetto e un altro oggetto).

In secondo luogo, trova un ciclo diretto nel grafico. Questo ciclo fornisce la risposta.

Ad esempio, supponi che Bob abbia una mela e desideri un'arancia e che Sarah abbia un'arancia e desideri una mela. La griglia conterrà

• un punto verde per (Bob, mela),
• un punto verde per (Sarah, arancione),
• un punto rosso per (Bob, arancione) e
• un punto rosso per (Sarah, mela).

Il ciclo che troviamo

• inizia dal punto verde (Bob, mela) e passa al punto rosso (Sarah, mela) (Bob dà una mela e Sarah lo riceve);
• passa dal punto rosso (Sarah, mela) al punto verde (Sarah, arancione) (dal momento che Sarah ha ricevuto una mela, è disposta a dare un'arancia);
• passa dal punto verde (Sarah, arancione) al punto rosso (Bob, arancione) (Sarah dà un'arancia a Bob); e
• ritorna dal punto rosso (Bob, arancione) al punto verde (Bob, mela) (Bob ha ricevuto un'arancia e quindi è disposto a mollare una mela).