Nel vasto mondo dell'informatica (e non solo!) incontriamo problemi di ogni tipo. Ma avete mai pensato che, andando oltre la loro specifica natura (matematica, logica, ingegneristica, economica, ecc.), molti problemi possono essere raggruppati in categorie ben definite?

Principalmente possiamo identificare tre gruppi principali:

1. Problemi di ricerca
2. Problemi di decisione
3. Problemi di ottimizzazione

Vediamoli in dettaglio per capirne le differenze.

Problemi di ricerca

Questa è forse la categoria più intuitiva perchè include tutti quei casi in cui il nostro obiettivo è l'individuazione di una soluzione che soddisfi determinati criteri.

Quando affrontiamo un problema di ricerca ci riferiamo sempre a una specifica istanza di quel problema. Un'istanza è un caso particolare con dati specifici.

Ad esempio risolvere "un'equazione di secondo grado" indica un tipo generale di problema, mentre "risolvere l'equazione x² - 4x + 4 = 0" fa riferimento ad una particolare istanza.

Nei problemi di ricerca vogliamo individuare una generica soluzione per quella specifica istanza o stabilire che non sono ammesse soluzioni.

È importante notare che una data istanza di un problema di ricerca potrebbe anche avere più soluzioni: in questi casi la scelta è arbitraria.

Ci basta trovarne anche una soltanto per dare una risposta positiva alla ricerca.

In sintesi nei problemi di ricerca vogliamo trovare UNA soluzione o dimostrare che non ne esiste NESSUNA.

Problemi di decisione

Si distinguono nettamente dagli altri per il tipo di risposta che richiedono, del tipo Sì/No oppure Vero/Falso.

In sostanza una risposta di tipo booleano.

Sono problemi basati su domande del tipo: "Questa cosa possiede tale proprietà?" oppure "Esiste una soluzione con queste caratteristiche?".

Un esempio classico è quello di un programma scritto in un linguaggio di programmazione e di cui si vuole stabilire se è sintatticamente corretto o meno.

La risposta a questa domanda sarà inevitabilmente "Vero" o "Falso" ("Sì" o "No") a seconda che il codice rispetti o meno tutte le regole sintattiche del linguaggio.

In sintesi nei problemi di decisione ci basta una risposta secca: Sì oppure No.

Problemi di ottimizzazione

Questa è forse la categoria più interessante e comune nella pratica quotidiana.

I problemi di ottimizzazione possono essere visti come una specializzazione di quelli di ricerca, nel senso che non siamo semplicemente interessati a trovare una soluzione, ma vogliamo trovare quella che ottimizza una certa metrica associata al problema stesso.

Tale metrica rappresenta una misura che ci permette di valutare la "bontà" delle diverse soluzioni possibili.

Consideriamo l'esempio concreto di voler trovare il percorso più breve per andare da una città A ad una città B.

É un problema comune affrontato quotidianamente da navigatori satellitari e app di mappe. In generale ci potrebbero essere diversi percorsi possibili per andare da A a B.

Per valutarli occorre definire una metrica, ad esempio il numero di chilometri da fare o il tempo di percorrenza.

L'obiettivo del problema di ottimizzazione è trovare, tra tutti i percorsi possibili, quello che ottimizza questa metrica.

"Ottimizzare" può significare:

1. minimizzare una quantità come il numero di chilometri o il tempo di percorrenza. Ad esempio, trovare il percorso con meno chilometri, anche se potrebbe richiedere più tempo a causa del traffico o trovare il percorso che richiede meno tempo, anche se si percorre più strada

2. massimizzare una quantità come nel caso degli investimenti: dato un budget, vogliamo scegliere gli investimenti che ne massimizzano il profitto.

Sono spesso legati a problemi di pianificazione o scheduling, dove dobbiamo distribuire risorse o ordinare attività per massimizzare profitti o minimizzare costi e tempi di esecuzione.

In sintesi nei problemi di ottimizzazione, vogliamo trovare la SOLUZIONE MIGLIORE secondo una data metrica (minimizzando o massimizzando un qualcosa).

Ma perchè è così importante questa classificazione?

Capire in quale categoria rientra un problema è il primo passo per affrontarlo in modo efficace.

Algoritmi e tecniche di risoluzione che funzionano bene per un problema di ricerca potrebbero non essere adatti per uno di ottimizzazione e viceversa. Questa distinzione ci guida nella scelta degli strumenti e delle strategie più appropriate.

[VIDEO YOUTUBE]

[PODCAST]