Introduction to Backtracking
In data structures and algorithms, one method for solving problems is backtracking. Using this method, we can write the algorithm. The problem is solved using brute force, which states that for the given problem, we try to make all the available solutions and select the best solution out of all the requested solutions. This criterion is also observed in dynamic programming, although dynamic programming is employed to address optimization issues. In contrast, backtracking is not employed to address optimization issues. We backtrack when we have several solutions and need each one. It is used to resolve a problem in which a series of items from a given set is selected for the sequence to meet certain requirements. To get a detailed explanation of different methods of data structures and algorithms, visit the online DSA course, led by experienced faculties.
How Do You Know If You Can Use Backtracking To Solve a Problem?
In general, backtracking can be used to solve any constraint satisfaction problem that has clear and well-defined constraints on any possible objective solution; however, the majority of the problems stated may be resolved using other well-known algorithms, such as Dynamic Programming or Greedy Algorithms, in logarithmic, linear, or linear-logarithmic time complexity, descending from the amount of the input, and so outperform the backtracking technique in every way. (since backtracking algorithms are generally exponential in both time and space). Though, only backtracking techniques have been available to handle a handful of the remaining issues.
Think about a scenario in which you have three boxes in front of you, and only one contains a gold coin, but you are unsure which one it is. You must open each box one at a time to obtain the coin. If the first box does not include the coin, you must close it and continue looking in subsequent boxes until you do. Backtracking is tackling each little issue separately to find the optimal answer.
When Should a Backtracking Algorithm Be Used?
Using the backtracking technique is possible in the following situations:
-
Numerous issues can be resolved using it. To develop a workable answer to a decision-making issue, for instance, is one purpose for it.
-
The use of backtracking algorithms to solve optimization issues has also been found to be quite successful.
-
The enumeration problem may occasionally be solved by using it to identify every viable solution.
-
Backtracking is not thought to be the best approach to fixing problems, on the other hand. When there is no set amount of time to solve a problem, it is helpful.
Terminologies
-
Solution vector: The intended solution X to an instance of the problem P with input size n is represented as a vector of potential solutions chosen from a limited number of alternatives or solutions S.
As a result, a solution can be represented as an n-tuple (X1, X2,..., Xn), and its partial solution is given as (X1, X2,..., Xi), wherein.
-
Implicit constraints:
These rules instruct how to relate all potential solutions (x) to one another and help find the tuples in the solution space S that meet a given problem instance P's criterion function.
For instance, in the N-queens problem, all xi's must be distinct and satisfy the non-attacking queen's condition, and in the 0/1 knapsack problem, all x's with value 'I' must represent the item that yields the overall highest profit and has a total weight of S knapsack capacity.
-
Explicit constraints:
These guidelines limit all potential solutions, x_i primes, to only accepting values from a predetermined set in a problem instance P. The problem's instances determine the explicit limitations.
For instance, in the N-queens problem, if N = 4, then x i in [1, 2, 3, 4, 5, 6 N = 8 7,8] and if then x i in [1, 2, 3, 4, 5, 6 N = 8 7,8], and in the 0/1 knapsack problem, xe [0, 1], where x_i = 0 denotes the exclusion of an item i and x_i = 1 represents the inclusion of an item i.
-
Solution space:
The solution space S of a problem instance P comprises all potential solutions xi that satisfies the explicit restrictions. All routes from the root node to a leaf node in a state space tree describe the solution space.
For instance, in the case of the N-queens problem, the solution space for that particular problem instance consists of all n! orderings (x_1-, x_2-,...,x n).
-
State space tree:
State space trees are depictions of a problem instance P's solution space S in the shape of a tree.
It makes it easier to find the desired solution to a problem by enabling systematic search in the solution space.
Different state space trees can each represent a portion of a problem's solution space.
-
State space:
All connections between root and child nodes of a state space tree explain the state space of an issue.
-
Problem state:
A state space tree's nodes each depict a problem state or a partial resolution created by decisions made along the way from the tree's root to that node.
-
Solution states:
These are the issue states that cause a tuple in the solution space S., The solution states are divided into several sub-solution spaces at each internal node. All nodes in a state space tree with a variable tuple size are solution states.
Only the leaf nodes in a state space tree with a particular tuple size are solution states.
-
Bounding function:
Additionally, it is referred to as a "validity function," "criterion function," or "promising function."
It is an optimization function B(x1, x2, Xa) that must be maximized or minimized for a certain problem instance P. In the solution space S of a problem instance P, it optimizes the search for a solution vector (X1, X2,... Xn).
Rejecting potential solutions that don't lead to the intended resolution of the issue is beneficial. When limits are not met, it kills live nodes instead of looking at their offspring.
For instance, profit maximization by filling a knapsack is the criterion function in the case of the knapsack issue.
If you are learning DSA from scratch, don’t forget to register for India's top data structures and algorithms course, available online
