UNIT-5

Back tracking: n-Queen’s Problem, Subset-Sum Problem.

Branch and Bound: Assignment Problem and Traveling Salesman Problem.

Backtracking
It is a general algorithmic technique for solving problems that involve searching for a solution
among a set of potential candidates. It's often used for problems that can be broken down into
a sequence of decisions, where each decision leads to a new state, and the goal is to reach a
"goal" state.

❖ state-space tree
It is a conceptual tree that represents all possible partial and complete solutions to a problem.
It's not necessarily a physical data structure built in memory, but rather a mental model or a
way to visualize the search process.

1. The N-Queens Problem

It is a classic problem in computer science and a perfect example of how backtracking
algorithms are used.

The Problem Statement:

The N-Queens problem asks: "How can you place N chess queens on an N×N chessboard
such that no two queens attack each other?"

Understanding "Attack":

In chess, a queen is a powerful piece that can attack any other piece in the same:

• Row (horizontally)
• Column (vertically)
• Diagonal (both main diagonals: top-left to bottom-right, and top-right to bottom-left)

The Goal:

The goal is to find all possible distinct arrangements (solutions) of N queens on the N×N
board where none of the attacking rules are violated.

Why is it a Classic Backtracking Problem?

1. Sequence of Decisions: You can solve this problem by making a series of decisions,
one queen at a time. Typically, you try to place one queen in each row.
 2. Constraints: At each step, when you try to place a queen, there are strict constraints:
it cannot be in the same row, column, or diagonal as any previously placed queen.
3. Building a Solution Incrementally: You build a potential solution by placing queens
one by one.
4. Dead Ends and Backtracking: If, at any point, you place a queen in a position where
it's impossible to place the remaining queens without violating the rules (i.e., you
reach a "dead end"), you must backtrack. This means you undo the last decision
(remove the last queen) and try a different position for it.
5. Finding All Solutions (or one): Depending on the problem's requirement, you might
stop at the first solution found, or continue backtracking to find all possible distinct
solutions

Example: 4-Queens Problem

For N=4, there are only two distinct solutions. Let's represent the board as a 4x4 grid. 'Q' for
a queen, '.' for an empty square.
This image (Figure 12.2) is a state-space tree visualizing the backtracking process for
solving the Four-Queens Problem.

Explanation:
1. Overall Purpose: Solving the Four-Queens Problem with Backtracking
o The Four-Queens Problem is about placing 4 queens on a 4x4 chessboard such
that no two queens attack each other (meaning no two queens share the same
row, column, or diagonal).
o This tree shows how a backtracking algorithm explores different possibilities
to find a solution.
2. Nodes (Numbered Squares with Grids):
o Each square grid represents a state or a partial solution on the chessboard.
o The 'Q's inside the grids show where queens have been placed so far.
o The numbers above each node (0, 1, 2, 3, 4, 5, 6, 7, 8) indicate the order in
which these nodes (states) are generated and explored by the backtracking
algorithm. This highlights the depth-first nature of the search.
3. Root Node (Node 0):
o The very top node, labeled '0', represents the initial state with an empty 4x4
chessboard. This is where the search begins.
4. Branches/Edges:
o The lines connecting the nodes represent the choices or decisions made at
each step. In the N-Queens problem, each decision is about placing a queen in
a specific column of the current row.
5. Small Numbers 1, 2, 3, 4 under the Grids:
o These numbers represent the column number (1st, 2nd, 3rd, or 4th column)
where the algorithm attempts to place the next queen in the current row.
o For example, from Node 0, the algorithm first tries placing a queen in column
1 of the first row (leading to Node 1). Then it tries column 2 (leading to Node
5).
6. 'x' Symbol (Unsuccessful Attempt):
o An 'x' under a column number indicates an unsuccessful attempt to place a
queen in that specific column.
o This happens when placing a queen in that position would immediately violate
the problem's constraints (i.e., it would be attacked by a queen already placed
in a previous row).
o When an 'x' is encountered, the algorithm backtracks to the previous decision
point (the parent node) and tries the next available option. This is the
"pruning" mechanism of backtracking.

