Laboratorio interattivo¶
Qui gli algoritmi euristici si toccano con mano: ogni app esegue un algoritmo passo per passo sulle istanze di riferimento del corso, che si possono anche cambiare. Scegli un'app: si apre a tutta pagina. Tutto gira nel browser; i numeri sono calcolati dall'algoritmo, non scritti a mano.
Capitolo 2 · Euristiche costruttive¶
-
Euristiche per il bin packing
Next Fit, First Fit, Best Fit, Worst Fit e FFD passo per passo, con il bound e l'ottimo. In «Impacchetti tu» provi a battere l'algoritmo.
-
List scheduling e LPT
Il diagramma di Gantt si costruisce lavoro per lavoro; accanto il bound max{max t_j, ⌈Σ t_j / m⌉} e l'ottimo.
-
Colorazione: greedy e DSATUR
Il grafo si colora vertice per vertice con il greedy e con DSATUR: Petersen, grafo a corona o grafo casuale.
Capitolo 3 · Ricerca locale¶
-
TSP: nearest neighbour e 2-opt
Il giro si costruisce città per città e poi il 2-opt lo migliora: sull'istanza del corso o nel piano, con le città da trascinare.
Capitolo 4 · Metaeuristiche¶
-
TSP: simulated annealing e tabu search
Le due metaeuristiche con il 2-opt, sull'istanza di riferimento, su TSP20 e sull'istanza degli esercizi, con i numeri casuali delle note: giro corrente, miglior giro e curva delle lunghezze.