Please enable JavaScript.
Coggle requires JavaScript to display documents.
Coping with the Limitations of Algorithm Power - Coggle Diagram
Coping with the Limitations of Algorithm Power
Backtracking
Backtracks if reach dead-end
State-space-tree
n-Queens
Hamiltonian Circuit
Subset-Sum
outputs n-tuple with valid items from a set of integers
Not
necessarily an efficient algorithm
Applied to difficult combinatorial problems with no efficient algorithm available
"Improvement over exhaustive search"
Construct partial solutions and evaluate
Branch and Bound
Two extra items compared to backtracking:
"a way to provide, for every node of a state-space tree, a bound on the best value of the objective function1 on any solution that can be obtained by adding further components to the partially constructed solution represented by the node"
"
the value of the best solution seen so far
"
Assignment problem
Hungarian method
Knapsack problem
Travelling Salesman Problem
feasible != optimal
