Tip:
Highlight text to annotate it
X
Abbiamo esaminato 2 algoritmi di ricerca.
Uno, ricerca breadth first, in cui espandiamo sempre prima
i percorsi meno profondi, i percorsi più brevi.
Il secondo, la ricerca minor costo prima, in cui espandiamo prima il percorso
con il minor costo totale.
E colgo l'occasione per introdurre un terzo algoritmo, la ricerca profondità prima,
che è in qualche modo l'opposto della ricerca breadth first.
Nella ricerca profondità prima, espandiamo sempre prima il percorso più lungo,
il percorso che contiene più lunghezze.
Ora, quello che vi chiedo di fare è per ciascuno di questi nodi in ognuno degli alberi,
dite in che ordine vengono espansi,
primo, secondo, terzo, quarto, quinto e così via, mettendo un numero nella casella.
E se ci sono parità, mettete quel numero e risolvete le parità da sinistra a destra.
Poi voglio che rispondiate ad un'altra domanda
quale di queste ricerche è ottimale?
Cioè, garantiscono di trovare la soluzione migliore?
E per la ricerca in breadth-first, ottimale significherebbe trovare il percorso più breve.
Se pensate che ci sia la garanzia di trovare il percorso più breve, marcare qui.
Per il minor costo prima, significherebbe trovare il percorso con il minor costo totale.
Marcate qui se pensate che il successo sia garantito.
E permettiamo l'ipotesi che tutti i costi debbano essere positivi.
E nel profondità prima, meno costoso o ottimale significherebbe, di nuovo,
come in breadth first, trovare il percorso più breve possibile in termini di numero di lunghezze.
Marcate qui se pensate che il profondità prima lo troverà sempre.