Trace a Path (Example):

• Node 0 (Start): Empty board.
• From Node 0, try Column 1: Leads to Node 1. A queen is placed in (Row 1, Col 1).
• From Node 1, try Column 1 (Row 2, Col 1): This is marked with an 'x'. Why?
Because a queen in (R2, C1) would attack the queen in (R1, C1) (same column). So,
backtrack.
• From Node 1, try Column 2 (Row 2, Col 2): This is marked with an 'x'. Why?
Because a queen in (R2, C2) would attack the queen in (R1, C1) (same diagonal). So,
backtrack.
• From Node 1, try Column 3 (Row 2, Col 3): Leads to Node 2. A queen is placed in
(R2, C3). Board now has queens at (R1, C1) and (R2, C3).
• From Node 2, try Column 1 (Row 3, Col 1): 'x' (attacks Q at R1C1). Backtrack.
• From Node 2, try Column 2 (Row 3, Col 2): 'x' (attacks Q at R2C3 diagonally).
Backtrack.
• From Node 2, try Column 3 (Row 3, Col 3): 'x' (attacks Q at R2C3 same column).
Backtrack.
• From Node 2, try Column 4 (Row 3, Col 4): Leads to Node 3. A queen is placed in
(R3, C4). Board now has queens at (R1, C1), (R2, C3), and (R3, C4).
• From Node 3, try Column 1 (Row 4, Col 1): 'x'. Backtrack.
• From Node 3, try Column 2 (Row 4, Col 2): 'x'. Backtrack.
• From Node 3, try Column 3 (Row 4, Col 3): 'x'. Backtrack.
• From Node 3, try Column 4 (Row 4, Col 4): 'x'. Backtrack.
o Since all options from Node 3 failed, the algorithm backtracks to Node 2. All
options from Node 2 have been exhausted.
• Backtrack further to Node 1. All options from Node 1 have been exhausted.
• Backtrack further to Node 0.
• From Node 0, now try Column 2 (Row 1, Col 2): Leads to Node 5. A queen is
placed in (R1, C2).
• ... (The process continues)
• From Node 5, try Column 1 (Row 2, Col 1): 'x'. Backtrack.
• From Node 5, try Column 2 (Row 2, Col 2): 'x'. Backtrack.
• From Node 5, try Column 3 (Row 2, Col 3): 'x'. Backtrack.
• From Node 5, try Column 4 (Row 2, Col 4): Leads to Node 6. Queen at (R2, C4).
• From Node 6, try Column 1 (R3, C1): Leads to Node 7. Queen at (R3, C1).
• From Node 7, try Column 1 (R4, C1): 'x'. Backtrack.
• From Node 7, try Column 2 (R4, C2): Leads to Node 8. Queen at (R4, C2).

7. "solution" Label (Node 8):

o The path leading to Node 8 represents a complete and valid solution to the
Four-Queens problem. All four queens have been placed without attacking
each other.
o The backtracking algorithm would typically stop here if only one solution is
needed, or continue exploring other branches if all solutions are required.
 2. Subset-Sum Problem.
The Subset-Sum Problem is a fundamental problem in computer science, falling under the
category of decision problems.

Examples:
• Example 1:
o Numbers: [3, 34, 4, 12, 5, 2]
o Target Sum: 9
o Answer: YES. Because the subset [4, 5] sums to 9. (Also, [3, 4, 2] sums
to 9).
• Example 2:
o Numbers: [3, 34, 4, 12, 5, 2]
o Target Sum: 30
o Answer: NO. There is no subset of these numbers that adds up to exactly 3

the tree as a map of all the ways you can pick numbers from your special list A = {3, 5, 6,
7} to try and make your target number d = 15.

1. Circles with Numbers (Nodes):

