Algoritmo di ricerca online
Un algoritmo di ricerca online è un algoritmo di ricerca in grado di analizzare un flusso di dati in input in tempo reale ed elaborare un processo al fine di determinare un'azione/dato da restituire in output. Questa tipo di processo di elaborazione dell'algoritmo è detto online ossia "in linea" con il flusso dei dati ( grandezza di flusso ). L'algoritmo di ricerca online è particolarmente efficace negli ambienti operativi dinamici. I principali vantaggi di un algoritmo di ricerca online sono la velocità di restituzione del risultato in output e la necessità di disporre di uno spazio limitato di memoria. Ad esempio, in una tabella di 9 celle l'agente sa qual è la sua posizione iniziale ( A3 ) ma non conosce la mappa del luogo ( ambiente osservazione parziale ). Per conoscere l'ambiente deve necessariamente iniziare l'esplorazione. Per farlo inizia una ricerca in profondità a partire dalle scelte possibili ( A2 e B3 ). Inizia a esplorare A2 e aggiunge B3 nella coda dei percorsi ancora "da visitare". Al termine dell'esplorazione di A2 l'agente torna sui suoi passi ( back-tracking ) fino alla cella di origine ( A3 ) per poi cominciare l'esplorazione della cella B3 e così via...
L'elaborazione si interrompe quando l'agente si trova nella cella B1 poiché tale cella è l'obiettivo dell'algoritmo. È importante sottolineare che l'agente non può verificare se una cella è l'obiettivo della ricerca fin quando non la esplora fisicamente.
Bassa complessità spaziale. L'algoritmo di ricerca online ha il vantaggio di non richiedere una grande quantità di memoria per esplorare l'ambiente. È sufficiente registrare i nodi ancora da visitare, il nodo di origine e il percorso di backtracking dell'esplorazione in corso.
Mossa irreversibile. L'algoritmo di ricerca online è inefficace in caso di mosse irreversibili. In tali casi l'agente non può tornare indietro sui suoi passi oppure il costo di backtracking potrebbe essere molto elevato. Ad esempio, se nella cella A1 si trovasse un fosso, l'agente ci cadrebbe dentro nel momento dell'esplorazione senza essere più in grado di continuare la ricerca. Questo rischio non si verifica negli algoritmi di ricerca offline poiché questi ultimi, essendo in possesso delle informazioni sull'ambiente operativo ( mappa ), possono simulare tutte le mosse ancora prima di eseguirle nella realtà.
Complessità e inefficienza. Il tempo di esecuzione di un algoritmo di ricerca online in profondità potrebbe rivelarsi molto lungo. Nel seguente esepio l'obiettivo della ricerca C3 si trova a 2 passi dal luogo di partenza A3. L'algoritmo di ricerca online non conosce la mappa e inizia la prima esplorazione da A3 a B2 ( 6 passi ). La prima esplorazione si conclude con un fallimento, l'algoritmo non trova l'obiettivo e deve tornare sui suoi passi mediante la funzione di back-tracking ( 6 passi ). Una volta tornato sul luogo di origine A3 l'algoritmo inizia la seconda esplorazione ( linea verde ) da B3 a B1 ( 2 passi ) giungendo all'obiettivo.
In conclusione, non conoscendo la mappa l'algoritmo di ricerca online deve esplorare l'intera mappa ( 14 passi ) prima di trovare l'obiettivo, nonostante quest'ultimo si trovi soltanto a 2 celle di distanza dal luogo di partenza, con conseguente aumento del tempo di esecuzione ( complessità temporale ) e della dimensione dello spazio di memoria per registrare il backtracking ( complessità spaziale ). Ciò dipende dal fatto che l'agente di ricerca online non può effettuare una simulazione del cammino. Per conoscere lo stato di una cella deve necessariamente trovarsi sul posto. Nell'esempio sopra esposto l'obiettivo si trova nell'ultimo ramo dell'albero di ricerca ossia nel peggiore posto possibile per una ricerca in profondità. L'inefficienza è visibile a occhio nudo.
Cammino ciclico. L'esplorazione tramite un algoritmo di ricerca online è anche soggetta al rischio dei cammini ciclici. L'algoritmo conserva in memoria soltanto l'informazione del nodo corrente, i nodi ancora da visitare e il backtracking. In mancanza di un opportuno controllo sul backtracking, in alcuni casi l'algoritmo potrebbe reinserire nella coda dei nodi da visitatore già esaminati in precedenza. Ad esempio, nel seguente grafo l'algoritmo comincia l'esplorazione dal nodo di partenza A percorrendo i tratti AB, BC e CD. Una volta giunto al nodo D aggiunge tra i nodi da visitare il nodo E e, nuovamente, il nodo B. In entrambi i casi l'algoritmo incappa in un cammino ciclico ( loop ) in quanto torna a trovarsi sul nodo B.
E' interessante sottolineare anche la tendenza al cammino pro-ciclico iterativo. Una volta tornato sul nodo B l'algoritmo ha il 33,3% di possibilità di tornare al nodo di partenza A e il 66,6% di probabilità di tornare sui nodi ciclici C o E. È quindi più probabile la reiterazione del cammino ciclico piuttosto che l'uscita.
Algoritmo di ricerca su internet. Un algoritmo di ricerca online è anche un algoritmo in grado di ricercare un'informazione sulla rete internet. Questa accezione non deriva dalla modalità di ricerca su grandezze di flusso ( in linea ) bensì dal luogo in cui si svolge la ricerca. In questo caso il termine "online" è utilizzato come sinonimo di internet o di web. Gli algoritmi di ricerca online sono alla base del funzionamento dei motori di ricerca.
