** **__Backtracking__

__Backtracking__

Backtracking is an algorithmic technique for recursively solving problems by trying to build a solution incrementally, one piece at a time, removing the solutions that fail to meet the constraints of the problem at any time (for example, time, here it is referred to the time elapsed until reaching any level of the search tree).

**According to the wikipedia definition,**

Backtrackingcan be defined as a general algorithmic technique that considers the search for all possible combinations in order to solve a computational problem.

There are three types of backtracking problems –

**Decision problem ** – In Decision problem we are looking for a feasible solution.(What is feasible solutions among all solutions possible).

**Optimization problem** – In Optimization problem we are looking for the best solution(What is best solution among all possible solutions possible).

**Problem of enumeration ** – In Problem of enumeration we find all the feasible solutions(What is feasible solutions among all solutions possible).

__Search space and optimization problem techniques__** Backtracking**

__General method__

Two versions of backtracking algorithms

Solution needs only to be feasible (satisfy problem’s constraints) sum of subsets

Solution needs also to be optimal knapsack problem

**The backtracking method **

- A given problem has a set of constraints and possibly an objective function
- The solution optimizes an objective function, and/or is feasible.
- We can represent the solution space for the problem by using a state space tree

The root of the tree represents 0 choices,

Nodes at depth 1 represent the first choice

Nodes at depth 2 represent the second choice, etc.

In this tree a*path*from a root to a leaf represents a candidate solution - Problem space consists of states (nodes) and actions (paths that lead to new states).
- If a node leads to failure go back to its “parent” node.
- Characteristics of Brute Force and Backtracking

Brute force algorithms are slow

They don’t employ a lot of logic

But, brute force algorithms are fairly easy to implement as a first pass solution Backtracking is a form of a brute force algorithm

**Goals of Backtracking Possible goals**

- Find a path to success
- Find all paths to success
- Find the best path to success

Not all problems are exactly alike, and finding one success node may not be the end of the search

**Pseudo code for recursive backtracking algorithms**

- If at a solution, report success
- for ( every possible choice from current state / node)

Make that choice and take one step along path

Use recursion to solve the problem for the new node / state

If the recursive call succeeds, report the success to the next high level

Back out of the current choice to restore the state at the beginning of the loop. - Report failure

**Algorithm for Backtracking**

void checknode(node v) { node u; if promising(v) then if (there is a solution at v) then write the solution ; else for (each child u of v) do checknode(u); }

Topic : Backtracking | Algorithm for Backtracking