Depth-limited search

Da Wikipedia, l'enciclopedia libera.
Jump to navigation Jump to search
Depth-limited search
ClasseAlgoritmo di ricerca
Struttura datiGrafo
Caso peggiore temporalmente
Caso peggiore spazialmente
OttimaleNo
CompletoNo

In informatica, il depth-limited search (DLS) è un algoritmo di ricerca per esplorare i vertici di un grafo. È una versione modificata del depth-first search ed è utilizzato, ad esempio, nell'algoritmo Iterative deepening.

Concetto di base[modifica | modifica wikitesto]

Come il depth-first search, il depth-limited search è un tipo di ricerca non informata. Funziona esattamente come il depth-first search, impedendo però l'inconveniente della completezza imponendo un limite alla profondità massima di ricerca. Anche se fosse possibile continuare l'espansione di un vertice a una data profondità, ciò non avverrà e di conseguenza non proseguirà andando all'infinito nella profondità di un percorso o rimanendo bloccato in un ciclo. Perciò il depth-limited search troverà una soluzione esclusivamente se è dentro un certo limite di profondità, il che garantisce quanto meno la completezza su tutti i grafi.

Algoritmo (informale)[modifica | modifica wikitesto]

  1. Determinazione vertice di partenza e assegnazione limite massimo di profondità
  2. Controllo se il vertice corrente è quello di destinazione:
    • No: Non fare nulla
    • Sì: return
  3. Controllo se il vertice corrente è meno in profondità del limite imposto:
    • No: Non fare nulla
    • Sì:
      1. Espansione vertice e salvataggio dei suoi successori in una pila
      2. Chiamata ricorsiva a DLS per tutti I vertici nella pila, quindi di nuovo il Passo 2

Pseudocodice[modifica | modifica wikitesto]

DLS(nodo, destinazione, profondita) {
	if ( profondita >= 0 ) {
		if ( nodo == destinazione )
			return nodo
		for each figlio in espandi(nodo)
			DLS(figlio, destinazione, profondità - 1)
	}
}

Proprietà[modifica | modifica wikitesto]

Complessità Spaziale[modifica | modifica wikitesto]

Magnifying glass icon mgx2.svgLo stesso argomento in dettaglio: Teoria della complessità computazionale.

Dal momento che il depth-limited search sfrutta il depth-first search, la complessità spaziale è equivalente a quella normale del depth-first search.

Complessità Temporale[modifica | modifica wikitesto]

Magnifying glass icon mgx2.svgLo stesso argomento in dettaglio: Teoria della complessità computazionale.

Dal momento che il depth-limited search sfrutta la ricerca depth-first, la complessità è equivalente a quella normale del depth-first search, ovvero , dove è il numero di vertici e il numero di archi nel grafo esplorato. Da notare che il depth-limited search non esplora l'intero grafo, ma solo la parte inclusa dentro il limite specificato.

Completezza[modifica | modifica wikitesto]

Magnifying glass icon mgx2.svgLo stesso argomento in dettaglio: NP-Completo.

Dal momento che il depth-limited search non può analizzare percorsi infinitamente lunghi né rimanere bloccato nei cicli, in generale non è un algoritmo completo visto che non trova alcuna soluzione che sia oltre al limite imposto. Se tuttavia il limite di profondità scelto è maggiore della profondità dell'albero, l'algoritmo diventa completo.

Ottimalità[modifica | modifica wikitesto]

Il depth-limited search non è ottimale in quanto, come il depth-first search, esplora completamente un percorso, incorrendo così nella possibilità di trovare una soluzione più costosa di un'altra.

Voci correlate[modifica | modifica wikitesto]