L'orario scolastico - Un problema intelligente adatto all'intelligenza

Che titolo per un articolo!?!?

Il primo anno che ho fatto l'orario in una scuola tutti mi dicevano che non poteva esistere un software per trovare un buon orario scolastico, che non poteva esistere un software che tenesse conto di tutti i vincoli, che non poteva esistere un software che ragionasse come un essere umano e che tenesse conto di tutti i fattori in gioco. Beh, dopo un po' di anni ho scoperto che non avevano così tanto torto.

Però prima di continuare sgombriamo il campo da dubbi: io uso un software per trovare l'orario scolastico, a mano non saprei da che parte iniziare e, soprattutto, mi farebbe impazzire l'idea che qualche specifica o qualche vincoli cambi all'ultimo minuto - e capita, ve l'assicuro - così da obbligarmi a rifare parte o tutto l'orario il giorno prima dell'inizio dell'anno scolastico.

D'altra parte, prima di scrivere questi articoli, ed in particolare proprio questo, mi sono voluto un po' documentare. Abbiamo già detto che il problema della ricerca di un orario scolastico è un problema che appartiene alla classe dei problemi detti Problemi di Soddisfacimento di Vincoli o CSP. 

Purtroppo non esiste una tecnica che dato questo tipo di problemi trova una soluzione tramite un calcolo più o meno complicato. Esistono, viceversa, algoritmi ricorsivi per la ricerca della soluzione. Uno di questi è ad esempio l'algoritmo Backtracking. Si cominciano ad assegnare le variabili in gioco in modo più o meno casuale (oppure seguendo euristiche di qualche genere) in modo tale che rispettino tutti i vincoli finché non si arriva ad una variabile che non si riesce ad assegnare, perché a prescindere da quale valore le diamo un vincolo non viene soddisfatto. Allora si va all'ultima variabile assegnata e che non ha infranto vincoli e le si dà un altro valore sempre con la condizione che rispetti i vincoli e si continua la ricerca. Le scelte vengono immagazzinate in un albero che tiene conto di tutte le opzioni visitate.

Per come è fatto l'algoritmo è però possibile imboccare vie sbagliate che obbligano a risalire l'albero anche più volte. Per esempio se la prima variabile che si assegna la si assegna in modo tale che non esiste alcuna soluzione con quel valore (e io a priori non lo posso sapere) l'algoritmo dovrà fare molte esplorazioni e ricorsioni prima di arrivare alla conclusione che quell'assegnazione è sbagliata. So di non essere precisissimo, però come più volte ho accennato l'obiettivo di questi miei articoli è di far comprendere appieno le problematiche.

E qui il problema è grande: gli algoritmi che permettono di trovare l'orario scolastico sono ricorsivi, cioè devono fare tanti tentativi prima di trovare una soluzione ed il numero di tentativi cresce in modo esponenziale al crescere dei vincoli.

Ho trovato un esempio per farsi un'idea di quanto tempo potrebbe volerci per trovare un orario scolastico (http://it.wikibooks.org/wiki/Costruire_un_orario_scolastico):

Supponiamo di avere una scuola con 40 classi, e con 30 ore settimanali ciascuna, un programma per generare l’orario scolastico attraverso una tecnica ricorsiva dovrebbe esaminare ogni disposizione di 30 ore su 40 classi e su un buon comupter ci metterebbe circa 1000000000000000000000000000000000000000000 anni!!!

Ed eccoci arrivati alla conclusione da cui scaturisce il titolo dell'articolo: è dimostrato che le tecniche informatiche migliori per affrontare questo tipo di problemi sono tecniche che richiedono l'impiego dell'intelligenza artificiale, cioè tecniche che emulano le capacità di ragionamento e di sintesi del cervello umano.

Un po' di link per approfondire:
http://it.wikibooks.org/wiki/Costruire_un_orario_scolastico
http://it.wikipedia.org/wiki/Backtracking