Tip:
Highlight text to annotate it
X
Data la non ottimalità della ricerca in profondità,
perché usarla?
La risposta ha a che fare con la richiesta di memoria.
Qui ho illustrato uno spazio di stato
costituito da un albero binario di grandi dimensioni o addirittura infinito.
Passando ai livelli 1, 2, 3, giù fino al livello n,
l'albero diventa sempre più grande.
Ora, consideriamo la frontiera per ognuno di questi algoritmi di ricerca.
Per il breadth-first, sappiamo che una frontiera assomiglia a questa,
quindi arrivando al livello n avremo bisogno di una quantità di memoria di
2 alla n di passi in una ricerca breadth-first.
Per la minor costo prima, la frontiera è più complicata.
Sarà qualcosa come questa regione di costi,
ma avrà un numero totale di nodi simile.
Ma per la ricerca profondità prima, mentre scendiamo l'albero, scendiamo in questo ramo,
e poi torniamo su, ma in ogni punto, la nostra frontiera avrà soltanto n nodi
invece di 2 alla n nodi, che è un risparmio sostanziale per la ricerca profondità prima.
Ovviamente, se teniamo traccia dell'insieme degli esplorati,
non risparmiamo poi così tanto.
Ma senza gli esplorati, la ricerca profondità prima ha un vantaggio enorme
in termini di spazio risparmiato.
Un'altra proprietà da considerare negli algoritmi
è la proprietà di completezza, cioè se un goal esiste,
riuscirà l'algoritmo a trovarlo?
Quindi passiamo da alberi molto grandi ad alberi infiniti,
e diciamo che esiste qualche goal nascosto profondo giu nell'albero.
La domanda è: questi algoritmi sono completi?
Cioè, garantiscono di trovare il percorso per il goal?
Cliccate sugli algoritmi che pensate siano completi in questo senso.