Please enable JavaScript.
Coggle requires JavaScript to display documents.
M16, Coping with the Limitations of Algorithm Power - Coggle Diagram
M16
Coping with the Limitations of Algorithm Power
Backtracking
Backtracking is a general algorithmic technique for solving problems recursively by trying to build a solution incrementally, removing those solutions that fail to satisfy the constraints of the problem at any point.
Key Concept: Systematically search for a solution to a problem among all available options.
Applications: Solving puzzles (like Sudoku), finding paths in mazes, and generating permutations/combinations.
Algorithm Structure
.
Check if the current partial solution is a complete solution.
If complete, report success.
If not, try to extend the current partial solution by adding a new element.
If extending leads to a valid solution, continue recursively.
If not, backtrack by removing the last added element and trying the next possibility.
Branch-and-Bound
Branch-and-Bound
Branch-and-Bound is an algorithm design paradigm for solving combinatorial and optimization problems.
Key Concept: Systematically explore branches of a tree, which represent subsets of the solution space.
Bounding: Prune branches that cannot yield a better solution than the best one found so far.
Applications: Solving optimization problems like the traveling salesman problem, knapsack problem, and integer programming.
Algorithm Structure
Algorithm Structure:
Initialize the best solution found so far.
Explore the branches of the solution space tree, starting from the root.
For each branch, calculate a bound on the best possible solution within that branch.
If the bound is worse than the best solution found so far, prune the branch.
If the branch is promising, explore it further.
Update the best solution whenever a better solution is found during the exploration.