Scribd
Upload
80 views21 pages

Backtracking

Backtracking is an algorithmic technique for solving problems recursively by trying to build a solution incrementally, abandoning a solution ("backtracking") as soon as it is determined that the solution cannot possibly be completed to a valid one. It is often used when solving constraint satisfaction problems that require examining partial candidates solutions to determine if they can possibly be completed to a valid solution. Examples of problems that can be solved using backtracking include the n-queens problem, sudoku puzzles, and the knapsack problem. The algorithm uses a state space tree to represent partial solutions and employs a depth-first search approach, abandoning nodes as soon as it is determined they cannot lead to a valid solution.

Uploaded by

vijaya lakshmi
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
80 views21 pages

Backtracking

Backtracking is an algorithmic technique for solving problems recursively by trying to build a solution incrementally, abandoning a solution ("backtracking") as soon as it is determined that the solution cannot possibly be completed to a valid one. It is often used when solving constraint satisfaction problems that require examining partial candidates solutions to determine if they can possibly be completed to a valid solution. Examples of problems that can be solved using backtracking include the n-queens problem, sudoku puzzles, and the knapsack problem. The algorithm uses a state space tree to represent partial solutions and employs a depth-first search approach, abandoning nodes as soon as it is determined they cannot lead to a valid solution.

Uploaded by

vijaya lakshmi
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 21

Design and analysis of algorithm

Backtracking
Unit 4
Backtracking
• Brute force Approach
• Find all possible solution
• Same as dynamic programming
• In Dynammic programming ,we solve
optimization problem
• It uses state space tree to represent solution
• It follows DFS
• Backtracking is an important tool for solving
constraint satisfaction problems, such as
crosswords, verbal arithmetic, Sudoku, and
many other puzzles.
Examples
1. Sum of subset
2. N-Queen Problem
3. Graph colouring
4. Hamiltonian cycle
5. Knapsack Problem
Sum of subsets
• Problem: Given n positive integers w1, ...
wn and a positive integer S. Find all
combination of integer whose sum is S.
• Example:
n=3, S=6, and w1=2, w2=4, w3=6

• Solutions:
{2,4} and {6}

Backtracking 5
steps
• Start with an empty set
• Add the next element from the list to the set
• If the subset is having sum M, then stop with that subset as
solution.
• If the subset is not feasible or if we have reached the end of
the set, then backtrack through the subset until we find the
most suitable value.
• If the subset is feasible (sum of subset < M) then go to step 2.
• If we have visited all the elements without finding a suitable
subset and if no backtracking is possible then stop without
solution.
Sum of subset Problem:
State SpaceTree for 3 items
w(1…6)=(5,10,12,13,15,18) and M = 30

0,73
yes no

i1 5,68 0,68

yes no yes no

i2 6 2 4 0

yes no yes no yes no yes no

i3 12 6 8 2 10 4 6 0

The sum of the included integers is stored at the node.

Backtracking 7
Backtracking

• Definition: We call a node nonpromising if it


cannot lead to a feasible (or optimal) solution,
otherwise it is promising

• Main idea: Backtracking consists of doing a


DFS of the state space tree, checking whether
each node is promising and if the node is
nonpromising backtracking to the node’s
parent
Backtracking 9
A Pruned State Space Tree (find all solutions)
w1 = 3, w2 = 4, w3 = 5, w4 = 6; S = 13

0
3 0

3 0
4 0 4 0

7 3 4 0

5 0 5 0 5 0

12 7 8 3 9 4
6 0

13 7

Sum of subsets problem

Backtracking 10
N Queen's problem and solution using backtracking algorithm

• Here, the n – queens are placed on a n * n


chess board, which means that the
chessboard has n rows and n columns and the
n queens are placed on thus n * n chessboard
such that no two queens are placed in the
same row or in the same column or in same
diagonal. So that, no two queens attack each
other.
Now, you can see that there is no safe place where we can put the last queen. So, we
will just change the position of the previous queen. And this is backtracking.

You might also like