Login Esegui login | Non sei registrato? Iscriviti ora (è gratuito!)
Username: Password:
  • Annuncio Pubblicitario

Cerco Programmatore Retribuito: Max Matching Pesato Bipartit

Il forum per tutti i developer. Leggere attentamente il regolamento di sezione prima di postare.

Cerco Programmatore Retribuito: Max Matching Pesato Bipartit

Messaggioda turnthehook » mer feb 02, 2011 4:37 pm

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!!!
Avatar utente
turnthehook
Neo Iscritto
Neo Iscritto
 
Messaggi: 3
Iscritto il: mer feb 02, 2011 4:33 pm

Re: cerco programmatore retribuito

Messaggioda M@ttia » mer feb 02, 2011 5:35 pm

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 [^]
</IE><FIREFOX>
Avatar utente
M@ttia
Moderatore
Moderatore
 
Messaggi: 8363
Iscritto il: lun giu 09, 2003 2:18 pm
Località: Ticino - Estero

Re: cerco programmatore retribuito

Messaggioda turnthehook » mer feb 02, 2011 5:45 pm

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.
Avatar utente
turnthehook
Neo Iscritto
Neo Iscritto
 
Messaggi: 3
Iscritto il: mer feb 02, 2011 4:33 pm

Re: cerco programmatore retribuito

Messaggioda M@ttia » mer feb 02, 2011 5:49 pm

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...
</IE><FIREFOX>
Avatar utente
M@ttia
Moderatore
Moderatore
 
Messaggi: 8363
Iscritto il: lun giu 09, 2003 2:18 pm
Località: Ticino - Estero

Re: Cerco Programmatore Retribuito: Max Matching Pesato Bipa

Messaggioda turnthehook » mer feb 02, 2011 5:59 pm

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
Avatar utente
turnthehook
Neo Iscritto
Neo Iscritto
 
Messaggi: 3
Iscritto il: mer feb 02, 2011 4:33 pm


Torna a Programmazione

Chi c’è in linea

Visitano il forum: Nessuno e 0 ospiti

Powered by phpBB © 2002, 2005, 2007, 2008 phpBB Group
Traduzione Italiana phpBB.it

megalab.it: testata telematica quotidiana registrata al Tribunale di Cosenza n. 22/09 del 13.08.2009, editore Master New Media S.r.l.; © Copyright 2008 Master New Media S.r.l. a socio unico - P.I. 02947530784. GRUPPO EDIZIONI MASTER Spa Tutti i diritti sono riservati. Per la pubblicità: Master Advertising