← Post precendente

6. Introduzione alla ricerca: un algoritmo di ricerca generico

Nell'articolo precedente abbiamo parlato del problema di ricerca sfruttando la struttura del grafo, e in particolare quella dell'albero, tramite il quale possiamo trovare il percorso da un nodo di partenza a uno finale. In questo articolo ci concentriamo sui vari tipi di algoritmi di ricerca. Un primo algoritmo che andremo ad analizzare è un algoritmo di ricerca generico, tramite il quale si ottiene un percorso di soluzione in un grafico.

Avendo a disposizione un grafo, un nodo iniziale un obiettivo, l'algoritmo di ricerca generico esplora i percorsi in maniera incrementale dal nodo iniziale. Si memorizzano i vari percorsi in una struttura chiamata frontiera o frangia. Inizialmente la frontiera contiene solo il nodo iniziale e nessun arco, man mano che la ricerca procede la frontiera si espande fino ad incontrare il nodo obiettivo. Vengono definite diverse strategie di ricerca che implementano in maniera diversa la frontiera. Vediamo un esempio.

Pseudocodice 1 - Ricerca Generica

1. procedura search ( G, S, obiettivo )
2.  Input
3.   G: grafo con N nodi e A archi
4.   S: nodo iniziale
5.   obiettivo: funzione booleana sui nodi
6.  Output
7.   percorso da S a un nodo per il quale
  l'obiettivo è vero o ⊥\bot se non esiste
8.  Variabili Locali
9.    Frontiera = {  <S>  }\{ \;< S > \;\}
10.    while Frontiera ≠{  }\ne \{\;\}
11.     seleziona e rimuovi <n0,…,nk>< n_0, \dots, n_k >      dalla frontiera
12.     if goal(  nk  )goal( \; n_k \; ) allora
13.      return <n0,…,nk>< n_0, \dots, n_k >
14. Frontiera = Frontiera∪{<n0,…,nk,n>:<nk,n>∈A}Frontiera \cup \{ < n_0, \dots, n_k, n > : < n_k, n > \in A \}
14.    return ⊥\bot

La frontiera è un insieme di percorsi e il suo costo iniziale è pari a zero in quanto costituita solo dal nodo iniziale. Ad ogni ciclo l'algoritmo rimuove un percorso dalla frontiera. Se la funzione goal restituisce vero, significa che si è raggiunto un nodo obiettivo e che quindi l'algoritmo ha trovato una soluzione e restituisce il percorso trovato. Altrimenti il percorso viene esteso di un altro arco attraverso l'ispezione dei vicini. Ogni neighboor viene aggiunto alla frontiera, e questo processo viene definito espansione.

Esaminiamo alcune caratteristiche dell'algoritmo appena visto:

  • Alla riga 11, la selezione del percorso stabilisce la strategia di ricerca, influenzandone l'efficienza;
  • Il ritorno presente alla riga 13, è utile in quanto il chiamante può ritentare la ricerca per ottenere un'altra risposta;
  • Se la procedura ritorna ⊥\bot (bottom), significa che non ci sono soluzioni rimanenti;
  • L'algoritmo verifica solo se un percorso termina in un nodo obiettivo dopo che il percorso è stato selezionato dalla frontiera, non quando viene aggiunto alla frontiera.

Per quanto riguarda l'ultimo punto vi sono due ragioni fondamentali per le quali l'algoritmo computa in questo modo. La ricerca non dovrebbe restituire un percorso all'interno del quale ci potrebbe essere un arco costoso, in quanto ci potrebbe essere un percorso con un costo minore. In secondo luogo, ci si potrebbe trovare nel caso in cui la funzione per determinare il costo di un nodo obiettivo richiede un costo eccessivo, quindi nel caso in cui questo calcolo non sia necessario, deve essere ritardato.

Introduciamo due concetti fondamentali riguardanti gli algoritmi di ricerca, il non determinismo don't-care e il non determinismo don't-know. Nel primo caso, se una selezione non porta a una soluzione, non verrà considerata insieme alle altre. Questo tipo di non determinismo viene utilizzano nell'allocazione delle risorse, in cui un numero di richieste per un numero limitato di risorse e un algoritmo di pianificazione deve selezionare chi ottiene quale risorsa in ogni momento.

La correttezza non dovrebbe essere influenzata dalla selezione, ma l'efficienza e la cessazione potrebbero esserlo. Quando c'è una sequenza infinita di selezioni, un meccanismo di selezione è giusto se una richiesta che è ripetutamente disponibile per essere selezionata alla fine sarà selezionata. Il problema di un elemento ripetutamente non selezionato si chiama starvation. In questo contesto, un'euristica è una regola empirica che può essere utilizzata per selezionare un valore.

Nel non determinismo don't-know, solo perché una scelta non ha portato a una soluzione non significa che altre scelte non lo faranno. Spesso si parla di un oracolo che potrebbe specificare, in ogni punto, quale scelta porterà a una soluzione. Poiché il nostro agente non ha un tale oracolo, deve cercare nello spazio delle scelte alternative. Questo tipo di non determinismo è fondamentale nella teoria della complessità computazionale di cui parliamo in questa serie di articoli.

In una procedura non deterministica, fingiamo che un oracolo faccia ogni volta una scelta appropriata. Pertanto, un'affermazione di scelta si tradurrà in una scelta che porterà al successo o fallirà se non ci sono tali scelte. Una procedura non deterministica può avere più risposte, dove ci sono più scelte che hanno successo, e fallirà se non ci sono scelte applicabili. Un errore esplicito nel codice indica una scelta che non dovrebbe riuscire.

Continueremo nel prossimo articolo a trattare di altre due tipologie di ricerca: la ricerca non informata e la ricerca euristica.

Post successivo →