Grafico Bipartito sbilanciato ponderato corrispondente

1

Sto cercando un modo per risolvere un problema di assegnazione, ma sto riscontrando alcuni problemi nel trovare l'algoritmo corretto da utilizzare.

Ho 2 liste di nodi A e B, e nel mio problema la lunghezza di A non può essere uguale a B.

Inoltre, il nodo a in A potrebbe non essere una potenziale corrispondenza con tutti i nodi in B. La preferenza è data da un doppio dove 0 non è interessato a 1 che è molto interessato e quindi rimuove tutte le corrispondenze con un bordo di 0 dopo (Poiché potrebbero esserci corrispondenze impossibili).

Se uno ha una preferenza tra x e b, b avrà la stessa preferenza per a.

Esempio grafico:

Sono interessato a creare l'abbinamento ottimale, il che significa che sommare i bordi è il più grande possibile. Nell'esempio sopra sarei interessato alla corrispondenza (1,1) e (3,2) lasciando 2 nella riga sinistra ineguagliata, con un peso del bordo totale di 1,9.

Ho esaminato il matrimonio stabile e l'algoritmo ungherese, ma entrambi questi algoritmi richiedono che ci sia una quantità uguale di nodi su ciascun lato e che non trovino il massimo peso del bordo totale.

(Il più grande o il più basso è una multa in quanto posso solo invertire il peso del bordo)

Qualcuno di voi può indicarmi un algoritmo che risolva questo problema per me?

    
posta Androme 15.06.2014 - 00:54
fonte

1 risposta

1

È possibile aggiungere nodi fittizi a B con bordi con peso da 0 a nodi in A e quindi invertire i pesi dei bordi. Controlla link e penso che tu possa applicare l'algoritmo ungherese a questo problema con la modifica e dopo aver trovato il costo totale minimo che puoi invertire ancora i pesi.

    
risposta data 15.06.2014 - 04:20
fonte

Leggi altre domande sui tag