5
Sono consapevole che ci sono molti argomenti simili. Ma la maggior parte di loro mi ha lasciato dei dubbi nel mio caso. Quello che voglio fare è trovare l'abbinamento perfetto (o il più vicino possibile perfetto nel caso in cui non ci sia corrispondenza perfetta ovviamente) e poi da tutti quegli abbinamenti in cui è possibile abbinare k di n vertici (dove k è il più alto possibile), Voglio scegliere il peso totale più alto possibile. Quindi, in poche parole quello che sto dicendo è seguenti priorità:Corrispondenza bipartitica ponderata
- abbinare quante vertici come possibili
- Perché (non ponderata) corrispondente al massimo nella maggior parte dei casi non è ambiguo, voglio scegliere quello che ha il più grande somma dei pesi sui bordi. Se ci sono molti di loro con lo stesso peso, non importa quale sarebbe scelto.
Ho sentito parlare dell'algoritmo Ford-Fulkerson. Funziona nel modo in cui lo descrivo o ho bisogno dell'altro algoritmo?
In effetti è per il mio diploma di studio finale (idk esattamente equivalente internazionale di laurea) sul problema dell'assunzione, quindi darò un tentativo di capire ford-fulkerson. Il problema è che non sono sicuro che funzioni nel modo che desidero. per esempio prendere il seguente caso:: = <1,3,1><2,4,1><1,4, infinito> non max-flusso significa che il bordo <1,4,inf> dovrebbe essere preso e allo stesso modo ha preso il peso massimo possibile invece di prima trovare il massimo vertice impostato e come seconda condizione somma dei pesi del bordo? –
abc
Questo non è esattamente il modo in cui useresti il flusso per risolvere questo problema. Vuoi capacità unitarie. Se si desidera una formulazione diretta, si utilizza un modello di flusso a costo minimo, mantenere le capacità dell'unità e lasciare che i costi siano, um, i costi. Questo non è un problema di flusso massimo, ma esiste un trucco (il metodo dual-primal) che consente di utilizzare il flusso massimo come subroutine. – tmyklebu