I 2 concetti sono legati (a volte è possibile anche combinarle), ma si dovrebbero concentrare solo sulle differenze fondamentali tra loro come i loro nomi suggeriscono:
Branch e legato esplora lo spazio di ricerca in modo esaustivo da ramificazione sulle variabili (= testare i valori delle variabili). Ciò crea diversi sottoproblemi, ad es. la ramificazione su una variabile binaria crea un problema in cui la variabile = 0 e un problema in cui è = 1. Potresti quindi procedere e risolverli ricorsivamente. L'aspetto "bounding" della tecnica consiste nella stima dei limiti delle soluzioni che possono essere raggiunte nel sottoproblema. Se il sottoproblema può fornire solo soluzioni errate (rispetto a una soluzione precedentemente trovata) è possibile saltare in sicurezza l'esplorazione di quella parte dello spazio di ricerca.
Le migliori prime prove per trovare una soluzione il più veloce possibile, cercando prima la parte più interessante dello spazio di ricerca (la più interessante = stima). Non divide lo spazio di ricerca, cerca solo di raggiungere una/la soluzione il più velocemente possibile.
Entrambi gli approcci cercano di saltare l'analisi di parti dello spazio di ricerca. Il loro uso ed efficienza dipendono dall'impostazione del problema. Per prima cosa, è meglio specificare un criterio per "la soluzione più interessante da esplorare", che a volte può risultare difficile/impossibile. Il ramo e il limite sono interessanti solo se il limite che è possibile attribuire ai sottoproblemi è significativo/non troppo ampio. Dipende dal problema che stai considerando ...
Quello che ho capito è questo: best-first search considera solo il costo di raggiungere uno stato (cioè la somma dei costi dallo stato root a quello stato) per il posizionamento , ma BB utilizza il costo minimo stimato di avere soluzioni complete attraverso quello stato. Ho ragione? – Barpa
No, Best Prima prova a selezionare il nodo successivo al processo utilizzando una stima del costo globale e non solo il costo corrente. Considera un problema di navigazione per il quale potresti utilizzare Dijkstra per creare alberi con il percorso più breve. Solo guardando al costo di raggiungere lo stato attuale è esattamente ciò che fa Dijkstra selezionando il nodo con la distanza tentativa più bassa per stabilirsi successivamente. Applicando Best First ad esso, si ottiene A * come in A * si seleziona sempre il nodo con la stima del costo totale più basso. – Origin
Mi dispiace, ma ora sono più confuso. Tu dici meglio: prima seleziona il nodo successivo usando la stima del costo globale. La stima del costo globale non è la stessa di quella del limite globale (inferiore o superiore) e degli usi associati per il confronto con lo stato corrente? – Barpa