MODULE II

FUNDAMENTAL ALGORITHMIC
STRATEGIES
Contents:
 Algorithm strategies
- Divide & Conquer
- Brute-Force
- Greedy
- Dynamic programming
- Backtracking
- Branch-and-Bound
 Problem Solving
- Bin Picking
- Knapsack
- Travelling Salesperson Problem
 Heuristics – characteristics & their application Domain.
 Backtracking

Contents:
 The General Method.
 Control Method: Recursive & Iterative .
 Sum of Subsets.
 8- Queens Problem.
 Graph Colouring.
 0/1 Knapsack problem.
 Hamiltonian Cycle.
 Backtracking

Introduction :
 Backtracking is a algorithm design strategy.

 Uses Brute Force approach.

Brute-Force Approach : Brute force(Exhaustive search) is a straightforward approach to solving a
problem, usually directly based on the problem’s statement and definitions of the concepts involved.
Generally it involved iterating through all possible solutions until a valid one is found.
Ex : A small padlock with 4 digits(each from 0-9).

 Backtracking is not for solving optimization problem.

 Used when all possible solutions need to find out.

 The desired solution is expressible as an n-tuple where the are

chosen from some finite set Si.

 To build the solution vector, criterion function has been applied.

 The solution can be represented in the form of a tree(solution tree/state space tree).
 Backtracking

Introduction : State space

Problem : What are different ways three students(B1B2G1) can seat on three chairs?
n=3 chairs = 3 Therefore all possible arrangements = ?
Solution : (B1B2G1) (B1G1B2) (B2B1G1) (B2G1B1) (G1B1B2) (G1B2B1)

B1 B2 G1 B1 B2 G1

B2 G1 B1 G1 B1 B2 B2 G1 B1 G1 B1 B2

B B
G1 B2 G1 B1 B2 B1 G1 G1 B2 B1

Fig. 1. State Space Tree Fig. 2. Solution Space Tree

 Backtracking

Control Abstraction : Recursive

Algo. 1: Recurssive Backtracking Algorithm

 Backtracking

Control Abstraction : Iterative

Algo. 2: Iterative Backtracking Algorithm

 Backtracking: Sum of Subsets
Sum of Subsets: Problem
 Suppose we are given n distinct positive numbers(usually called weights) .
 We desire to find all combinations of these no’s whose sums are m.
 Finding all these combinations is called sum of subsets problem.
 One could formulate this problem using either fixed- or variable-sized tuples.
 The element xi of the solution vector is either one(1) or zero(0) depending on
whether the weight wi is included or not.
A simple choice for the bounding function is iff

The bounding functions we use are therefore

and
 Backtracking: Sum of Subsets
Sum of Subsets: Problem : Let n=6, m=30 and w={5, 10, 12, 13, 15, 18}.
Find all possible subsets of w that sum to m.

Solution:

Fig 3: Portion of state space tree generated by SumOfSub

 Backtracking: Sum of Subsets
Sum of Subsets: Problem : Let n=6, m=30 and w={5, 10, 12, 13, 15, 18}.

Fig 4: Portion of state space tree showing Ist subset some 1) x[1:6] = x(1, 1, 0, 0, 1, 0)
to 30 2) x[1:6] = x(1, 0, 1, 1, 0, 0)
3) x[1:6] = x(0, 0, 1, 0, 0, 1)
 Backtracking: Sum of Subsets
Sum of Subsets: Algorithm

Algo. 3: Recursive backtracking algorithm for sum of subsets problem

 Backtracking: Sum of Subsets

Variable size solution: w=(1, 12, 18, 30 ), m=30.

Fig. 5 Possible State Space tree organization for sum of subsets (Variable-size).

Solution: 1. (2, 3) 2. (4)

 Backtracking: n-Queens Problem
8-Queens Problem :
 A classic combinatorial problem is to place 8 queens on an 8x8 chessboard in
such a way that no two queens “attack” each other, ie no two of them are on the
same row, column, or diagonal.
 Let us number the rows and columns of the chessboard 1 through 8.
 The queens can also be numbered 1 through 8. Since each queen must be on a
different row, we assume queen i is to be placed on row i.
 Therefore, all solutions to the 8-queens problem can be represented as 8-tuples
