Unit 6
Backtracking Branch and Bound
Dr. Meghana Harsh Ghogare
Backtracking Branch and Bound
• Introduction to Backtracking
• Introduction to Brach & Bound
• 0/1 Knapsack Problem
• N-Queens Problem
• Travelling Salesman Problem
Introduction to Backtracking
Backtracking Overview:
• Backtracking is a general algorithmic technique that searches through
all possible combinations to solve a problem.
• It uses recursion and is faster than brute force by eliminating invalid
candidates with a single test.
• Brute force tries all possible solutions,
• backtracking discards invalid partial solutions early, improving performance.
Backtracking Problem Types:
1.Decision Problem: Finding a feasible solution.
2.Optimization Problem: Searching for the best solution.
3.Enumeration Problem: Finding all feasible solutions.
• Space Tree Representation:
• Backtracking problems are represented as a tree (search or space
tree).
• It checks for solutions from root to leaves in a recursive, depth-first
manner.
• Invalid subtrees are skipped, improving performance.
Red should not be in the middle
BRUTE FORCE
Backtracking
Introduction to Branch and Bound:
• Branch and Bound is a technique for solving optimization problems by
exploring the solution space as a tree.
• Costs are associated with branches, and branches with lower costs
are prioritized.
• Pruning is used to eliminate branches that do not lead to a solution.
Introduction to Brach & Bound
• The house with Park
• The number of red house
• Here there are 2 options
• 1) if the weight is greater than the capacity donot take the item
• Else
• 2) take the item but subtract the item from the capacity
Backtracking Example
• We take item3 vs we do not take
• X3-1 and x3=0
• And so on
• We can do it better by using Branch and Bound
N-Queens Problem
2 queens cannot be present in same row, same column, and 1 up left
diagonal and 1
• Back track queen 3, cant change, backtrack Queen 2 no change
Backtrack queen 1
• There are multiple possibilities of keeping 4 queens in 4 rows
• We are use Backtracking.
• If we need 1 optimal solution then we need to use Dynamic
Programming
Code of n queen
• https://replit.com/@AppMillers/NQueens2
Algorithm
1.Start from row 0, try placing a queen in each column.
2.Move to the next row and check if a queen can be safely placed (no queens
should be in the same column, row, or diagonal).
3.If it is not safe, backtrack by removing the last placed queen and trying a
different column.
4.Continue this process until all queens are placed or all columns are
exhausted for a particular row.
5.The algorithm will print the solution(s) once all queens are safely placed.
• This is how the backtracking approach systematically explores all
possibilities for solving the N-Queens problem.
# Function to check if the current
position is safe for the queen # Function to solve N-Queens # Function to print the board
def is_safe(board, row, col, n):
def solve_n_queens(board, row, n): def print_board(board, n):
# Check the same column if row == n: for row in board:
for i in range(row): # Solution found, print the board print(" ".join("Q" if x == 1 else "."
if board[i][col] == 1: for x in row))
print_board(board, n)
return False return True print("\n")
# Check the upper left diagonal # Main function to solve N-Queens
res = False problem
for i, j in zip(range(row, -1, -1), for col in range(n):
range(col, -1, -1)): def n_queens(n):
if board[i][j] == 1: if is_safe(board, row, col, n): board = [[0 for _ in range(n)] for _ in
return False # Place the queen range(n)]
board[row][col] = 1 if not solve_n_queens(board, 0, n):
# Check the upper right diagonal # Recur to place the rest of the print("No solution exists")
queens
for i, j in zip(range(row, -1, -1),
range(col, n)): res = solve_n_queens(board, # Input: Change N for the desired size
row + 1, n) or res of the board
if board[i][j] == 1: # Backtrack, remove the queen N = 4
return False board[row][col] = 0 n_queens(N)
return True return res
Travelling Salesman Problem(Branch & Bound)
• Given:
Weighted Graph
Cost Adjacency matrix
Goal:
Strat from any point and reach back
there in in minimum cost
State Space tree
• Backtracking and Branch and bound both use state space tree
• But there approach is different
• In backtracking every leaf node is a solution
• But We want minimum cost tour
• So find out cost of each branch, the moment we find a more
minimum option discard the previous one.
• But backtracking is more time consuming for solving optimization i.e
minimization or maximization problem, we avoid backtracking.
• Backtracking is best used for permutation problems
Reduce the matrix (Row reduction, subtract
Column reduction and add total
Cost of reduction is 25
The min cost of tour may be 25
Draw a state space
tree
• From 1, I can visit 2,3,4,5
• Cost of 1st node =25
• Cost from 1 to 2=
• C(1,2) 1st row 2nd col make
all infinity
• (2,1) also as infinity
• Then find min in each row
and column if min is already
0 then new reduction=0
• C(1,2)=C(1,2)+R=NewR=25
The least cost node is 4
Therefore it is further
explored
Now 4 is connected to 2,3,
5
(6,7,8 are node no.)
Find the cost from (4,2)
• Find the cost from (4,2)
• (4,2)=(1,4) & (4,2)
fill 1st row 4th col & 4th
row 2nd Col with ∞ and
(2,1) also ∞
• Since we cannot go back
from
• 2 to 4 make that also ∞
• Check for reduction
(4,3)=(1,4) & (4,3)
fill 1st row 4th col & 4th row 3rd Col with ∞ and (3,1) also ∞
