SUBJECT NAME : Design and Analysis of Algorithm

SUBJECT CODE : CCS53

SEMESTER : V

UNIT – V: BACKTRACKING & BRANCH AND BOUND

1. The General Method
2. The 8 Queens Problem
3. Sum of Subsets
4. Graph Coloring
5. Hamiltonian Cycles
6. Branch and Bound: General Method
7. LC Branch and Bound
8. FIFO Branch and Bound.
1.General method:

In this topic, we will learn about the backtracking, which is a very important skill set to solve
recursive solutions. Recursive functions are those that calls itself more than once. Consider an
example of Palindrome:

Initially, the function isPalindrome(S, 0, 8) is called once with the parameters isPalindrome(S, 1,
7). The recursive call isPalindrome(S, 1, 7) is called once with the parameters isPalindrome(S, 2,
6).

Backtracking is one of the techniques that can be used to solve the problem. We can write the
algorithm using this strategy. It uses the Brute force search to solve the problem, and the brute
force search says that for the given problem, we try to make all the possible solutions and pick
out the best solution from all the desired solutions. This rule is also followed in dynamic
programming, but dynamic programming is used for solving optimization problems. In contrast,
backtracking is not used in solving optimization problems. Backtracking is used when we have
multiple solutions, and we require all those solutions.

Backtracking name itself suggests that we are going back and coming forward; if it satisfies the
condition, then return success, else we go back again. It is used to solve a problem in which a
sequence of objects is chosen from a specified set so that the sequence satisfies some criteria.

When to use a Backtracking algorithm?

When we have multiple choices, then we make the decisions from the available choices. In the
following cases, we need to use the backtracking algorithm:

o A piece of sufficient information is not available to make the best choice, so we use the
backtracking strategy to try out all the possible solutions.

o Each decision leads to a new set of choices. Then again, we backtrack to make new
decisions. In this case, we need to use the backtracking strategy.

How does Backtracking work?

Backtracking is a systematic method of trying out various sequences of decisions until you find
out that works. Let's understand through an example.

We start with a start node. First, we move to node A. Since it is not a feasible solution so we
move to the next node, i.e., B. B is also not a feasible solution, and it is a dead-end so we
backtrack from node B to node A.
Suppose another path exists from node A to node C. So, we move from node A to node C. It is
also a dead-end, so again backtrack from node C to node A. We move from node A to the
starting node.

Now we will check any other path exists from the starting node. So, we move from start node to
the node D. Since it is not a feasible solution so we move from node D to node E. The node E is
also not a feasible solution. It is a dead end so we backtrack from node E to node D.
Suppose another path exists from node D to node F. So, we move from node D to node F. Since
it is not a feasible solution and it's a dead-end, we check for another path from node F.

2. The 8 Queens Problem

The eight queens problem is the problem of placing eight queens on an 8×8 chessboard
such that none of them attack one another (no two are in the same row, column, or diagonal).
More generally, the n queens problem places n queens on an n×n chessboard.

Algorithm:

 Create a function backtrack that simply places the queens on corresponding rows and
columns and marks them visited.
 The working of backtrack is as follows:
o If the current row is equal to 8, then a solution has been found. Therefore, add this
to the answer.
o Traverse through the columns of the current row. At each column, try to place the
queen in (row, col):
 Calculate the diagonal and anti-diagonal which the current square
belongs to. If it is unvisited, place the queen in the (row, col).
 Skip this column, if the queen cannot be visited.
o If the queen has been placed successfully, call the backtrack function of row + 1.
o Since, all paths have now been explored, clear the values of the queens placed so
far and the visiting arrays, so that next distinct solution can be found.

3. Subset Sum Problem

It is one of the most important problems in complexity theory. The problem is given an A set
of integers a1, a2,…., an upto n integers. The question arises that is there a non-empty subset
such that the sum of the subset is given as M integer?. For example, the set is given as [5, 2, 1, 3,
9], and the sum of the subset is 9; the answer is YES as the sum of the subset [5, 3, 1] is equal to
9. This is an NP-complete problem again. It is the special case of knapsack

Let's understand this problem through an example.

problem.

We have a set of 5 integers given below:

N = 4, -2, 2, 3, 1

We want to find out the subset whose sum is equal to 5. There are many solutions to this
problem.

The naïve approach, i.e., brute-force search generates all the possible subsets of the original
array, i.e., there are 2n possible states. Here the running time complexity would be exponential.
Then, we consider all these subsets in O(N) linear running time and checks whether the sum of
the items is M or not.

The dynamic programming has pseudo-polynomial running time.

Statement: Given a set of positive integers, and a value sum, determine that the sum of the
subset of a given set is equal to the given sum.

Or

Given an array of integers and a sum, the task is to have all subsets of given array with sum
equal to the given sum.