(x1, x2,………, x8) where xi is the column on which queen i is placed.
1 2 3 4 ←column
R 1 Q
o Q
2 Solution x[1:4]= x 2 4 1 3
w
↓ 3 Q
4 Q
 Backtracking: n-Queens Problem
8-Queens Problem :

Fig 5. Tree organization of the 4-queens solution space.

 Backtracking: n-Queens Problem
8-Queens Problem :

1 2 3 4
1
2
3
4

Fig 6. Portion of tree of fig 5 that is generated during backtracking

 Backtracking: n-Queens Problem
8-Queens Problem :
Suppose two queens are placed at positions (i, j) and (k, l). Then two queens are
on the same diagonal only if

The first equation implies

The second equation implies

Therefore two queens lie on the same diagonal iff

 Backtracking: n-Queens Problem
8-Queens Problem : Algorithm

Algo 4. All solutions to n-queens problem

 Backtracking: n-Queens Problem
8-Queens Problem : Algorithm

Algo 5. Can a new queen is placed?

 Backtracking: n-Queens Problem
8-Queens Problem : Analysis

Computing time of Place(k, i) is O(k-1)

nC = 64C8 = 4.4 (4426165368) billion tuples to examine

r

But by allowing only placements of queens on distinct rows & columns, we

require the examinations of at most 8 ! = 40, 320 tuples.

The total no of nodes in the 8-queens state space tree is

 Backtracking: Graph Coloring
Graph Coloring : Problem
 m-colorability decision problem
 m-colorability optimization problem
 Planar Graph
 A map & its planar graph representation
 Algorithms mcoloring(), NextValue(k)

Let G be a graph and m be a given positive number. We want to discover whether the
Nodes of G can be colored in such a way that no two adjacent nodes have the same
color yet only m colors are used. This is termed as m-colorability decision problem.
The m-colorability optimization problem asks for the smallest integer m for which
the graph G can be colored. This integer is referred to as the chromatic number of
the graph.
A graph is said to be planar iff it can be drawn in a plane in such a way that no two
edges cross each other.
 Backtracking: Graph Coloring
Graph Coloring : Problem

Fig 7. Example graph & its coloring

Fig8. A map & its planar graph representation

 Backtracking: Graph Coloring
Graph Coloring : Problem

Fig 9. State space tree for mColoring when n=3 & m=3
 Backtracking: Graph Coloring
Graph Coloring : Problem
Find all m- coloring combinations for the following graph using Backtracking
approach(SST) that selects color R for vertex 1. Three colors available are {R, G, B}.

Fig 10. 4-node graph

1 2 3 4
1 0 1 0 1
2 1 0 1 0
3 0 1 0 1
4 1 0 1 0
Fig 12. All possible 3-colorings of graph in fig 8.
Fig 11. Adjacency matrix
Solutions: 1) R,G,R,G 2) R,G,R,B 3) R,G,B,G
of graph in fig 10.
4) R,B,R,G 5) R,B,R,B 6) R,B,G,B
 Backtracking: Graph Coloring
Graph Coloring : Algorithm
Algorithm mColoring(k)
// This algorithm was formed using recursive backtracking schema. The graph is represented by its boolean
// adjacency matrix G[1:n, 1:n]. All assignments of 1, 2, 3, …, m to the vertices of a graph such that
// adjacent vertices are assigned distinct integers are printed. K is the index of the next vertex to color.
{
repeat
{ // Generate all legal assignments for x[k].
NextValue(k) ; // Assign to x[k] a legal color.
if (x[k] = 0) then return; // No new color possible
if (k = n) then // At most m colors have been used to color n vertices.
write(x[1:n]);
else mColoring(k+1);
} until (false);
}
Algo 6. Finding all m-colorings of a graph
 Backtracking: Graph Coloring