o Each circle shows you how much you've added up so far on your journey.
o Start at the top (Node 0): You haven't picked any numbers yet, so your sum
is 0.
2. Lines Coming Out of Circles (Branches):
 oEach line represents a choice you make for the next number in your list (3,
then 5, then 6, then 7).
o "with X" line: Means you add that number (X) to your sum. You're including
it in your current collection.
o "w/o X" line: Means you skip that number (X). Your sum stays the same for
now.
3. Ends of the Lines (Leaf Nodes / Where Paths Stop):
o "solution" label: This is like hitting the jackpot! It means the numbers you
picked on that path add up exactly to 15. You found a way to make your
target sum!
o 'x' symbol: This is a dead end. It means the way you've picked numbers on
this path cannot possibly reach 15.
▪ Why a dead end? (The messages below the 'x'):
▪ "14 + 7 > 15" (Sum got too big): You added a number, and
now your total is more than 15. You can't un-add it, so this path
is wrong.
▪ "8 < 15", "3 < 15", etc. (Sum is too small, and no more
numbers to add): You've already looked at all the numbers in
your list, but your current total is still less than 15. Since you
can't add any more, this path won't work.

Tracing a Path (Example):

1. Start at Node 0 (sum = 0).

2. Decision for '3':
o "with 3" branch: Go to node 3 (sum = 3).
o "w/o 3" branch: Go to node 0 (sum = 0).
3. From node 3 (sum = 3), decision for '5':
o "with 5" branch: Go to node 8 (sum = 3 + 5 = 8).
o "w/o 5" branch: Go to node 3 (sum = 3).
4. From node 8 (sum = 8), decision for '6':
o "with 6" branch: Go to node 14 (sum = 8 + 6 = 14).
▪ Now consider '7'. If we include '7', sum becomes 14 + 7 = 21. The
inequality 14 + 7 > 15 marks this as an 'x'. We backtrack.
o "w/o 6" branch: Go to node 8 (sum = 8).
5. From node 8 (sum = 8), decision for '7':
o "with 7" branch: Go to node 15 (sum = 8 + 7 = 15).
▪ This is exactly our target sum, d = 15. This is a "solution"!
o "w/o 7" branch: Go to node 8 (sum = 8). The inequality 8 < 15 marks this
as an 'x' because we've processed all numbers (3, 5, 6, 7) and the sum (8) is
not equal to 15. We backtrack.

❖ This tree visually demonstrates how the backtracking algorithm explores possibilities by making
choices ("with" or "without" each number), keeping track of the current sum, and cutting off
(pruning) branches that cannot possibly lead to a solution (marked with 'x' and an inequality). It
continues until it finds a solution or exhausts all possibilities.
Branch and Bound
Branch and Bound is a powerful optimization technique that strategically explores the solution
space by breaking down problems and using estimated bounds to intelligently cut off
unproductive branches, significantly speeding up the search for the best possible answer.

1. Assignment Problem
The Assignment Problem is a fundamental problem in combinatorial optimization.
It deals with the task of assigning a set of "agents" (or workers) to a set of "tasks" (or jobs),
with the goal of minimizing the total cost or maximizing the total benefit of the assignments.

The Core Idea:

Imagine you have:
• N workers
• N tasks

And you know:

• The cost (or benefit) of assigning each worker to each task. This is often represented in
an N x N matrix, where cost[i][j] is the cost of assigning worker i to task j.

The problem is to find a way to assign exactly one worker to exactly one task, such that:
• Every worker is assigned.
• Every task is assigned.
• The total cost of all assignments is minimized (or the total benefit is maximized).

Key Characteristics:
1. One-to-One Assignment: Each worker is assigned to exactly one task, and each task
is assigned to exactly one worker. This is crucial.
2. Equal Numbers: Usually, the number of workers equals the number of tasks (N
workers to N tasks). If they are unequal, you can often introduce "dummy" workers or
tasks with zero cost to balance the numbers.
3. Cost/Benefit Matrix: The relationships between workers and tasks are defined by a
matrix.
4. Optimization: The goal is to find the best possible assignment (minimum cost or
maximum benefit).

