Appunti Intelligenza Artificiale PDF

Fondamenti di Intelligenza Artificiale - Appunti e Note Prof. Fabio Palomba 1 Introduzione all’Intelligenza Artificiale L’Intelligenza Artificiale (IA) è un campo della scienza che mira a creare sistemi in grado di eseguire compiti che richiedono intell...

Fondamenti di Intelligenza Artificiale - Appunti e Note Prof. Fabio Palomba 1 Introduzione all’Intelligenza Artificiale L’Intelligenza Artificiale (IA) è un campo della scienza che mira a creare sistemi in grado di eseguire compiti che richiedono intelligenza umana. Il suo sviluppo ha portato innovazioni in numerosi settori, dall’automazione industriale alla personalizzazione di contenuti nei social media. Esempi di applicazioni comuni includono: Google Maps: Fornisce percorsi ottimizzati tenendo conto del traffico in tempo reale. Sistemi di raccomandazione: Utilizzati da piattaforme come Netflix o YouTube per sug- gerire contenuti personalizzati. L’IA è sviluppata per migliorare diversi aspetti della vita e della società, risolvendo problemi complessi che sono difficili da affrontare manualmente. Le motivazioni principali per lo sviluppo di IA includono: Ottimizzazione delle risorse: Permettere una gestione più efficiente delle risorse. Velocità di apprendimento: Creare sistemi che imparano e si adattano più velocemente rispetto agli esseri umani. Risoluzione di problemi complessi: Affrontare sfide che richiederebbero troppo tempo e risorse per essere risolte dagli esseri umani. Curiosità scientifica: Spingere i confini della conoscenza su come l’intelligenza può essere simulata o replicata artificialmente. 1.1 Definizioni di Intelligenza Artificiale L’IA può essere definita in diversi modi, in base a ciò che si intende per “intelligenza”. Esistono quattro principali approcci, ciascuno con una diversa enfasi: Pensare umanamente: L’obiettivo è simulare i processi cognitivi umani, utilizzando tec- niche come la modellazione cognitiva. Si tenta di riprodurre i meccanismi del cervello umano, spesso tramite studi psicologici e neuroscienze. Pensare razionalmente: Questo approccio si concentra sul pensiero logico e deduttivo, cercando di costruire sistemi che seguano regole formali della logica per risolvere problemi. La logica formale è usata come base per la creazione di algoritmi intelligenti.  Agire umanamente: L’IA viene progettata per replicare il comportamento umano. Questo approccio è alla base del Test di Turing, che misura l’intelligenza di una macchina sulla base della sua capacità di imitare un comportamento umano in un’interazione. Agire razionalmente: L’approccio degli agenti razionali si concentra sulla creazione di agenti che agiscono in modo ottimale, basandosi sulle informazioni a loro disposizione. L’obiettivo è prendere decisioni razionali per raggiungere un obiettivo specifico, indipenden- temente dal fatto che tali azioni simulino o meno il pensiero umano. 1.2 Il Test di Turing Il Test di Turing, proposto da Alan Turing nel 1950, è uno dei primi tentativi di definire un crite- rio per l’intelligenza artificiale. Il test si basa su un esperimento chiamato gioco dell’imitazione. Durante il test, una persona (interrogatore) interagisce con una macchina e un altro essere umano tramite una tastiera o altri mezzi di comunicazione che escludono l’elemento visivo. L’interrogatore pone domande sia alla macchina che all’essere umano e deve determinare quale dei due è la macchina. Se l’interrogatore non riesce a distinguere tra la macchina e l’umano in un numero significativo di casi, allora si dice che la macchina ha passato il Test di Turing e può essere consid- erata intelligente. Il Test di Turing ha avuto un impatto profondo sulla filosofia e sullo sviluppo dell’Intelligenza Artificiale (IA). Le implicazioni del test sono molteplici e riguardano sia l’aspetto tecnico che quello etico e filosofico della definizione di intelligenza. 1. Definizione comportamentale di intelligenza Il Test di Turing si basa su una definizione di intelligenza puramente comportamentale. Non si interessa di come la macchina arrivi alle risposte, né della sua capacità di comprendere veramente il contenuto delle sue risposte. Se la macchina può rispondere in modo indistinguibile da un essere umano, si assume che essa sia intel- ligente. Questo criterio comportamentale ha implicazioni significative: Non richiede alla macchina di simulare esattamente i processi cognitivi umani, ma solo di imitare il comportamento umano. Introduce una forma pragmatica di intelligenza, in cui ciò che conta non è la natura del pensiero, ma l’effetto che esso ha sulle interazioni esterne. 2. Imitazione vs Comprensione Uno dei principali punti di discussione riguardanti il Test di Turing è la distinzione tra imitazione e comprensione. Il test valuta la capacità di una macchina di imitare un comportamento intelligente, ma non fornisce alcuna indicazione sul fatto che la macchina comprenda realmente ciò che sta facendo. Questo ha generato diversi dibattiti su temi, come da esempio quelli proposti di seguito: IA forte vs IA debole: L’IA forte sostiene che le macchine possano sviluppare una vera intelligenza, simile a quella umana, mentre l’IA debole suggerisce che le macchine possono solo imitare l’intelligenza senza comprenderla realmente. 2  Il paradosso della simulazione: È possibile che una macchina sembri intelligente senza es- serlo davvero? Se una macchina può simulare perfettamente l’intelligenza umana, ciò significa che è effettivamente intelligente o è solo un’imitazione sofisticata? 3. Limiti del Test di Turing Sebbene il Test di Turing sia stato influente, presenta alcuni rilevanti limiti, tra cui: Superficialità delle risposte: Il test misura solo l’abilità della macchina di rispondere in modo convincente, senza prendere in considerazione la profondità o la complessità del ragionamento dietro le risposte. Non misura la comprensione: Il test non valuta la capacità della macchina di comprendere concetti, emozioni o contesti. Un sistema basato su risposte predefinite potrebbe superare il test senza ”pensare” in modo autonomo. Critica di Searle: John Searle, nel suo famoso argomento della stanza cinese, ha contestato il Test di Turing affermando che una macchina può manipolare simboli senza capire il loro significato. Questo suggerisce che la macchina non possieda una vera comprensione, anche se supera il Test di Turing. 4. Implicazioni etiche e filosofiche Il Test di Turing ha sollevato questioni etiche e filosofiche riguardanti l’intelligenza artificiale: Responsabilità delle macchine: Se una macchina può comportarsi in modo intelligente, chi è responsabile delle sue azioni? Quali sono i limiti dell’autonomia delle macchine? Status delle macchine: Se una macchina supera il Test di Turing, possiamo considerarla come avente uno status simile a quello umano? Può una macchina avere diritti o responsabilità etiche? Conseguenze per la natura dell’intelligenza: Il Test di Turing pone la domanda su cosa significhi davvero essere intelligenti. Se l’intelligenza è definita dal comportamento es- terno, allora le macchine potrebbero già essere ”intelligenti” in alcuni contesti. Tuttavia, se l’intelligenza implica comprensione e coscienza, il test potrebbe non essere sufficiente per definire l’intelligenza. 5. Influenza sulla ricerca IA Il Test di Turing ha avuto un impatto significativo sulla ricerca nel campo dell’IA, orientando l’attenzione degli scienziati verso lo sviluppo di sistemi capaci di imitare il comportamento umano. Tuttavia, con il tempo, la comunità scientifica ha iniziato a spostarsi verso altri criteri più pratici e misurabili di intelligenza, come la razionalità degli agenti e la capacità di risolvere problemi complessi in modo efficiente. Il test ha comunque aperto la strada a questioni più profonde sulla relazione tra comportamento esterno e processi interni di pensiero. 3 1.3 Dall’imitazione alla razionalità: perché si passa da un approccio all’altro Nel corso degli anni, si è osservato un passaggio dall’approccio di imitare il comportamento umano (come nel Test di Turing) a quello di costruire agenti razionali che prendono decisioni ottimali. Questo passaggio è motivato da diverse ragioni: Limitazioni nel replicare l’intelligenza umana: Gli sforzi iniziali si concentravano sullo studio di come gli esseri umani pensano e agiscono. Tuttavia, l’intelligenza umana è complessa e difficile da replicare fedelmente, in quanto include emozioni, intuizioni e altri processi difficili da modellare. Focalizzazione sull’efficienza e l’ottimizzazione: Man mano che l’IA ha trovato appli- cazione in problemi complessi del mondo reale, come la pianificazione e l’ottimizzazione, l’enfasi si è spostata dalla semplice imitazione del comportamento umano all’efficienza e all’ottimizzazione del processo decisionale. Questo ha portato allo sviluppo degli agenti razionali, che agiscono in modo ottimale in base alle informazioni disponibili. Risultati pratici migliori: Costruire sistemi basati sul pensiero razionale e sulla logica formale ha prodotto risultati più concreti e utilizzabili in contesti pratici. Gli agenti razionali possono essere impiegati per risolvere problemi complessi, come il routing su reti di grandi dimensioni, con un’efficacia molto maggiore rispetto agli approcci che cercano di imitare il pensiero umano. Flessibilità: Gli agenti razionali sono più flessibili in quanto non devono simulare esatta- mente il comportamento umano. Possono agire in modi che gli esseri umani non consider- erebbero, purché il risultato sia ottimale. Questo li rende più adatti a risolvere problemi di ottimizzazione e pianificazione su larga scala. L’evoluzione della definizione di IA riflette la transizione da un focus sull’imitazione del pensiero umano verso un’enfasi sull’azione razionale. Questo cambiamento ha portato a significativi progressi nell’efficacia e nell’efficienza degli algoritmi di IA, consentendo loro di risolvere problemi complessi in diversi settori industriali e scientifici. 4 2 Agenti Intelligenti Un agente è un sistema che percepisce l’ambiente circostante tramite sensori e agisce su di esso tramite attuatori. Gli agenti possono essere classificati in diverse categorie a seconda delle loro capacità e del contesto in cui operano. Gli agenti possono essere: Umani: I sensori includono occhi, orecchie, ecc.; gli attuatori includono mani, gambe, tratto vocale, ecc. Robotici: I sensori includono telecamere e telemetri; gli attuatori includono motori e bracci meccanici. Software: I sensori includono input da tastiere, contenuti di file, pacchetti di rete; gli attua- tori includono la visualizzazione delle informazioni, la modifica di file e l’invio di pacchetti di rete. 2.1 Comportamento di un Agente Il comportamento di un agente è descritto da una funzione agente, che mappa una sequenza di percezioni in una specifica azione. In altre parole, la funzione agente determina l’azione che l’agente esegue in base a ciò che ha percepito. Questo può essere rappresentato matematicamente come: Funzione Agente : P → A dove P è l’insieme delle percezioni e A è l’insieme delle azioni. La funzione agente è implementata da un programma agente, che riceve come input la percezione corrente e restituisce un’azione da eseguire. 2.2 Agenti Razionali Un agente razionale è un agente che, per ogni sequenza di percezioni, sceglie l’azione che mas- simizza il valore atteso della sua misura di prestazione, date le informazioni a sua disposizione. La razionalità di un agente dipende da: La misura di prestazione adottata. La conoscenza pregressa dell’agente sull’ambiente. Le azioni che l’agente può compiere. La sequenza di percezioni ricevute fino al momento attuale. Nota: La razionalità non implica onniscienza. Un agente razionale non conosce il risultato ef- fettivo delle sue azioni, ma agisce sulla base delle informazioni che ha. Per migliorare la propria 5 razionalità, un agente può intraprendere azioni di information gathering, ovvero azioni final- izzate alla raccolta di nuove informazioni sull’ambiente circostante. Ad esempio, un agente può esplorare l’ambiente sconosciuto per ottenere una migliore comprensione e prendere decisioni più informate. Un agente può migliorare la propria capacità di compiere azioni razionali attraverso l’apprendimento. Questo consente all’agente di adattarsi a nuovi ambienti o situazioni in base alle esperienze passate, migliorando le proprie prestazioni. 2.3 Struttura di un Agente La struttura di un agente può essere descritta come una combinazione di: Architettura: L’hardware o la piattaforma su cui l’agente opera (ad esempio, un computer con sensori e attuatori). Programma agente: Implementa la funzione agente e decide l’azione da eseguire in base alla percezione corrente. L’obiettivo principale della progettazione di agenti intelligenti è creare programmi che producano comportamento razionale con il minor numero di regole o codice. 2.4 Tipi di Agenti Esistono vari tipi di agenti intelligenti, ognuno con capacità diverse: Agenti Reattivi Semplici: Questi agenti intraprendono azioni basate esclusivamente sulla percezione corrente, ignorando la storia percettiva. Ad esempio, un agente può eseguire una semplice regola condizionale: ”se rilevi sporco, allora pulisci”. Agenti Reattivi Basati su Modello: Questi agenti hanno un modello interno dell’ambiente, che permette loro di tenere traccia dello stato del mondo e prevedere l’effetto delle proprie azioni. Agenti Basati su Obiettivi: A differenza degli agenti reattivi, questi agenti prendono decisioni basate su specifici obiettivi che desiderano raggiungere. Pianificano le azioni in base a come le loro scelte influenzeranno il raggiungimento degli obiettivi. Agenti Basati sull’Utilità: In aggiunta agli obiettivi, questi agenti utilizzano una funzione di utilità per misurare la ”desiderabilità” di uno stato, permettendo loro di scegliere tra obiettivi contrastanti in modo ottimale. Agenti che Apprendono: Questi agenti migliorano continuamente le loro prestazioni grazie all’apprendimento, modificando il proprio comportamento in base al feedback ricevuto dalle loro azioni. 6 2.5 PEAS: Definizione degli Agenti Un ambiente può essere descritto utilizzando la struttura PEAS (Performance, Environment, Ac- tuators, Sensors): P (Performance): La misura di prestazione adottata per valutare l’operato dell’agente. E (Environment): L’ambiente in cui l’agente opera. A (Actuators): Gli attuatori a disposizione dell’agente per eseguire azioni. S (Sensors): I sensori utilizzati dall’agente per percepire l’ambiente. 2.6 Proprietà degli Ambienti Gli ambienti in cui operano gli agenti possono essere caratterizzati da diverse proprietà: Completamente osservabile vs Parzialmente osservabile: Se l’agente ha accesso a tutte le informazioni rilevanti sull’ambiente o solo a una parte di esse. Deterministico vs Stocastico: Se le azioni dell’agente determinano completamente lo stato successivo dell’ambiente o se ci sono elementi di casualità. Episodico vs Sequenziale: Se le decisioni dell’agente sono prese indipendentemente per ciascun episodio o se ogni azione influenza gli stati futuri. Statico vs Dinamico: Se l’ambiente cambia mentre l’agente sta deliberando o se rimane invariato. Discreto vs Continuo: Se l’ambiente fornisce un numero limitato di percezioni e azioni o se le percezioni e azioni sono continue. Singolo agente vs Multi-agente: Se l’agente opera da solo o in presenza di altri agenti con cui può collaborare o competere. Gli agenti intelligenti sono il cuore dell’Intelligenza Artificiale. Essi sono progettati per interagire con l’ambiente, prendere decisioni razionali e adattarsi a nuove situazioni grazie all’apprendimento. La varietà di agenti e di ambienti in cui operano rende l’IA una disciplina dinamica e ricca di sfide. 7 3 Formulazione di Problemi Di seguito, alcune note ed osservazione rispetto la formulazione di problemi. Il materiale non è esaustivo, ma vuole essere un supporto allo studio individuale. Pertanto, la sola lettura di questo documento è sconsigliata. 3.1 Agenti Basati su Obiettivi Un agente basato su obiettivi agisce nell’ambiente per raggiungere uno stato desiderato. Questi agenti non si limitano a rispondere a stimoli immediati, ma pianificano sequenze di azioni in base agli obiettivi da raggiungere. Funzionamento. Quando l’agente deve raggiungere un obiettivo complesso, valuta l’effetto delle proprie azioni sul mondo. La domanda che guida la sua decisione è: “Cosa accadrà se compio l’azione A? Sarò soddisfatto se lo faccio?”. Flessibilità: Questo tipo di agente è flessibile perché la conoscenza può essere modificata e adattata. Gli agenti reattivi, al contrario, richiedono una riscrittura delle regole condizione- azione ogni volta che cambia il contesto. 3.2 Rappresentazione Atomica degli Stati Nel contesto degli agenti risolutori di problemi, lo stato del mondo viene rappresentato in modo atomico. Ciò significa che ogni stato è considerato indivisibile e privo di struttura interna. Esempio. Un agente che cerca di viaggiare da una città all’altra considera ogni città come uno stato, senza analizzare le caratteristiche interne di ciascuna città. 3.3 Formulazione di Problemi La formulazione di un problema in AI è un passaggio cruciale per identificare le azioni che l’agente deve compiere per raggiungere un obiettivo. Il processo di formulazione comprende: Stato Iniziale. Punto di partenza dell’agente. Ad esempio, nel problema del viaggio in Romania discusso nel libro di testo e durante la lezione, lo stato iniziale potrebbe essere “in(Arad)”. Azioni. Insieme di azioni applicabili in ogni stato. Ad esempio, “Go(Sibiu)”, “Go(Timisoara)”. Modello di Transizione. Definisce come ogni azione modifica lo stato. Ad esempio, eseguire “Go(Zerind)” nello stato “in(Arad)” porterà allo stato “In(Zerind)”. 8  Test Obiettivo. Verifica se uno stato raggiunge l’obiettivo. Ad esempio, lo stato finale può essere “In(Bucarest)”. Costo di Cammino. Funzione che calcola il costo per passare da uno stato all’altro. 3.4 Algoritmi di Ricerca La risoluzione dei problemi tramite ricerca prevede che l’agente individui una sequenza di azioni che porti dallo stato iniziale allo stato obiettivo. Gli algoritmi di ricerca seguono tre fasi principali: Formulazione del problema. Il problema deve essere descritto formalmente, identificando le componenti che ne caratterizzeranno l’ambiente di esecuzione, ovvero quindi le componenti descritte in Sezione 3.3. Ricerca di una soluzione. Una volta formulato il problema, l’agente deve trovare una sequenza di azioni che porti dallo stato iniziale allo stato obiettivo. Esistono diversi approcci per la ricerca, tra cui, ad esempio: – Ricerca non informata. L’agente esplora lo spazio degli stati senza alcuna conoscenza a priori sull’obiettivo. Esempi sono la ricerca ad ampiezza e la ricerca in profondità. – Ricerca informata. L’agente utilizza delle euristiche per guidare la ricerca. Un esempio è l’algoritmo A*, che usa una funzione di valutazione per stimare il costo totale dal nodo attuale all’obiettivo. Esecuzione della sequenza di azioni. Una volta trovata la sequenza di azioni che conduce all’obiettivo, l’agente la esegue per raggiungere lo stato desiderato. Se la soluzione trovata è subottimale, l’agente potrebbe dover riformulare il problema o rieseguire la ricerca. Durante l’esecuzione delle azioni, l’agente ignora le sue percezioni perché ha già calcolato la sequenza completa in anticipo. Questo tipo di comportamento è detto a ciclo aperto, poiché l’agente non aggiorna il suo stato in base a nuove informazioni dall’ambiente. Questo approccio fun- ziona solo in ambienti deterministici e completamente osservabili, dove ogni azione ha un unico risultato e l’agente può prevedere con esattezza gli effetti delle sue azioni. Tuttavia, se l’ambiente fosse stocastico o parzialmente osservabile, dove le azioni possono avere risultati in- certi o le percezioni non riflettono completamente lo stato del mondo, l’agente avrebbe bisogno di un approccio a ciclo chiuso. In questo caso, l’agente aggiornerebbe costantemente la sua conoscenza dell’ambiente in base alle nuove percezioni e potrebbe ricalcolare le azioni neces- sarie per raggiungere l’obiettivo, adattando la sequenza di azioni durante l’esecuzione. Questo lo renderebbe più flessibile e capace di rispondere ai cambiamenti imprevisti nell’ambiente. 3.5 Un esempio: Formulazione del Problema delle 8 Regine Il problema delle 8 regine richiede di piazzare 8 regine su una scacchiera in modo che nessuna possa attaccarne un’altra. Esistono due principali formulazioni di questo problema, ognuna con implicazioni diverse in termini di complessità computazionale. 9 Il primo modo di definire il problema è tramite una formulazione incrementale. In particolare, il problema sarebbe descritto come segue: Descrizione. Si aggiungono progressivamente le regine sulla scacchiera, cominciando dallo stato vuoto. Ogni stato corrisponde a una scacchiera con un numero crescente di regine. Azioni: Piazzare una regina in una casella vuota. Complessità: Questa formulazione esplora uno spazio di ricerca molto ampio, in quanto non impone vincoli immediati sul posizionamento delle regine. La ricerca dovrà esaminare circa 1.8 × 1014 possibili configurazioni per trovare una soluzione valida. Svantaggi: La mancanza di vincoli rende questa formulazione molto inefficiente per problemi con molti stati, come il problema delle 8 regine. Il numero di combinazioni da esaminare può crescere rapidamente, rendendo la ricerca complessa e lunga. In alternativa, potremmo descrivere il problema tramite una formulazione a stato completo. Quindi: Descrizione: In questa formulazione, tutte le regine sono già piazzate sulla scacchiera, e il compito è spostarle in modo che nessuna minacci un’altra. Azioni: Spostare una regina all’interno della colonna in cui si trova, se minacciata. Complessità: Questa formulazione riduce drasticamente lo spazio di ricerca. Invece di esplorare tutte le possibili configurazioni, si esaminano solo configurazioni in cui ogni regina è già piazzata in una colonna separata. La complessità scende a circa 1.6 × 107 possibili configurazioni, rendendo la ricerca molto più gestibile. Vantaggi: Ridurre lo spazio di ricerca tramite vincoli (come il fatto che le regine si trovino in colonne diverse) rende questa formulazione più efficiente. Tuttavia, anche in questo caso, per problemi con N regine, la complessità può aumentare significativamente (ad esempio, con N = 100, lo spazio di ricerca raggiunge 1052 stati). Altri esempi di problemi di ricerca sono: Problema del Commesso Viaggiatore: Ottimizzare un percorso che visiti una serie di città una sola volta minimizzando la distanza complessiva. Questo è un esempio di un prob- lema di ottimizzazione NP-completo, in cui lo spazio di ricerca cresce esponenzialmente con il numero di città. Problemi di Navigazione Robotica: Estensione del problema di ricerca di percorsi a spazi continui e multidimensionali, come nel caso di robot dotati di braccia o gambe, che richiedono il controllo di movimenti complessi. Anche qui, la definizione corretta del problema e l’uso di astrazioni riduce la complessità della ricerca. 10 4 Algoritmi di Ricerca Non Informata Nella lezione precedente abbiamo discusso la formulazione dei problemi di ricerca. In questa lezione, ci concentreremo sugli algoritmi di ricerca non informata, che non dispongono di informazioni ag- giuntive sugli stati oltre a quella fornita dalla definizione del problema. Gli algoritmi di ricerca operano cercando una sequenza di azioni che porti dallo stato iniziale all’obiettivo. Durante la ricerca, viene costruito un albero di ricerca, con lo stato iniziale come radice e le azioni che espan- dono i rami. 4.1 Ricerca di Soluzioni Una soluzione è una sequenza di azioni. Gli algoritmi di ricerca non informata seguono queste fasi: Espansione: Espandere uno stato significa applicare le azioni per ottenere nuovi stati. Frontiera: L’insieme di tutti i nodi foglia che possono essere espansi costituisce la frontiera. Cammini ciclici: Uno stato può essere ripetuto più volte, causando cicli, il che potrebbe portare a fallimenti in alcuni algoritmi. Sulla base di questa definizione, un algoritmo di ricerca ad albero può essere rappresentato in termini di questo pseuso-codice: function RICERCA-ALBERO(problema, strategia) returns una soluzione o fallimento inizializza la frontiera usando lo stato iniziale di problema loop do if la frontiera è vuota then return fallimento scegli un nodo foglia in base a strategia e rimuovilo dalla frontiera if il nodo contiene uno stato obiettivo then return la soluzione corrispondente espandi il nodo scelto, aggiungendo i nodi risultanti alla frontiera Un miglioramento dell’algoritmo di ricerca consiste nell’introduzione di un insieme esplorato per evitare la ripetizione di stati già visitati. function RICERCA-GRAFO(problema, strategia) returns una soluzione o fallimento inizializza la frontiera usando lo stato iniziale di problema inizializza a vuoto l’insieme esplorato loop do if la frontiera è vuota then return fallimento scegli un nodo foglia e rimuovilo dalla frontiera if il nodo contiene uno stato obiettivo then return la soluzione corrispondente aggiungi il nodo all’insieme esplorato espandi il nodo scelto, aggiungendo i nodi risultati alla frontiera solo se non sono nella frontiera o nell’insieme esplorato 11 4.2 Strategie di Ricerca Non Informata Le principali strategie di ricerca non informata includono: Ricerca in ampiezza: Espande prima i nodi di profondità minore. Ricerca a costo uniforme: Espande il nodo con il minor costo di cammino. Ricerca in profondità: Espande il nodo più profondo prima di tornare indietro. Ricerca in profondità limitata: Limita la profondità della ricerca per evitare cicli infiniti. Ricerca ad approfondimento iterativo: Combina la ricerca in ampiezza con la ricerca in profondità limitata, aumentando progressivamente il limite di profondità. Ricerca bidirezionale: Esegue una ricerca simultanea dallo stato iniziale e dall’obiettivo. Di seguito vengono descritti i principali algoritmi di ricerca non informata trattati durante il corso. Gli appunti descrivono il funzionamento generale, lo pseudocodice, ma anche i principali vantaggi e svantaggi di ognuno di essi. Al termine, troverete anche un quiz tramite il quale potervi esercitare per la prova di esame. 4.2.1 Ricerca in Ampiezza (Breadth-First Search) La ricerca in ampiezza esplora gli stati a partire dalla radice espandendo tutti i nodi a una de- terminata profondità prima di passare alla successiva. Viene utilizzata una coda FIFO (First-In, First-Out) per garantire che i nodi più vicini alla radice siano espansi per primi. Pro: Completo: Trova sempre una soluzione se questa esiste. Ottimo: Trova la soluzione più breve in termini di numero di passaggi (quando il costo di cammino è uniforme). Contro: Complessità spaziale: Richiede molta memoria per mantenere tutti i nodi della frontiera (O(bd ), dove b è il fattore di ramificazione e d la profondità della soluzione). Complessità temporale: Il tempo necessario è esponenziale rispetto alla profondità della soluzione (O(bd )). 12 Esempio di Utilizzo: Utile: Per problemi in cui la soluzione è vicina allo stato iniziale, come la risoluzione di puzzle con poche mosse richieste. Non utile: In problemi con un fattore di ramificazione elevato, come la ricerca di un percorso in una mappa complessa. Pseudocodice: function RICERCA-IN-AMPIEZZA(problema) nodo