Graph Coloring : Algorithm
Algorithm NextValue(k)
// x[1], …, x[k-1] have been assigned integer values in the range [1, m] such that adjacent vertices have
// distinct integers. A value fir x[k] is determined in the range [0, m]. X[k] is assigned the next highest
// numbered color while maintaining distinctness from the adjacent vertices of vertex k. If no such color
// exists, then x[k] = 0.
{
repeat
{
x[k] := (x[k+1]) mod (m+1) ; // Next highest color.
if (x[k] = 0) then return; // All colors have been used.
for j := 1 to n do // Check if this color is distinct from adj. colors.
{
if ((G[k, j] ≠ 0 and (x[k] = x[j])) then // If (k, j) is and edge and id adj. vertices have
break; // the same color.
}
if (j = n+1) then return; // New color found.
} until (false); // Otherwise try to fine another color
}
Algo 7. Generating a next color
 Backtracking: Graph Coloring

Graph Coloring : Analysis

An upper bound on the computing of mColoring() can be found by

noticing the number of internal nodes in the state space tree is

At each internal node, O(mn) time is spent by NextValue() to determine the

children corresponding to legal colorings.

Hence. Total time is bounded by

 Backtracking: 0/1 Knapsack
0/1 Knapsack : Problem
Given n positive weights wi, n positive profits pi, and a positive number
m that is the knapsack capacity, this problem calls for choosing a subset of the
weights such that

The xi’s constitute a zero-one-valued (0/1) solution vector.

The solution space is the same as that for the sum of subsets problem.
If the object weights and profits are w[i] and p[i] then it is assumed that

p[i]/w[i] ≥ p[i+1]/w[i+1], 1 ≤ I < n.

 Backtracking: 0/1 Knapsack
0/1 Knapsack : Problem
Consider the instance of the 0/1 Knapsack problem : n= 8 p=(11, 21, 31, 33, 43, 53,
55, 65), w=(1, 11, 21, 23, 33, 43, 45, 55) , m= 110. Find all the solutions.
Solution:

Fig. Portion of the state space tree of the solution

 Backtracking: 0/1 Knapsack

0/1 Knapsack : Problem

Consider the instance of the 0/1 Knapsack problem : n= 8 p=(11, 21, 31, 33, 43, 53,
55, 65), w=(1, 11, 21, 23, 33, 43, 45, 55) , m= 110. Find all the solutions.
Solution:
b+(1- ( c-m)/ w[i]) * p[i]
139 + (1- (134 - 110)/ 45) * 55 = 139 + ( 1- 24/45) * 55 = 164.88

1) x(1:8) = x(1, 1, 1, 1, 1, 0, 0, 0) P= 139 W = 89

2) x(1:8) = x(1, 1, 1, 1, 0, 1, 0, 0) P= 149 W = 99
3) x(1:8) = x(1, 1, 1, 1, 0, 0, 1, 0) P= 151 W = 101
4) x(1:8) = x(0, ….. )
:
:
 Backtracking: 0/1 Knapsack
0/1 Knapsack : Algorithm

Algo. 8. Algorithm for a bounding function

 Backtracking: 0/1 Knapsack
0/1 Knapsack : Algorithm

Algo. 9 : Backtracking solution to the 0/1 knapsack problem

 Branch And Bound

Contents:

 The Method.
- FIFO Branch-and Bound
- LIFO Branch-and Bound
- LC Branch-and-Bound

 0/1 Knapsack Problem.

 Job Sequencing with Deadlines

 Travelling Salesperson Problem.

 Branch And Bound

 Branch & Bound is very much similar to Backtracking.

 It uses state space tree to solve the problem.

 That is solution is represented like a state space tree.

 But unlike Backtracking, Branch & Bound design strategy is useful for solving
optimization (only minimization not maximization) problems.

 But any way, we can covert maximization problems into minimization problem
and then we can solve it branch & bound.
 Branch And Bound
Branch & Bound:The Method
Example : Let n=4, (p1 , p2 , p3 ) = (100, 10, 15, 27) and (d1 , d2 , d3 ) = (2, 1, 2, 1).
Find all feasible solutions and their values .
Solution : FIFO (First-in-First-Out) B & B Variable size

Fig. 1 FIFO B&B State space tree for variable size tuple Q 2 3 4 5 6 7 9
 Branch And Bound
Branch & Bound:The Method
Example : Let n=4, (p1 , p2 , p3 ) = (100, 10, 15, 27) and (d1 , d2 , d3 ) = (2, 1, 2, 1).
Find all feasible solutions and their values .
Solution : LIFO (Last-in-First-Out) B & B Variable size

5 6
4
3
2
S
Fig. 2 LIFO B&B State space tree for variable size tuple
 Branch And Bound
