Algoritmi ad hoc¶
Parte 6 del corso, volume 6 delle dispense: capitoli 41–42.
Algoritmi ad hoc: il branch-and-bound sull'elemento critico per il problema dello zaino 0/1 e il branch-and-bound DSATUR per la colorazione dei vertici.
Problemi di zaino¶
-
41. Zaino: branch-and-bound sull'elemento critico
L'algoritmo per il KP · Un esempio svolto
Problemi di colorazione¶
-
42. Colorazione dei vertici: il branch-and-bound DSATUR
L'algoritmo per il VCP · Un esempio svolto