Example:
Let's say you have 3 workers (Worker 1, Worker 2, Worker 3) and 3 tasks (Task A, Task B,
Task C). The cost matrix shows how much it costs to assign each worker to each task:
Possible Assignments (and their costs):
• (W1 to A, W2 to B, W3 to C) -> Cost = 10 + 9 + 2 = 21
• (W1 to A, W2 to C, W3 to B) -> Cost = 10 + 8 + 5 = 23
• (W1 to B, W2 to A, W3 to C) -> Cost = 3 + 4 + 2 = 9
• ...and so on for all 3! = 6 possible assignments.

The Solution:
The optimal solution (minimum cost) in this example is:
• Worker 1 to Task B (cost 3)
• Worker 2 to Task A (cost 4)
• Worker 3 to Task C (cost 2)
• Total Minimum Cost = 3 + 4 + 2 = 9

How it's Solved:

The Assignment Problem can be solved using various algorithms:
1. Brute Force: Trying every single possible assignment (N! permutations). This is highly
inefficient for large N. For N=10, 10! is already 3,628,800.
2. Hungarian Algorithm (Kuhn-Munkres Algorithm): This is the most famous and
efficient polynomial-time algorithm specifically designed for the Assignment Problem.
It uses concepts from matrix reduction and bipartite matching.
3. Linear Programming: The Assignment Problem can be formulated as a special type
of linear programming problem (specifically, an integer linear program).
4. Network Flow: It can also be modeled as a minimum-cost maximum-flow problem in
a bipartite graph.
5. Backtracking/Branch and Bound: While not the most efficient for typical
Assignment Problems (Hungarian Algorithm is better), you could technically apply
backtracking or branch and bound for smaller instances or as a general search method.

The Assignment Problem is a classic example of a problem that often arises in resource
allocation, scheduling, and operational research.
2. Applying Branch and Bound Technique to Solve:
Knapsack Problem and Traveling Salesman Problem.

Knapsack Problem

The diagram you provided, "FIGURE 12.8 State-space tree of the best-first branch-and-bound
algorithm for the instance of the knapsack problem," illustrates the execution of a best-first
branch-and-bound algorithm to solve a knapsack problem.

Core Concepts:

• Knapsack Problem: A classic optimization problem where you have a knapsack with
a maximum weight capacity and a set of items, each with a weight and a value. The
goal is to select a subset of items that maximizes the total value while staying within
the knapsack's weight limit.
• State-Space Tree: A tree structure where each node represents a partial solution or a
state in the search for the optimal solution.
• Branch and Bound: An algorithmic paradigm used for optimization problems. It
systematically explores the solution space by building a search tree.
 o Branching: The process of creating child nodes from a parent node,
representing different choices (e.g., "with an item" or "without an item").
o Bounding: The process of calculating an upper bound (or lower bound,
depending on the problem) for the optimal solution in the subtree rooted at a
given node. This bound is used to prune branches that cannot lead to a better
solution than the current best known.
• Best-First Search: A search strategy where the next node to explore is the one that
appears most promising, typically based on a heuristic or a bound value. In this case,
it's likely the node with the highest upper bound.

Elements of Each Node:

Each rectangular node in the tree represents a state and contains the following information:

• Node Number: A unique identifier for the node (e.g., 0, 1, 2, ...).

• w (weight): The cumulative weight of the items included in the knapsack for the
solution path leading to this node.
• v (value): The cumulative value of the items included in the knapsack for the solution
path leading to this node.
• ub (upper bound): The estimated maximum possible value that can be achieved in the
subtree rooted at this node. This is a crucial part of the "bound" mechanism. If this
upper bound is less than or equal to the value of an already found feasible solution, the
branch can be pruned.

Branching Decisions:

The branches emanating from each node represent decisions regarding an item:

• "with n": The n-th item is included in the knapsack.

• "w/o n": The n-th item is not included in the knapsack.

Node Classifications/Outcomes:

• "not feasible": The cumulative weight w exceeds the knapsack's capacity. This branch
is pruned as it cannot lead to a valid solution.
• "X inferior to node m": The upper bound (ub) of this node is less than or equal to the
value (v) of a solution found in another node (node m). This means this branch cannot
lead to a better solution than one already identified, so it's pruned.
• "optimal solution": This node represents a complete, feasible solution with the highest
value found so far among the explored paths. This is the goal of the algorithm.

Step-by-Step Explanation of the Tree's Exploration:

trace the execution:

1. Node 0 (Root):
o w = 0, v = 0 (starting with an empty knapsack).
 o ub = 100 (initial upper bound, likely calculated by including fractional parts of
items to get a theoretical maximum).

2. Branching from Node 0 (considering item 1):

o "with 1" (Node 1): Item 1 is included.
▪ w = 4, v = 40 (assuming item 1 has weight 4 and value 40).
▪ ub = 76.
o "w/o 1" (Node 2): Item 1 is not included.
▪ w = 0, v = 0.
▪ ub = 60.
▪ Pruned: "X inferior to node 8". This means at some point, node 8
(which has a value of 65) was found, and the ub of node 2 (60) is less
than 65, so this branch is not worth exploring further.

3. From Node 1 (best-first, as Node 1 has a higher ub (76) than Node 2 (60) initially):

o Branching from Node 1 (considering item 2):

▪ "with 2" (Node 3): Item 2 is included.
▪ w = 11 (e.g., 4 from item 1 + 7 from item 2).
▪ Pruned: "X not feasible". The knapsack capacity has been
exceeded.
▪ "w/o 2" (Node 4): Item 2 is not included.
▪ w = 4, v = 40.
▪ ub = 70.

