MegaLab.it

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!!!

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

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.

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...

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