Backtracking
It is a problem solving technique that involves finding a solution incrementally by trying different options and undoing them if they lead to a dead end.
While exploring multiple possibilities, when a dead state is reached, the algorithm backtracks to the previous select state and explores other possibilities to choose a different path.
A rule is selected and if it doesn’t lead to a solution, the intervening steps are forgotten.
Compared to graph search control regime, backtracking strategies are simpler to implement and require less storage.
Pseudocode for Backtracking
-
if (valid solution):
-
store the solution
-
return
-
for (choice in all choices):
-
if (valid choice):
-
APPLY(choice)
-
find_solutions(parameters)
-
BACKTRACK(remaining choices)
-
return
Rules Applied for Backing Up
-
Whenever we generate a state description that already occurs on the path back to the initial state description
-
Whenever we apply an arbitrarily set number of rules without having generate a goal state description
-
Whenever there are no more applicable rules
|
Note
|
Since backtracking is purely brute force, so in terms of complexity, it performs very badly. |