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
Construct solutions one component at a time, evaluating such partially constructed candidates as follows:
If a partially constructed solution can be developed further without violating the problem's constraints, it is done by taking the first remaining legitimate option for the next component.
If there is no legitimate option for the next component, no alternatives for any remaining component need to be considered.
In this case, the algorithm backtracks to replace the last component of the partially constructed solution with its next option.
This kind of processing is implemented by making a state-space tree.
A node is promising if it corresponds to a partially constructed solution that may still lead to a complete solution.
Otherwise, it is nonpromising.
Leaves are either complete solutions or nonpromising dead ends.
Usually uses DFS.
Usually applied to difficult combinatorial problems for which no efficient algorithms for finding exact solutions possibly exist.
Holds hope for solving instances of nontrivial sizes in an acceptable amount of time.
Branch-and-Bound
Deals with optimization problems, requiring, on top of what's required in backtracking:
The value of the best solution seen so far.
A way to provide, for every node of a state-space tree, a bound on the best value of the objective function on any solution that can be obtained by adding further components to the partially constructed solution represented by the node.
Just like backtracking, the nodes are pruned when there's a dead end, being pruned for any of the following reasons:
The value of the node's bound is not better than the value of the best solution seen so far.
The node represents no feasible solutions because the constraints of the problem are already violated.
The subset of feasible solutions represented by the node consists of a single point, in which case the value of its objective function is compared with that of the best solution seen so far and update the latter with the former if the new solution is better.