Artificial intelligence - Intelligenza Artificiale

Strategie di ricerca informate

Le strategie di ricerca informate fanno uso di informazioni supplementari. L'idea è quella di usare una funzione di valutazione che, dato un nodo n, restituisce la valutazione di quel nodo, un indice di quanto buono è quel nodo. Per calcolare l'output di questa funzione, si utilizzano informazioni esterne alla formulazione del problema. Si sceglierà il nodo con la funzione di valutazione più bassa, pensandola come un costo, una stima del costo che devo sostenere per andare dal nodo n al nodo di goal. Questa funzione è chiamata funzione euristica.

Ad esempio, la stima del costo per andare da A al nodo goal è 3.

Attenzione: nella definizione, la funzione di valutazione era definita sui nodi, ma per semplicità viene definita sugli stati corrispondenti ai nodi.

Una delle strategie di ricerca informate è la strategia Best First Greedy. Per valutare un nodo nella frontiera, si utilizza proprio questa funzione di valutazione.

.AB CScelgo B perché è quello con la stima del costo minore → espando BAB CA E//l’euristica sullo stato finale si assume sempre pari a 0.Nella frontiera ho A=3, E=0, C=3Scelgo quello che vale meno, cioè E → è stato di goal → finish!L’idea è quindi quella di non valutare più i nodi in base alla loro profondità, ma sulla base di unafunzione euristica, quindi utilizzando informazione supplementare. Infatti è stata aggiunta,non c’era nella formulazione del problema originale.La ricerca best-first-greedy è completa? Dipende dall’euristica. Se h (A ) = 1 e h ( C ) = 1 etutte le altre = 100, continuo a saltare ACACACAC... → è non completa con ricerca albero, ècompleta con ricerca grafoE’ ottima?Complessità spaziale e temporale?07/04/11Strategie di ricerca informateLa Best First Greedy l’abbiamo vista la volta scorsa: ‘scegli i nodi dalla frontiera

1. stesso stato.Quindi le condizioni su h sono più stringenti perché devo garantire che il nodo scelto è quello buono!
2. h ammissibile
3. h consistente: cioè quando presa una coppia di nodi n, n' dove n' è un successore di n, allora vale la disuguaglianza triangolare: = costo per andare da n a n' ≤ costo per andare da n a n' tramite l'azione a (è ridondante). Ecco la disuguaglianza triangolare: h è definita sui nodi, ma per semplicità la definisco sugli stati. Es. trovo prima D, poi E che è successore → h(d) < 2 + h(e)
4. Se h è consistente allora h è ammissibile. Si dimostra per deduzione. E non è vero il contrario.
5. Se h è consistente e uso RICERCA GRAFO (ma anche RICERCA ALBERO) allora A* è ottima. Dimostrazione intuitiva... guardala sul libro. A* ricerca albero è ottima se h è ammissibile. A* ricerca grafo è ottima se h

è consistente (e anche con ricerca albero).A* è completa? SI trova addirittura la soluzione ottima! → SI tranne dei casi degeneri es. concosti pari a 0...etc etc.

Complessità:

• temporale: con “-” proporzionale a quanto h è precisa, più h si avvicina ad h*più “-” è piccolo e proporzionale alla lunghezza della soluzione. → E’ esponenziale nellaprecisione di h e nella lunghezza della soluzione. E’ ovvio che sia esponenziale.
• spaziale. Tutti i nodi vanno mantenuti in memoria → è uguale alla complessitàtemporale!

Ci sono delle versioni speciali che diminuiscono la complessità tamporale...

Si può dimostrare che:

• A* espande tutti i nodi con
• A* espande qualche nodo con
• A* espande nessun nodo con

Con C* il costo della soluzione ottima.

A* è ottimamente efficiente → non esiste nessun altra strategia che è garantita ottima su tutti iproblemi di ricerca

E che espanda meno nodi di A* a parità della funzione euristica. Non può trovare la soluzione senza espandere tutti quelli con f(n) < C*? No perché se non li espande tutti con f(n) < C* potrebbe perdere soluzioni ottime. E perché ne espande alcuni con f(n) = C*? Perché almeno uno è la soluzione. Non espande nessuno con f(n) > C* perché non ci porteranno mai alla soluzione ottima.

8/4/11 Esercitazione di Nicola Gatti ngatti@elet.polimi.it home.dei.polimi.it/ngatti

Esercizi sul sito.. il tipo si occupa di Microeconomia computazionale e teoria dei giochi

Spazio degli stati: insieme finito o infinito che può essere rappresentato con un grafo solo nel caso finito, dato che nel caso infinito la rappresentazione non sarà esaustiva.

Obiettivo: rappresenta il problema della ricerca ed è solitamente espresso da una coppia di stati: INIZIALE e FINALE.

Strategia di ricerca: dice come ci si deve muovere per arrivare alla soluzione.

• senza con eliminazione degli stati ripetuti (RICERCA-ALBERO)
• con eliminazione degli stati ripetuti (RICERCA-GRAFO)

Il costo spazio degli stati prevede cicli, l'algoritmo può non terminare. Con Ottimo se gli archi di eliminazione hanno la garanzia di avere tutti lo stesso costo ottimalità. E' garantita la terminazione dell'algoritmo.

ESERCIZIO DI RICERCA

Stato iniziale: A

Stato finale: I

Strategia in ampiezza e senza eliminazione degli stati ripetuti: Criterio di scelta: scelgo il nodo presente nella frontiera, a profondità minore nell'albero di ricerca.

Inserisco A nella frontiera; espando il nodo togliendo A (marcato con 1°) dalla frontiera; ora la frontiera contiene B E F. Estraggo B (che marco con 2°) e la frontiera diventa C E F; espando C (che marco con 3°) togliendolo dalla frontiera che ora sarà composta da A F G H E F; tolgo F che marco con 4° aggiungendo H alla frontiera dato che non è stato finale; espando C che marco con 5° ed espando i successori con D; espando A

marcando con 6° e inserisco di nuovoD E F

Lo stesso esercizio in ampiezza, ma con l’eliminazione degli stati ripetuti.

In questa tipologia oltre alla frontiera, c’è un insieme chiamato CHIUSO che contiene l’insieme degli stati che sono già stati visitati. Nel momento in cui si scopre che il nodo è stato visitato, il nodo viene marchiato e allo stesso tempo cancellato con una croce.

Lo stesso esercizio con ricerca in profondità e senza elimininazione.

Inserisco A che essendo da solo viene marcato con 1°. Espando e in frontiera si hanno B E F; prendo B che marco con 2°. In frontiera si hann