1. Example 1:
2. Input: set[] = {4, 16, 5, 23, 12}, sum = 9
3. Output = true
4. Subset {4, 5} has the sum equal to 9.
5.
6. Example 2:
7. Input: set[] = {2, 3, 5, 6, 8, 10}, sum = 10
8. Output = true
9. There are three possible subsets that have the sum equal to 10.
10. Subset1: {5, 2, 3}
11. Subset2: {2, 8}
12. Subset3: {10}
There are two ways of solving the subset problem:

o Recursion
o Dynamic programming

Before knowing about the recursive approach, we should know about two things in a subset
which are given below:

o Include: Here include means that we are selecting the element from the array.
o Exclude: Here, exclude means that we are rejecting the element from the array.

To implement the recursive approach, we consider the following two cases:

o Now we consider the first element and now the required sum is equal to the difference
between the target sum and value of first element. The number of elements is equal to the
difference between the total elements and 1.
o Leave the 'first' element and now the required sum = target sum. The number of elements
is equal to the difference between the total elements and 1.

Let's understand that how can we solve the problem using recursion. Consider the array
which is given below:

arr = [3, 4, 5, 2]

sum = 9

Method 2: Dynamic Programming

Let A be an array or set which contains 'n' non-negative integers. Find a subset 'x' of set 'A' such
that the sum of all the elements of x is equal to w where x is another input (sum).

For example:

A = {1, 2, 5, 9, 4}

Sum(w) = 18

Now we have to find out the subset from the given set whose sum is equal to 18. Here we will
use the dynamic programming approach to solve the subset sum problem.

Example:
A = [2, 3, 5, 7, 10]

Sum(w) = 14

First, we create a table. The column contains the values from 0 to 14 while row contains the
elements of the given set shown as below:

In the below table:

i: It represents the rows. Rows represents the elements.

j: It represents the columns. Columns represent the sum.

Consider the element 2. We will use 1 as a true value and 0 as a false value. The value 1
comes under 0 and 2 columns shown as below:

Here i=1, a[i] =2

Note: The rule for filling each column is given below:

Required sum = j - element
A[i][j] = A[i-1][required sum]

When j= 1

Required sum = 1 - 2 = -1; Since the sum is negative so put 0 under the column 1 as shown in
the above table.

When j= 2

Required sum = 2 - 2 = 0; Since the value of sum is zero so we put 1 under the column 2 as
shown in the above table.

We put 0 under the columns whose sum is greater than 2 as we cannot make sum more than 2
from the element 2.
Consider the element 3.

Here i = 2, a[i] = 3

The columns whose sum is less than 3 will have the same values as the previous columns.

Graph coloring is the procedure of assignment of colors to each vertex of a graph G such that no
adjacent vertices get same color. The objective is to minimize the number of colors while
coloring a graph. The smallest number of colors required to color a graph G is called its
chromatic number of that graph. Graph coloring problem is a NP Complete problem.

4. Graph Coloring
Method to Color a Graph
The steps required to color a graph G with n number of vertices are as follows −
Step 1 − Arrange the vertices of the graph in some order.
Step 2 − Choose the first vertex and color it with the first color.
Step 3 − Choose the next vertex and color it with the lowest numbered color that has not been
colored on any vertices adjacent to it. If all the adjacent vertices are colored with this color,
assign a new color to it. Repeat this step until all the vertices are colored.
Example
In the above figure, at first vertex a is colored red. As the adjacent vertices of vertex a are again
adjacent, vertex b and vertex d are colored with different color, green and blue respectively.
Then vertex c is colored as red as no adjacent vertex of c is colored red. Hence, we could color
the graph by 3 colors. Hence, the chromatic number of the graph is 3.

Applications of Graph Coloring

Some applications of graph coloring include −

 Register Allocation
 Map Coloring
 Bipartite Graph Checking
 Mobile Radio Frequency Assignment
 Making time table, etc.

In an undirected graph, the Hamiltonian path is a path, that visits each vertex exactly once, and
the Hamiltonian cycle or circuit is a Hamiltonian path, that there is an edge from the last vertex
to the first vertex.
In this problem, we will try to determine whether a graph contains a Hamiltonian cycle or not.
And when a Hamiltonian cycle is present, also print the cycle.
Input and Output
Input:
The adjacency matrix of a graph G(V, E).
Output:
The algorithm finds the Hamiltonian path of the given graph. For this case it is (0, 1, 2, 4, 3, 0).
This graph has some other Hamiltonian paths.
If one graph has no Hamiltonian path, the algorithm should return false.
Algorithm
isValid(v, k)
Input − Vertex v and position k.
Output − Checks whether placing v in the position k is valid or not.

5. Branch and Bound: General Method

What is Branch and bound?

Branch and bound is one of the techniques used for problem solving. It is similar to the
backtracking since it also uses the state space tree. It is used for solving the optimization
problems and minimization problems. If we have given a maximization problem then we can
convert it using the Branch and bound technique by simply converting the problem into a
maximization problem.

Let's understand through an example.

Jobs = {j1, j2, j3, j4}

P = {10, 5, 8, 3}

d = {1, 2, 1, 2}

The above are jobs, problems and problems given. We can write the solutions in two ways which
are given below:

