Completezza di profondità prima ricerca

Question

cito da Artificial Intelligence: A Modern Approach:

Le proprietà di ricerca in profondità dipendono fortemente dal fatto che viene utilizzato il grafico-search o albero di ricerca di versione. La versione di ricerca del grafico, che evita stati ripetuti e percorsi ridondanti, è completa in spazi di stato finiti perché alla fine espanderà ogni nodo. La versione di ricerca ad albero, d'altra parte, è non completa [...]. La ricerca dell'albero di profondità può essere modificata senza costi di memoria aggiuntivi, in modo tale da controllare i nuovi stati rispetto a quelli sul percorso dalla radice al nodo corrente; questo evita loop infiniti negli spazi a stati finiti ma non evita la proliferazione di percorsi ridondanti.

Non capisco come si può eseguire la ricerca del grafico e la ricerca dell'albero non essere, essendo un albero un particolare grafico.

Inoltre, non ho chiaramente capito la differenza tra "loop infinito" e "percorsi ridondanti" ...

maggio qualcuno spiegare questo a me?

ps. Per coloro che hanno il libro è pagina 86 (3a edizione).

Answer 1

La ricerca dell'albero di profondità può rimanere bloccata in un ciclo infinito, motivo per cui non è "completa". La ricerca del grafico tiene traccia dei nodi che ha già cercato, quindi può evitare di seguire loop infiniti.

"Percorsi ridondanti" sono percorsi diversi che conducono dallo stesso nodo iniziale allo stesso nodo finale. La ricerca del grafico continuerà a esplorare tutti questi percorsi ridondanti, ma una volta raggiunto un nodo che ha visitato in precedenza, non andrà oltre, ma eseguirà il backup e cercherà altri percorsi che non ha ancora provato.

Questo è diverso da un "ciclo infinito" che è un percorso che conduce da un nodo a se stesso.

In risposta al tuo commento, guarda la citazione che hai appena pubblicato:

Depth-first tree search can be modified at no extra memory cost so that it checks new states against those on the path from the root to the current node.

Così, mentre in profondità di ricerca albero fa tenere traccia del percorso dalla radice al nodo corrente, a evitare loop infiniti, deve effettuare una ricerca lineare su quel percorso ogni volta che visita un nuovo nodo. Se hai scritto un'implementazione della ricerca ad albero in profondità che non ha effettuato il controllo, potrebbe entrare in un ciclo infinito.

Hai ragione, ciò che il libro ha detto sulla "proliferazione di percorsi ridondanti" non si riferisce alla completezza. Indica solo una differenza tra la ricerca di grafici e alberi. Poiché la ricerca ad albero tiene traccia del percorso corrente , può essere eseguito sullo stesso percorso più di una volta nella stessa ricerca (anche se si esegue il controllo che ho appena menzionato).

Supponiamo che il nodo radice abbia 2 diramazioni. Ognuno di questi rami conduce allo stesso nodo singolo, che ha un lungo percorso che porta fuori da esso. La ricerca ad albero seguirà quel lungo percorso due volte, una volta per ciascuno dei 2 rami che conduce ad esso. Questo è ciò che l'autore sottolinea.