Branch & Bound:The Method
Example : Let n=4, (p1 , p2 , p3 ) = (100, 10, 15, 27) and (d1 , d2 , d3 ) = (2, 1, 2, 1).
Find all feasible solutions and their values .
Solution : LC (Least Cost) B & B Variable size

Fig. 3 Least Cost B&B State space tree for variable size tuple
 Branch And Bound
Control Abstraction : LC Search

Algo. 1 Control Abstraction for Least Cost Search

 B&B: JSWD
Job Sequencing With Deadlines :
Problem : n jobs, deadline di >= 0 and profit pi >0

For any job i profit pi is earned iff the job is completed by its deadline. To complete
a job, one has to process the job for one given unit of time ti > 0.Only one machine
is available for processing the jobs.
 B&B: JSWD
Job Sequencing With Deadlines :
Problem : : Let n=4, (p1 , p2 , p3 , p4 ) = (5, 10, 6, 3), (d1 , d2 , d3 , d4 ) = (1, 3, 2, 1) and
(t1 , t2 , t3 , t4 ) = (1, 2, 1,1). Find optimal solution using variable tuple size FIFO B&B.
Solution:

Jobs -> 1 2 3 4

Profit Penalty 5 10 6 3
deadline 1 3 2 1
time 1 2 1 1
 B&B: JSWD
Job Sequencing With Deadlines : 1 2 3 4
Jobs ->
Solution: Profit Penalty 5 10 6 3
deadline 1 3 2 1
time 1 2 1 1

Solution:
x[] = x[J2, J3]
Penalty = 10+ 6 = 16
x[] = x[J1, J4]
Penalty = 5 + 3 = 8
Fig. 3 FIFO B&B State space tree for variable size of problem solution
 B&B: 0/1 Knapsack
0/1 Knapsack problem: LC B & B :

 Need to find upper bound & cost of every node in the state space tree.

B & B solves only minimization problem. But 0/1 Knapsack is maximization

problem.

So we need to convert this problem into minimization problem. To convert let us

consider all profits of objects as negatives.

Similarly all upper bound & cost values are also negative.
 B&B: 0/1 Knapsack
0/1 Knapsack problem: Solve the 0/1 Knapsack problem using LC B & B
approach for the instance : n =4, (w1 , w2 , w3 , w4) = (2, 4, 6, 9), (p1 , p2 , p3 , p4) =
(10, 10, 12, 18) , & m= 15.
Solution :

Upper = ∞, -32, -38

Solution:
x[1:4] = x[1, 1, 0, 1]
Profit = 10+ 10 + 0 + 18 = 38
Cost/Knp wt = 2+4+0+9 = 15
Fig. 3 LC branch-and bound state space tree for the problem (Fixed size tuple)
 B&B: 0/1 Knapsack
0/1 Knapsack problem: Solve the 0/1 Knapsack problem using LC B & B
approach for the instance : n =4, (w1 , w2 , w3 , w4) = (2, 4, 6, 9), (p1 , p2 , p3 , p4) =
(10, 10, 12, 18) , & m= 15.
Solution :

Fig. 3 FIFO branch-and bound state space tree for the problem
 B&B: 0/1 Knapsack

0/1 Knapsack problem: Algorithm

Algo. 2 Function UBound for Knapsack problem

 B&B: Travelling Salesperson Problem
Travelling Salesperson problem: Algorithm

 Let G = (V, E) be a directed weighted graph defining an instance of the travelling

salesperson problem.
 Let ci j equal to the cost of an edge <i, j> and & let |V| = n.
 Assume that every tour starts & ends at vertex 1. So, the solution space is given
by . Then

Fig. 8 SST for TSP with n= 4 & start vertex is 1

 B&B: Travelling Salesperson Problem
Travelling Salesperson problem:

 Let c(.) be a cost function and be a cost function with reduced matrix.
 A row(column) of a matrix is said to be reduced iff it contains at least one zero
& all other entries are non-negative.
 A matrix is said to be reduced iff every row & column is reduced.

1) Change all entries in row I & column j of A to ∞.

2) Set A(j, 1) to ∞ .
3) Reduce all rows & columns in the resulting matrix except for rows &
columns containing only ∞ .
Let the resulting matrix be B. If r is the total amount subtracted in step
3 then

For upper bound function u, we can use u(R) = ∞ for all nodes R.
That’s it.