Stato del mondo in giochi e algoritmi

Podcast Beta

Play an AI-generated podcast conversation about this lesson

Questions and Answers

Quale delle seguenti affermazioni riguarda le direzioni in cui l'agente può muoversi?

L'agente può muoversi solo in diagonale.

L'agente può muoversi in tutte le direzioni senza restrizioni.

Ci sono quattro direzioni possibili: Nord, Est, Sud, Ovest. (correct)

L'agente può muoversi solo orizzontalmente.

Qual è il numero totale di posizioni possibili per i fantasmi?

120

12 (correct)

Qual è la caratteristica principale degli agenti in un mondo a griglia?

Possono muoversi solo in diagonale.

Possono muoversi su celle adiacenti senza ostacoli. (correct)

Possono spostarsi in qualsiasi punto della griglia senza restrizioni.

Possono saltare sopra gli ostacoli.

Quale affermazione descrive in modo più accurato gli stati del mondo?

Stati del mondo sono influenzati da posizioni dell'agente, cibo, fantasmi e direzione. Signup and view all the answers

Quale tra le seguenti affermazioni è vera riguardo agli algoritmi di ricerca incompleti?

Eseguono percorsi infiniti senza completare la ricerca. Signup and view all the answers

Come si definisce un algoritmo di ricerca completo?

Raggiunge qualsiasi stato connesso allo stato iniziale. Signup and view all the answers

Qual è una misura tipica della complessità temporale in relazione agli spazi degli stati?

La dimensione del grafo dello spazio degli stati. Signup and view all the answers

Qual è un esempio di strategia di ricerca sistematica su una griglia infinita?

Ricerca a spirale. Signup and view all the answers

Cosa caratterizza un algoritmo di ricerca non informata?

Non ha indizi sulla distanza dall'obiettivo. Signup and view all the answers

Quale dei seguenti fattori definisce la complessità in uno spazio degli stati implicito?

Il numero massimo di azioni e il fattore di ramificazione. Signup and view all the answers

Qual è la difficoltà di un algoritmo valido su uno spazio degli stati infinito senza soluzione?

Deve continuare a cercare indefinitamente. Signup and view all the answers

Cosa comporta l'uso dell'operatore 'fattoriale' nel problema di Knuth?

Un percorso infinito da 4 a (4!)! Signup and view all the answers

Qual è la principale caratteristica della ricerca in ampiezza in termini di soluzioni?

Trova sempre una soluzione con il numero minimo di azioni. Signup and view all the answers

Qual è la complessità temporale e spaziale della ricerca in ampiezza?

O(b^d) Signup and view all the answers

Cosa implica il fatto che un nodo è generato durante la ricerca in ampiezza?

Deve essere testato se è una soluzione. Signup and view all the answers

Quale problema è evidenziato riguardo all'utilizzo della ricerca in ampiezza?

Ha limiti esponenziali che possono essere problematici. Signup and view all the answers

Qual è un fattore di ramificazione comune considerato in un problema di ricerca reale?

b = 10 Signup and view all the answers

Qual è l'effetto dell'aumento della profondità d in una ricerca in ampiezza?

Aumenta esponenzialmente il numero di nodi richiesti. Signup and view all the answers

Qual è uno dei requisiti di memoria per la ricerca in ampiezza con b = 10 e d = 10?

10 terabyte Signup and view all the answers

Per quali istanze la ricerca non informata è in grado di risolvere i problemi con complessità esponenziale?

Solo per le istanze più piccole. Signup and view all the answers

Quale affermazione è vera riguardo ai nodi con $f(n) < C^*$?

A* espande tutti i nodi che sono sicuramente espansi. Signup and view all the answers

Cosa significa che un'euristica è consistente in un algoritmo A?

Stabilisce relazioni di costo tra nodi. Signup and view all the answers

Qual è il ruolo del concetto di potatura nella ricerca A*?

Potare elimina possibilità dalla considerazione senza esaminarle. Signup and view all the answers

Quale affermazione sulla ricerca A* è corretta?

A* è sia completa che ottimale in termini di costo. Signup and view all the answers

Qual è la conseguenza di avere un costo del percorso di soluzione ottimale $C^*$?

Alcuni nodi con f(n) = C* possono essere espansi. Signup and view all the answers

Perché è importante la diminuzione di h in relazione al costo dell'azione intrapresa?

Mostra come ogni passo riduce la distanza dall'obiettivo. Signup and view all the answers

Qual è uno svantaggio della ricerca A* rispetto ad altri algoritmi?

Il numero di nodi espansi può essere esponenziale rispetto alla soluzione. Signup and view all the answers

Qual è una caratteristica di A* rispetto alla ricerca a costo uniforme?

A* evita di espandere nodi non necessari. Signup and view all the answers

Quale delle seguenti affermazioni descrive correttamente la ricerca a fascio?

Include solo i k migliori candidati nella sua espansione. Signup and view all the answers

