Vai al contenuto

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.

    Apri l'app →

  • 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.

    Apri l'app →

  • Colorazione: greedy e DSATUR


    Il grafo si colora vertice per vertice con il greedy e con DSATUR: Petersen, grafo a corona o grafo casuale.

    Apri l'app →

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.

    Apri l'app →

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.

    Apri l'app →