4. From Node 4 (Node 4's ub (70) is currently the highest among active nodes):
o Branching from Node 4 (considering item 3):
▪ "with 3" (Node 5): Item 3 is included.
▪ w = 9 (e.g., 4 from previous + 5 from item 3).
▪ v = 65 (e.g., 40 from previous + 25 from item 3).
▪ ub = 69.
▪ "w/o 3" (Node 6): Item 3 is not included.
▪ w = 4, v = 40.
▪ ub = 64.
▪ Pruned: "X inferior to node 8". Node 8 has a value of 65, and
node 6's ub (64) is less than 65.

5. From Node 5 (Node 5's ub (69) is currently the highest among active nodes):

o Branching from Node 5 (considering item 4):

▪ "with 4" (Node 7): Item 4 is included.
▪ w = 12.
▪ Pruned: "X not feasible". Knapsack capacity exceeded.
▪ "w/o 4" (Node 8): Item 4 is not included.
▪ w = 9, value = 65.
 ▪ This is a complete, feasible solution. At this point, this becomes
the current_best_value for pruning other branches.

Summary of the Best-First Branch-and-Bound Process:

The algorithm continuously selects the active node with the highest upper bound to expand. It
prunes branches if:
• They become infeasible (exceed weight capacity).
• Their upper bound is less than or equal to the value of the best feasible solution found
so far.

By following this process, the algorithm efficiently explores the solution space, avoiding paths
that cannot lead to the optimal solution, and eventually identifies the "optimal solution" (Node
8 in this case) which has a value of 65 and a weight of 9.

Traveling Salesman Problem

This image illustrates a method called "branch and bound" used to find the shortest possible
"tour" in a weighted graph. Let's break it down:

Part (a): The Weighted Graph

Imagine this as a map with cities (the circles labeled 'a', 'b', 'c', 'd', 'e') and roads connecting
them. Each road has a number next to it – this number represents the "weight" or "cost" of
traveling that road (e.g., distance, time, or money).
• Vertices (Nodes): The circles (a, b, c, d, e).
• Edges (Connections): The lines connecting the circles.
• Weights: The numbers on the edges (1, 2, 3, 4, 5, 6, 7, 8, 9).
The goal is to find a "Hamiltonian circuit" or "Hamiltonian tour." This means you start at one
city, visit every other city exactly once, and then return to your starting city, all while keeping
the total travel cost as low as possible.

Part (b): The Branch-and-Bound State-Space Tree

This is where the "branch and bound" algorithm comes into play.
It's a smart way to explore all possible tours without having to check every single one (which
would be too many for larger graphs).

Here's how it works in simple steps:

1. Starting Point (Node 0):
o You pick a starting city (in this case, 'a').
o lb = 14 (lower bound = 14): This is an estimate of the minimum possible cost
for any tour starting from 'a'. The algorithm calculates this using some clever
tricks (like finding the smallest outgoing edges from each city). It's a guarantee
that no tour will be cheaper than this.
2. Branching Out (Nodes 1, 2, 3, 4):
o From 'a', you can go to 'b', 'c', 'd', or 'e'. Each of these possibilities creates a
"branch" in the tree.
o For each branch (e.g., a, b), a new lb is calculated. This new lb is a lower bound
for all tours that start with 'a' and then go to 'b'.
o Notice that some branches (2, 3, 4) are marked with an 'X'. This means they've
been "pruned" or "bound." Why? Because their lb (lower bound) is already
greater than or equal to l (the cost of the current best tour found so far, which
you'll see later). If a partial tour already looks more expensive than a complete
tour we've already found, there's no point in exploring it further.
3. Continuing to Branch (Nodes 5, 6, 7):
o You pick the branch with the lowest lb to explore next (e.g., a, b at Node 1,
because its lb is 14).
o From a, b, you can go to 'c', 'd', or 'e' (since 'a' is the start and 'b' was just visited).
o Again, new lb values are calculated for these longer partial tours.
o Node 7 (a, b, e) is pruned because its lb (19) is greater than or equal to the l of
Node 11 (16, which is an optimal tour already found).
4. Finding Complete Tours (Nodes 8, 9, 10, 11):
o Eventually, you reach a point where you've visited all cities and can return to
the start. This forms a complete "tour."
o l (length/cost) is calculated for these complete tours.
▪ Node 8 (a, b, c, d, (e, a)): The tour is a -> b -> c -> d -> e -> a. Its cost l
= 24. This is the "first tour" found.
▪ Node 9 (a, b, d, c, (e, a)): The tour is a -> b -> d -> c -> e -> a. Its cost l
= 19. This is a "better tour" than the first one.
▪ Node 10 (a, b, d, c, (e, a)): The tour is a -> b -> d -> c -> e -> a. Its cost
l = 24. This is an "inferior tour" compared to Node 9.
▪ Node 11 (a, b, d, e, (c, a)): The tour is a -> b -> d -> e -> c -> a. Its cost
l = 16. This is currently the "optimal tour" because it's the shortest
complete tour found so far.
5. Pruning with the Best Tour (Nodes 2, 3, 4, 7):
o Once a complete tour is found (like the one at Node 11 with l = 16), this l value
becomes the "upper bound" or "current best solution."
 o Now, any time a new partial tour has a lb (lower bound estimate) that is higher
than this current best l, that branch can be immediately stopped or "pruned"
(marked with 'X'). There's no way it can lead to a shorter tour than what we
already have. This is the "bounding" part of the algorithm, saving a lot of
computation.
Summary:
The branch-and-bound algorithm systematically explores possible tours. It uses "lower bounds"
to estimate the minimum cost of partial tours and "prunes" branches that are guaranteed to be
worse than the best tour found so far. This significantly reduces the amount of searching needed
to find the truly shortest tour.
The final result, after exploring and pruning, is the "optimal tour" (Node 11 in this case), which
has the minimum cost (16).

COMPLETED