Au confluent de l'algorithmique et de la modélisation
Un problème à un million de dollars : trouver une solution est-il aussi facile que la vérifier ? Écrit sous la forme « P = NP ? », ce problème est pour l'instant toujours ouvert. Ainsi, montrer qu'un emploi du temps vérifie les contraintes imposées est facile, mais en trouver un qui convienne ? S'il faut les énumérer un par un pour les tester, on risque d'y passer un temps plus long que l'âge du soleil, alors qu'on aimerait avoir la solution dans les cinq minutes ou les vingt-quatre heures. On cherche d'abord à identifier les problèmes que l'on sait résoudre rapidement. Pour les autres, on utilisera si possible des recherches arborescentes intelligentes, des algorithmes exacts efficaces de type cheminement combinatoire, ou des méthodes approchées (métaheuristiques).
Tutti gli articoli di questo dossier
Programmazione lineare intera | Tangente
Per risolvere problemi di ottimizzazione, può essere necessario tradurli in equazioni all’interno di modelli matematici. La programmazione lineare intera consente di farlo usando soltanto polinomi di primo grado, le cui variabili devono assumere valori interi.
P è uguale a NP?
La domanda tiene con il fiato sospeso la comunità scientifica da oltre quarant’anni. Fa parte dei «problemi del millennio», l’elenco di sette grandi enigmi matematici proposti dal Clay Mathematics Institute nel 2000. Facciamo luce sulla questione.
Metaeuristiche: ottimizzazione approssimata | Tangente
Problemi NP-difficili, esplosione combinatoria, modelli con milioni di variabili e un numero esponenziale di disequazioni… Che fare quando nessun metodo di ottimizzazione funziona? Quale metodo usare quando si vuole ottenere rapidamente una soluzione a un problema?
Percorsi combinatori: i percorsi più brevi | Tangente
Quando si decide il percorso man mano che si procede, come in un labirinto occorre scegliere tra più strade. E la domanda si ripresenta a ogni nuovo bivio, creando così un’esplosione combinatoria dei percorsi possibili. Come aggirarla?
Ricerca ad albero
Ottimizzare l’uso di un telescopio per stabilire quale parte del cielo osservare è fondamentale. Una sfida simile, riconducibile a un problema di colorazione, richiede tentativi che nemmeno un computer moderno ha il tempo di esaminare in modo esaustivo.