Tip:
Highlight text to annotate it
X
Ecco le risposte.
Ricerca breadth-first, come dice il nome, espande i nodi in questo ordine.
1, 2, 3, 4, 5, 6, 7.
Quindi, attraversa una riga per volta, in ampiezza prima.
È ottimale?
Beh, espande sempre i percorsi più brevi prima,
quindi, dovunque si nasconda il goal, lo troverà senza esaminare
percorsi più lunghi, quindi è ottimale.
Minor costo prima, espandiamo il percorso di lunghezza zero,
poi il percorso di lunghezza 2.
Poi un percorso di lunghezza 4, lunghezza 5,
lunghezza 6, uno di lunghezza 7, e infine, uno di lunghezza 8.
E vediamo che è garantito di trovare il percorso meno costoso,
assumendo che ogni passo non abbia costo negativo.
La ricerca profondità prima va prima al nodo più profondo,
quindi va all'1, 2, 3, poi torna su, 4,
poi torna su, 5, 6, 7.
E si vede che non c'è la certezza di trovare il percorso più corto.
Diciamo che i goal siano in posizione 5 e in posizione 3.
Troverebbe il percorso più lungo per la posizione 3 e considererebbe quello il goal
e non troverebbe il goal in posizione 5.
Quindi non è ottimale.