Algoritmo di ricerca

In informatica, un algoritmo di ricerca è un algoritmo progettato per risolvere un determinato problema di ricerca. Gli algoritmi di ricerca servono al ritrovamento di informazioni memorizzate all'interno di una certa struttura dati o calcolate nello spazio di ricerca del dominio di un problema, a valori discreti o continui.

La scelta dell'algoritmo di ricerca appropriato da utilizzare dipende spesso dalla struttura dati oggetto della ricerca e anche dalle conoscenze pregresse sui dati stessi. Gli algoritmi possono essere resi più veloci ed efficienti attraverso l'uso di strutture dati ausiliarie appositamente costruite come gli alberi di ricerca, le mappe hash e gli indici ^[1][2].

Classificazione

Algoritmi per spazi di ricerca virtuali

Gli algoritmi per la ricerca in spazi virtuali sono utilizzati nei problemi di soddisfacimento di vincoli, nei quali l'obiettivo è trovare un insieme di assegnazioni di valori a determinate variabili che soddisfino specifiche equazioni e disequazioni/uguaglianze matematiche (essi sono anche alla base di algoritmi di ottimizzazione per i quali l'obiettivo consiste nel trovare un'assegnazione di variabili che massimizzi o minimizzi una determinata funzione di tali variabili).

Gli algoritmi per problemi di ricerca includono la ricerca di base a forza bruta (chiamata anche ricerca “ingenua” o “non informata”) e una varietà di euristiche che cercano di sfruttare la conoscenza parziale della struttura dello spazio di ricerca, come il rilassamento lineare, la generazione di vincoli e la propagazione di vincoli.

Una sottoclasse importante è costituita dai metodi di ricerca locale, che considerano gli elementi dello spazio di ricerca come i vertici di un grafo, con i archi definiti da una serie di euristiche applicabili al caso in oggetto, e esplorano lo spazio spostandosi da un elemento all'altro lungo gli archi, ad esempio secondo il criterio della discesa più ripida o del miglior vicino (best first), oppure in una ricerca stocastica. Questa categoria comprende una grande varietà di metodi metaeuristici generali, come la ricottura simulata (simulated annealing), la ricerca tabù, gli A-team^[3] e la programmazione genetica, che combinano euristiche generiche in modi specifici. L'opposto della ricerca locale è rappresentato dai metodi di ricerca globale. Tali metodi sono applicabili quando lo spazio di ricerca non è limitato e tutti gli aspetti della rete sono noti all'esecutore dell'algoritmo di ricerca.^[4]

La classe include anche vari algoritmi di ricerca ad albero, che considerano gli elementi come vertici di un albero e attraversano tale albero in un ordine speciale. Esempi di quest'ultimo tipo includono metodi esaustivi come la ricerca in profondità e la ricerca in ampiezza, nonché vari metodi euristici di potatura dell'albero di ricerca come il backtracking e il branch and bound. A differenza delle metaeuristiche generali, che nel migliore dei casi funzionano solo in senso probabilistico, molti di questi metodi di ricerca ad albero garantiscono di trovare la soluzione esatta o ottimale, se viene concesso loro tempo sufficiente. Questo aspetto riguarda la completezza degli algoritmi.

Un'altra importante sottoclasse è costituita dagli algoritmi per l'esplorazione dell'albero di gioco dei giochi a più giocatori, come gli scacchi o il backgammon, i cui nodi sono costituiti da tutte le possibili situazioni di gioco che potrebbero derivare dalla situazione attuale. In tali problemi l'obiettivo è trovare la mossa che offra le maggiori possibilità di vittoria, tenendo conto di tutte le possibili mosse degli avversari. Problemi simili si verificano quando gli esseri umani o le macchine devono prendere decisioni successive i cui risultati non sono interamente sotto il proprio controllo, come nella guida dei robot o nella pianificazione di strategie di marketing, finanziarie o militari. Questo particolare tipo di problema, detto di ricerca combinatoria, è stato ampiamente studiato nel contesto dell'intelligenza artificiale. Esempi di algoritmi per questa classe sono l'algoritmo minimax, la potatura alfa-beta e l'algoritmo A* con le sue varianti.

Algoritmi per la ricerca di sotto-strutture

A tale classe sono ascritti gli algoritmi che ricercano pattern come sotto-strutture all'interno di una struttura data.

Una sottoclasse importante e ampiamente studiata è quella degli algoritmi per grafi, in particolare gli algoritmi di attraversamento dei grafi, utilizzati per trovare sotto-strutture specifiche in un dato grafo, come sotto-grafi, percorsi, circuiti e così via. Alcuni esempi sono l'algoritmo di Dijkstra, l'algoritmo di Kruskal, l'algoritmo di Prim, l'algoritmo del vicino più prossimo.

Un'altra sottoclasse importante di questa categoria è costituita dagli algoritmi di ricerca di stringhe, i quali cercano pattern all'interno delle stringhe. Due esempi famosi sono gli algoritmi di Boyer-Moore e Knuth-Morris-Pratt, oltre a diversi algoritmi basati sulla struttura dati dell'albero dei suffissi.