Differenza tra "backtracking" e "branch and bound"

Question

Nel backtracking usiamo sia bfs che dfs.Even in branch e bound usiamo sia bfs che dfs nella ricerca aggiuntiva e al costo minore.

Allora, quando usiamo backtracking e quando usiamo ramo e legati

funziona utilizzando ramo e legato riduce il tempo di complessità in scala?

qual è la ricerca a costo minimo in Branch e Bound?

mi corregga se sbaglio

Grazie

Answer 1

Backtracking

1. E 'utilizzato per trovare tutte le possibili soluzioni a disposizione di un problema.
2. Attraversa l'albero dello spazio di stato tramite il metodo DFS (profondità prima ricerca).
3. Si rende conto che ha fatto una scelta sbagliata & annulla l'ultima scelta eseguendo il backup.
4. Cerca l'albero di stato fino a quando non ha trovato una soluzione.
5. Comprende la funzione di fattibilità .

branch-and-bound

1. E 'utilizzato per risolvere problemi di ottimizzazione.
2. Può attraversare l'albero in qualsiasi modo, DFS o BFS.
3. Si rende conto che ha già una soluzione ottimale migliore a cui la pre-soluzione porta così abbandona quella pre-soluzione.
4. Cerca completamente nell'albero dello stato per ottenere una soluzione ottimale.
5. Comprende una funzione di delimitazione .

Answer 2

Backtracking

• Backtracking è un algoritmo generale per reperire tutti (o alcuni) soluzioni ad alcuni problemi computazionali, in particolare problema di soddisfacimento di vincoli, che crea incrementalmente candidati alle soluzioni, e abbandona ogni parziale candidato c ("backtracks") non appena determina che c non può essere completato a in una soluzione valida.
• Enumera una serie di candidati parziali che, in linea di principio, potrebbero essere completati in vari modi per fornire tutte le possibili soluzioni al problema dato. Il completamento viene eseguito in modo incrementale mediante una sequenza di passi estensione candidato.
• Concettualmente, i candidati parziali sono rappresentati come nodi di una struttura ad albero , l'albero di ricerca potenziale .Ogni candidato parziale è il genitore dei candidati che differiscono da esso per una singola fase di estensione, le foglie dell'albero sono i candidati parziali che non possono essere ulteriormente ampliati.
• Attraversa questo albero di ricerca in modo ricorsivo, dalla radice in giù, in ordine di profondità (DFS). Si rende conto di aver fatto una scelta sbagliata & annulla l'ultima scelta eseguendo il backup.
• Per ulteriori dettagli: Sanjiv Bhatia's presentation on Backtracking for UMSL.

branch and bound

• A branch-and-bound algoritmo è costituito da un'elencazione sistematica di soluzioni candidate mediante stato spazio di ricerca: l'insieme delle soluzioni candidate è pensato come formando un albero radicato con il set completo alla radice.
• L'algoritmo esplora i rami di questo albero, che rappresentano i sottoinsiemi del set di soluzioni. Prima di enumerare le soluzioni candidate di un ramo, il ramo viene verificato rispetto ai limiti stimati superiori e inferiori nella soluzione ottimale e viene scartato se non è in grado di produrre una soluzione migliore rispetto a quella migliore trovata finora dall'algoritmo.
• Può attraversare l'albero in qualsiasi modo seguente:
  1. BFS(Breath prima ricerca) o Branch (FIFO) e Bound
  2. D-Ricerca o Branch (LIFO) e bound
  3. Almeno Conte Ricerca o Branch (LC) e bound
• Per ulteriori informazioni: Sanjiv Bhatia's presentation on Backtracking for UMSL.