Esplorazione casuale

L'esplorazione casuale è una tecnica di indagine in un ambiente ignoto. È conosciuta anche come random walk. In un ambiente ignoto o parzialmente osservabile l'agente razionale esplora gli stati dell'ambiente intorno a sé in modo casuale. La scelta del passo successivo è determinata dalla casualità ( random ) senza seguire una euristica o una logica particolare. Passeggiando in modo casuale l'agente raggiunge comunque l'obiettivo. Nel seguente esempio l'agente si trova nel nodo A e ha l'obiettivo di trovare la cella O. Non conosce l'ambiente intorno a sé, quindi sceglie a caso una direzione. Ha quindi la medesima probabilità ( 25% ) di scegliere B, C, D o E.

L'esplorazione casuale è utilizzata prevalentemente nella ricerca locale online e nella ricerca online per l'esplorazione di un ambiente parzialmente osservabile in assenza di altre informazioni disponibili.

Inefficienza. Pur essendo una tecnica di ricerca molto semplice e poco impegnativa di un ambiente ignoto, l'esplorazione casuale è fortemente inefficiente poiché l'agente razionale può visitare più volte gli stessi stati del mondo senza seguire nessuna logica o strategia di ricerca.

Ambiente non sicuro. Quando l'ambiente operativo non è sicuro, l'esplorazione reale comporta un elevato rischio di cadere in una mossa irreversibile o in una situazione di impasse ( vicolo cieco ).

Struttura del problema. In alcuni casi la struttura del problema potrebbe concentrare la passeggiata soltanto in alcuni stati del mondo a scapito degli altri. In tali casi, la ricerca casuale la complessità della ricerca casuale aumenta in modo crescente. Ad esempio, nel seguente caso i nodi agli angoli ( nodi di colore rosso ) hanno una minore probabilità di essere esplorati rispetto agli altri nodi in quanto la rete tra i nodi è molto più fitta al centro rispetto all'esterno. Il tempo dell'esplorazione completa dell'ambiente è molto più lungo.

Euristica. Per migliorare l'efficienza dell'esplorazione casuale è necessario integrare nell'algoritmo di ricerca una funzione euristica e una capacità di memoria al fine di consentire di tenere traccia dei nodi ancora da osservare