Qual è la principale differenza tra IDA* e la ricerca a doppia profondità?

IDA* non usa memoria per mantenere stati già visitati. Signup and view all the answers

Quale affermazione è vera riguardo alla ricerca RBFS?

Ha come obiettivo il percorso alternativo se il nodo corrente supera il limite. Signup and view all the answers

Cosa determina il valore limite in un'iterazione di IDA*?

Il costo f più piccolo di un nodo oltre il limite dell'iterazione precedente. Signup and view all the answers

Qual è un aspetto chiave della ricerca RBFS?

Utilizza uno spazio lineare per la sua esecuzione. Signup and view all the answers

Quando si utilizza un approccio a costo uniforme nella ricerca, quali cerchi diversifica?

Tutti i cerchi concentrici. Signup and view all the answers

Qual è la condizione necessaria affinché RBFS sia considerata ottimale?

La funzione euristica deve essere ammissibile. Signup and view all the answers

Che ruolo gioca la variabile f_limit nella ricerca RBFS?

Determina quando abbandonare il percorso corrente. Signup and view all the answers

Study Notes

Lo stato del mondo

Questo documento descrive gli elementi che compongono lo "stato del mondo" in un gioco.
Lo spazio degli stati è composto da 120 possibili posizioni per l'agente, 30 variabili booleane per la presenza di cibo (2^30 possibilità), 12 posizioni per i fantasmi (12^2 possibilità) e 4 possibili direzioni per l'agente, per un totale di 120×(2^30)×(12^2)×4 stati del mondo.
Il calcolo considera solo le posizioni dell'agente per determinare i percorsi (ignorando cibo e fantasmi), ottenendo 120 possibili stati.
Se si considerano solo le posizioni dell'agente e la presenza di cibo, ignorando la posizione dei fantasmi e la direzione, si ottengono 120×(2^30) stati.

Spazio degli Stati Infiniti

Un problema di ricerca con uno spazio degli stati infinito può portare a un algoritmo che esplora in modo infinito senza mai tornare a uno stato già raggiunto.
Un algoritmo completo deve essere sistematico nell'esplorazione dello spazio degli stati, assicurandosi di poter raggiungere ogni stato connesso allo stato iniziale.
In uno spazio degli stati infinito senza soluzione, un algoritmo valido deve cercare per sempre, poiché non può sapere se il prossimo stato sarà un obiettivo.

Complessità Temporale e Spaziale

La complessità temporale e spaziale viene misurata in base alla dimensione del grafo dello spazio degli stati, rappresentato da ∣V∣+∣E∣, dove ∣V∣ è il numero di vertici (nodi degli stati) e ∣E∣ è il numero di archi (coppie stato/azione).
Per uno spazio degli stati implicito, la complessità può essere misurata in termini di profondità, numero di azioni in una soluzione ottimale (d), e fattore di ramificazione (m), ovvero il numero di successori di un nodo.

Ricerca Non Informata

La ricerca non informata non ha informazioni su quanto uno stato sia vicino all'obiettivo.
La ricerca in ampiezza trova sempre una soluzione con il numero minimo di azioni, ma non è ottimale per i problemi con azioni di costo variabile.
La complessità temporale e spaziale della ricerca in ampiezza è O(b^d), dove b è il fattore di ramificazione e d è la profondità della soluzione.
I problemi di ricerca esponenziale non possono essere risolti dalla ricerca non informata se non per le istanze più piccole.

Ricerca A*

A* utilizza una funzione euristica h(n) per stimare il costo di raggiungere l'obiettivo da uno stato n.
A* è completa, ottimale in termini di costo e ottimamente efficiente.
A* può comunque essere inefficiente per problemi con uno spazio degli stati molto grande.

Ricerca a Fascio

La ricerca a fascio espande solo una porzione dell'albero di ricerca, quella che contiene i k migliori candidati.
Una versione alternativa della ricerca a fascio mantiene tutti i nodi il cui punteggio f è entro δ dal miglior punteggio f.

Iterative-deepening A* (IDA*)

IDA* è un algoritmo che offre i vantaggi della ricerca A* senza dover mantenere tutti gli stati raggiunti in memoria.
In IDA*, il limite per la profondità è il costo f (g + h).

Recursive Best-first Search (RBFS)

RBFS imita la ricerca best-first search standard, ma utilizza uno spazio lineare.
RBFS mantiene una variabile f _limit per tenere traccia del valore f del miglior percorso alternativo disponibile da un antenato del nodo corrente.
RBFS è ottimale se la funzione euristica h(n) è ammissibile.

Studying That Suits You

Use AI to generate personalized quizzes and flashcards to suit your learning preferences.

Description

Questo quiz esplora i concetti relativi allo stato del mondo in un contesto di gioco. Vengono analizzati gli elementi costitutivi degli stati del mondo e le problematiche associate all'esplorazione di spazi di stati infiniti. Metodi e algoritmi per l'esplorazione vengono anche discussi.