Systematically searches for a solution to a problem among all available options. In backtracking, we start with one possible option out of many available options and try to solve the problem if we are able to solve the problem with the selected move then we will print the solution else we will backtrack and select some other option and try to solve it. If none if the options work out we will claim that there is no solution for the problem.
Backtracking can be thought of as a selective tree/ graph traversal method. The tree is a way of representing some initial starting position (the root node) and a final goal state (one of the leaves). Backtracking allows us to deal with situations in which a raw brute-force approach would explode into an impossible number of options to consider.
Backtracking can be thought of as a selective tree/ graph traversal method. The tree is a way of representing some initial starting position (the root node) and a final goal state (one of the leaves). Backtracking allows us to deal with situations in which a raw brute-force approach would explode into an impossible number of options to consider.
Example Algorithms of Backtracking
- Binary Strings: generating all binary strings - Generate binary strings of n bit - 1.Problem1.cpp
- Generating k – ary Strings
- N-Queens Problem
- The Knapsack Problem
- Generalized Strings
- Hamiltonian Cycles [refer to Graphs chapter]
- Graph Coloring Problem
Generate permutation of a string - 2.Problem2.cpp
No comments:
Post a Comment