Il fondale è nella nebbia. Trova il punto più profondo esplorando meno celle possibile.
🔦Click su una cella → la esplori e scopri quanto è profonda
🎯Hai 30 tentativi per trovare il punto più profondo
🔲Il riquadro è il vicinato: le celle "accanto" a quella in cui sei
🏆Poi guarda come cercano gli algoritmi, sulla stessa mappa!
ℹ️ Esatti, approssimati, metaeuristiche
Un algoritmo esatto garantisce la soluzione migliore, ma per esserne sicuro deve controllare (quasi) tutto: su problemi grandi è troppo lento.
Una ricerca locale parte da una soluzione e guarda solo il suo vicinato: le soluzioni che si ottengono con una piccola modifica. Si sposta sulla migliore finché nessun vicino è meglio. Veloce, ma si ferma nel primo "buco" che trova: un ottimo locale.
Le metaeuristiche sono strategie per non restare intrappolati. Quelle a soluzione singola (come il Simulated Annealing) muovono una sola soluzione ma a volte accettano mosse peggiori. Quelle a popolazione (Genetico, Formiche, Sciame di particelle) muovono tante soluzioni che si scambiano informazioni.
Nessuna metaeuristica garantisce l'ottimo, ma di solito trova soluzioni molto buone esplorando una piccola parte della mappa.