Suppose we want to perform the jobs j1 and j2 then the solution can be represented in two ways:
The first way of representing the solutions is the subsets of jobs.

S1 = {j1, j4}

The second way of representing the solution is that first job is done, second and third jobs are not
done, and fourth job is done.

S2 = {1, 0, 0, 1}

The solution s1 is the variable-size solution while the solution s2 is the fixed-size solution.

First, we will see the subset method where we will see the variable size.

First method:

In this case, we first consider the first job, then second job, then third job and finally we consider
the last job.

As we can observe in the above figure that the breadth first search is performed but not the depth
first search. Here we move breadth wise for exploring the solutions. In backtracking, we go
depth-wise whereas in branch and bound, we go breadth wise.

7.LC Branch and Bound

Branch and bound is an algorithm to find the optimal solution to various
optimization problems. It is very similar to the backtracking strategy, only just in the
backtracking method state-space tree is used. The benefit of the branch and bound
method is that it does not limit us to only a certain way of traversing the tree. Though it
also has certain drawbacks, one being it is much slower and gets an exponential time
complexity in the worst cases. The branch and bound method are applicable to many
discrete combinational problems.
The branch and bound can be solved using FIFO, LIFO, and least count strategies.
The selection rule used in the FIFO or LIFO linked list can sometimes be erroneous, as it
does not give preference to certain nodes, and hence may not find the best response as
quickly. To overcome this drawback we use the least cost method, which is also
considered to be an intelligent method as it uses an intelligent ranking method. It is also
referred to as the approximate cost function “C”.
The least-cost method of branch and bound selects the next node based on the
Heuristic Cost Function, and it picks the one with the least count, therefore it is one of
the best methods. In the 0/1 knapsack problem, we need to maximize the total value, but
we cannot directly use the least count branch and bound method to solve this.
Therefore, we convert this into a minimization problem by taking the negative of the
given values.
The steps to solve the 0/1 Knapsack problem is as follows:
1. We need to sort the items based on the value/ weight ratio.
2. A dummy node is inserted in the priority queue.
3. Then we follow the following steps until the priority queue is empty:
 The peak element from the priority queue is extracted and inserted into the current node.
 When the upper bound of the current node is less than the minimum lower bound then we
proceed further with the next element.
 We do not consider the elements with upper bounds more than the minimum lower bound as the
upper bound stores the best value, and if the best value is itself not optimal than the minimum
lower bound then exploring further is of no use.

1. Then update the path array.

2. We check the node level of the current node, if the lower node level of the current node is less
than the final lower bound then we update the final path and final lower bound. If it is not less
than the final lower bound then we continue with the next element.
3. The lower and upper bounds of the right child of the current node are calculated.
4. Then we calculate the lower and upper bounds of the left child of the current node if the current
item can be inserted in a knapsack.
5. We finally update the minimum lower bound and insert the children, in case the upper bound is
less than the minimum lower bound.

8. FIFO Branch and Bound.

FIFO Branch and Bound solution is one of the methods of branch and bound.
Branch and Bound is the state space search method where all the children E-node that is
generated before the live node, becomes an E- node.
FIFO branch and bound search is the one that follows the BFS like method. It does so as
the list follows first in and first out.
Some key terms to keep in mind while proceeding further:
What is a live node?
A live node is the one that has been generated but its children are not yet generated.

What is an E node?
An E node is the one that is being explored at the moment.

What is a dead node?

A dead node is one that is not being generated or explored any further. The children of
the dead node have already been expanded to their full capacity.

Branch and Bound solution have three types of strategies:

1. FIFO branch and bound.
2. LIFO branch and bound.
3. Least Cost branch and bound.

In this article, we have briefly discussed the FIFO branch and bound.

To proceed further with the FIFO branch and bound we use a queue.
In FIFO search the E node is assumed as node 1. After that, we need to generate children
of Node 1. The children are the live nodes, and we place them in the queue accordingly.
Then we delete node 2 from the queue and generate children of node 2.
Next, we delete another element from the queue and assume that as the E node. We then
generate all its children.
In the same process, we delete the next element and generate their children. We keep
repeating the process till the queue is covered and we find a node that satisfies the
conditions of the problem. When we have found the answer node, the process terminates.

Let us understand it through an example:

We start by taking an empty queue:

In the given diagram we have assumed that node 12 is the answer node.
As mentioned we start by assuming node 1 as the E node and generate all its children.
2 3 4

Then we delete node 1 from the queue, take node 2 as the E node, and generate all its
children:
3 4 5 6

We delete the next element and generate children for the next node, assuming it to be the
E node.
4 5 6

We repeat the same process. The generated children of 4, that is node 9 are killed by the
boundary function.
5 6

Similarly, we proceed further, but the children of nodes 5, meaning the nodes 10, and 11
are also generated and killed by boundary function. The last standing node in the queue is
6, the children of node 6 are 12, and it satisfies all the conditions for the problem,
therefore it is the answer node.