A backtracking algorithm is a problem-solving method that finds the intended output via a brute-force approach.
Backtracking implies that if the current answer isn't working, you should go back and try something else. As a result, recursion is used in this method.
When there are several solutions to a problem, this method is utilized to solve it. Dynamic programming is the way to go if you want the best result.
A space state tree is a tree that depicts all of the problem's conceivable states (solution or nonsolution) from the root to the leaf.
Problem: You want to figure out all the different ways you can arrange two lads and one girl on three benches using the backtracking approach. The girl must not sit in the middle of the bench.
Solution: There are 3! = 6 choices in all. We'll investigate all options and come up with the best answer. We attempt all of the options in a recursive fashion.
|
|
