B&B ultimo appello, dubbio soluzione

Rispondi
Avatar utente
InformateciBot
Messaggi: 314
Iscritto il: 30/09/2018, 16:33

TuxDroid
Ciao a tutti, ho un dubbio su questa soluzione proposta:
[url=http://pages.di.unipi.it/mpappalardo/ro_2016_01_19_a.pdf]Esercizio 5, punto 3[/url]

Quando pone la variabile x34=0 calcola il nuovo vS(P)=80, e fin qui ci sono. Tuttavia il 2-albero non dovrebbe essere cambiato. Nell'istanzare la variabile successiva, ovvero x24=0, il 2-albero di costo minimo dovrebbe diventare l'albero costituito dagli archi {(1,4),(1,5),(2,3),(3,4),(3,5)} che dovrebbe avere costo = 79. Tuttavia sulla soluzione il costo è di 82 e questa operazione proprio non mi torna!

Voi cosa ne pensate? Grazie in anticipo!

bongi23
Quando togli l'arco (2,4) dal 2-albero devi "inserire" un altro arco che passa da 2, proprio perchè stiamo usando un 2-albero come rilassamento. In questo caso l'arco che entra al posto di 2,4 è l' arco 1,2, e tutto torna.

In generale in un r-albero devi avere due archi incidenti sul nodo r e devono essere gli archi di costo minimo che incidono su quel nodo. In questo caso particolare gli archi di costo minimo incidenti su 2 erano 2,4 e 2,3 ma dato che 2,4 lo togli il successivo arco con il minor peso è l'arco 1,2.

Spero di essere stato chiaro e di non averti detto qualche cavolata!
Rispondi

Torna a “[RO] Ricerca Operativa”