Cerco Programmatore Retribuito: Max Matching Pesato Bipartit

[turnthehook]

Ciao a tutti, cerco disperatamente un programmatore (retribuito),preferibilmente C++, ma non necessariamente, che mi possa implementare un programmino che risolva un problema di ricerca operativa: MASSIMO MATCHING PESATO SU GRAFO BIPARTITO...URGENTE!!!

[M@ttia]

Purtroppo al momento non ho tempo di mettermi a programmare (amati esami ...), ma il problema in sé è relativamente semplice e ampiamente risolto e analizzato. A dipendenza di come il tuo grafo è dato come input il codice C++ varierà, ma l'idea dell'algoritmo sarà sempre una degli algoritmi "famosi" esistenti (che poi possono venire ottimizzati a seconda delle strutture dati usate, programmazione multicore, ecc.).

• Il primo algoritmo che mi viene in mente, nonché anche il più semplice da capire (ma probabilmente non il più efficente) è quello di:
  

  Codice: Seleziona tutto

  1) Iniziare con Matching M := vuoto;
2) Cercare nel grafo un "improving alternating path" P;
3) M := Switchare tutti i lati in P che erano in M in liberi, e quelli liberi in M;
4) Ripetere 2-3 fintanto che un P improving non esiste più.


  
  Un path è alternating quando alterna lati in M e non in M; è improving quando "somma(liberi)-somma(matching) > 0" (si può eseguire un BFS oppure un Dijkstra ad esempio per trovare questi path).
  
  
• Un secondo modo è di aggiungere tutti i lati mancanti con peso 0 (che quindi non verranno mai presi nel max, o comunque verranno presi solo nel caso in cui non era possibile fare altrimenti, quindi alla fine si lasciano via dal risultato) ed ottenere un grafo bipartito completo; a questo punto è un classico problema di maximum assignment, risolvibile in 1000 modi (scrivendo come una matrice e lavorando su di essa; formulando il linear problem matematico e risolvendo con CPLEX, ecc.).
  
  
• Ancora, orientando tutti i lati nel modo appropriato e aggiungendo un nodo "sorgente" a sinistra (collegato a tutti i sinistri) e un nodo target a destra (collegato a tutti quelli di destra) è possibile ricondurre il problema al trovare un maximum flow dalla sorgente al target.

Tutto dipende da quale si preferisce, da quale struttura dati si intende usare e da quanto tempo si vuole investire a programmare: non è difficile, dato che la teoria è già stata sviluppata interamente al giorno d'oggi...

Buon divertimento

[turnthehook]

Ti ringrazio molto dell'interessamento, ma il mio problema è diverso: io non ho mai programmato e non so come si faccia, per cui cercavo qualcuno che me lo implementasse del tutto. Grazie comunque.

[M@ttia]

Beh in questo caso ti consiglio di dare ulteriori dettagli per chi vorrà poi programmarlo (in che formato/convenzione viene dato il grafo (input)? Quanto saranno grandi? (20 nodi o 10.000.000 di nodi? deve essere altamente ottimizzato o basta che funzioni? ecc.), così uno vede se è alla sua portata o meno...

[turnthehook]

Allora il grafo deve essere un grafo bipartito completo, io devo inserire i due insiemi di nodi e i pesi degli archi,l'ordine di grandezza deve raggiungere circa i 5000 nodi