Risoluzione di problemi e intelligenza artificiale RISOLUZIONE DI PROBLEMI E INTELLIGENZA ARTIFICIALE. La risoluzione dei problemi comprende tutta l'informatica. I metodi di risoluzione dei problemi fanno uso del concetto di ricerca per tentativi, ricercando una soluzione in uno spazio di soluzioni possibili. Presentazione dei più importanti metodi di risoluzione di problemi basati sulla ricerca per tentativi. ROMPICAPO E GIOCHI COME ESEMPIO DI PROBLEMI Definizione di problemi mediante esempi. Il gioco del quindici. Questo gioco consiste di 15 tessere mobili numerate, inserite in un telaio 4x4. Una cella del telaio è sempre vuota, cosicché è possibile spostare una tessera numerata adiacente nella cella vuota. Il problema è di mutare la disposizione iniziale in quella finale con tutte le tessere poste in modo progressivo. STATI E OPERATORI DEI PROBLEMI Una soluzione nel gioco del quindici è di tentare varie mosse finché non capiti di ottenere la disposizione finale, un tentativo del genere implica essenzialmente una ricerca per tentativi. Per discutere i metodi risolutivi di questo tipo è utile introdurre la nozione di stato e operatore del problema. - Nel gioco del quindici uno stato del problema è semplicemente una particolare disposizione delle tessere. - Un operatore trasforma uno stato in un altro, nel gioco del quindici ci sono quattro operatori corrispondenti alle mosse: muovi lo spazio vuoto a sinistra, in alto, a destra, in basso. Lo spazio degli stati raggiungibili dallo stato iniziale consiste di tutte le disposizioni che si possono produrre movendo le tessere nel modo corretto.RIDUZIONE DI PROBLEMI A SOTTOPROBLEMI Un metodo di risoluzione di problemi un po' più raffinato richiede la nozione di sottoproblema. Per esempio, poniamoci il problema di dover guidare un'auto da Salerno a Milano. Il tutto si potrebbe ridurre ai seguenti sottoproblemi: guidare da Salerno a Napoli guidare da Napoli a Roma guidare da Roma a Milano La soluzione di tutti e tre i sottoproblemi produrrebbe la soluzione del problema originario. Possibilità di risolvere i sottoproblemi con un metodo qualsiasi. Si può affrontare con il metodo dello spazio degli stati o analizzarlo a sua volta in sottoproblemi. LA RAPPRESENTAZIONE E LA RICERCA I metodi di risoluzione che abbiamo menzionato richiedono un'azione di ricerca della soluzione. Quindi è indispensabile condurre tali ricerche nel modo più efficiente possibile. Lo stesso problema può ammettere diverse rappresentazioni, alcune delle quali con uno spazio degli stati molto più piccolo delle altre. Rappresentazioni nello spazio degli stati Descrizioni degli stati e della forma Definizioni degli operatori Definizione degli stati finali Descrizioni degli stati Un processo di risoluzione che trovi una soluzione descrittiva deve lavorare con una descrizione degli stati Formulazione di un problema Schematizzare gli stati del problema. Scegliere una particolare forma per la descrizione degli stati Scelta della forma Scelta Continua »