UNIT V

Backtracking

Backtracking

​

1. The General Method

​

• The 8-Queens Problem

​

• Sum of Subset's

​

• Graph Colouring

​

The General Method

• Backtracking is one of the important algorithm design technique.

​

• Many problems which deal with searching for a set of solutions or ask for an optimal solution satisfying some constraints can be solved using backtracking.

​

• The name backtracking was defined by D.H Lemmer in 1950’s.

​

• All the solutions solved using backtracking must satisfy two constrains

1.Explicit constraints

2.Implicit constraints

​

• Backtracking follows Depth first approach(DFS)

​

• Explicit constraints are the rules which restrict each x_i to take on values from a given set.

Example: x_i ≥ 0 or S={set of all non negative real numbers}

x_i =0 or x_i =1 or S={0,1}

• Explicit constraints depends on the particular instance of the problem being solved. All the tuples that satisfy explicit constraints defines the possible solution space for ‘i’

​

• The implicit constraints are the rules that determines which of the tuples in the solution space satisfies the criterion function.

​

• If the solution is expressible as an n-tuples (x₁, x₂, x₃,----- x_n) where x_i are chosen from finite set, then we can apply backtracking.

(x₁, x₂, x₃, x₄)=(2,4,1,3)

• Generally backtracking solves three types of problems

​

Enumeration problems: find all possible solutions

​

Decision problems: is there any feasible solution or not

​

Optimization problems: whether there exits any best solution.

​

• State space tree: In backtracking while solving a given problem, a tree is constructed based on the choices made. Such a tree with all possible solutions are called a state space tree.

​

• The tree organization of the solution of the state space is referred to as state space tree.

• Each state space tree consists of the following nodes

1.Live node: A node which has been generated but its children have not yet

been generated is called a “live node”

​

2.E-node:A live node whose children are currently being generated is

called a “E-node”.

​

3.Dead node: A node which is already expanded and there is no use for

future.

​

• Bounding functions are used to kill live nodes without generating its children.

​

• A node in a state space tree is said to be promising. If it corresponds to a partially constructed solution that may lead to a complete solution.

In other words, if we expand the node, if it gets the complete solution,

then it is called a promising node.

​

• A node in a state space tree is said to be non-promising, if it can not lead to a complete solution.

​

• Each node in the state space tree defines a problem statement. All paths from root node to leaf nodes or other nodes defines problem state space.

​

• Solution states are the problem states S for which the path from the root to S defines a tuple in the solution space.
• Answer states are those solution state S for which the path from root to S defines a tuple which is a member of the set of solution of the given problem.

The n-Queens Problem

To solve the n×n board problems we have to follow the following constraints.

1.No two Queens are in the same row

2.No two Queens are in the same column

3.No two Queens are in the same diagonal

Example:

Let us take n=1 n=2

​

​

This is called a trivial solution

​

Let take n=3

​

​

​

​

Q1

1

1

1

2

1

2

no solution when n=2

1 2 3

1

​

2

​

3

No solution when n=3

Let us take when n=4

​

The solution vector is

(x₁, x₂, x₃, x₄)=(2,4,1,3)

​

​

Q_i can be placed on i^th row

​

When two coordinates (i,j) and (k,l) are diagonal elements then these two pairs satisfies the following condition.

|i-k|=|j-l|

Here the explicit constraints are S_i ={1,2,3,4}

​

1 2 3 4

1

​

2

3

​

4

4 Queen problem: State space tree

8 Queen problem

1 2 3 4 5 6 7 8

Sum of subsets

x_k =1

x_k =0

​

Draw the state space tree for m=31 and w[1:4]={7,11,13,24}

0,1,55

7,2,48

0,2,48

x₁ =1

​

x₁ =0

​

18,3,37

7,3,37

x₂ =1

​

x₂ =0

​

31,4,24

18,4,24

x₃ =1

​

x₃ =0

​

42,5,0

18,5,0

x₄ =1

x₄ =0

Kill the node because 42>31

We are using bounding function

20,4,24

7,4,24

x₃ =1

x₃ =0

​

44,5,0

20,5,0

x₄ =1

x₄ =0

44>31

31,5,0

7,5,0

x₄ =1

x₄ =0

Solution 2

Solution 1

Right sub tree

0,2,48

11,3,37

0,3,37

x₂ =1

x₂ =0

24,4,24

11,4,24

x₃ =1

x₃ =0

48,5,0

24,5,0

x₄ =1

x₄ =0

35,5,0

11,5,0

x₄ =1

x₄ =0

13,4,24

0,4,24

x₃ =1

x₃ =0

Kill the node because 48>31

We are using bounding function

​

35>31

37,5,0

13,5,0

x₄ =1

x₄ =0

37>31

24,5,0

0,5,0

x₄ =1

x₄ =0

Graph Colouring

• Let G=(V,E) be a graph, in graph colouring problem, we have to find whether all the vertices of the given graph are coloured or not, with the constraint that no two adjacent vertices have the same colour.

​

​

​

​

​

​

​

• The problem has two versions

1.m-colourability decision problem

2.m-colourability optimization problem

a

b

c

d

e

• Chromatic number: the minimum no of colours required to colour the all vertices of the given graph is called chromatic number.

​

• If the degree of the graph is ‘d’ then it can be coloured with ‘d+1’ colours

Example:

​

​

​

​

​

a

b

c

Example: draw the state space tree for n=4 and m=3

Branch and Bound

Branch and Bound

​

1. The General Method

​

• The Travelling Salesperson Problem(LCBB)

​

• 0/1 knapsack problem(FIFO AND LCBB)

​

​

The General Method

• Branch and Bound is a systematic method for solving optimization problems.

​

• Branch and Bound technique applied when the Greedy and dynamic programming methods may fail.

​

• Branch and Bound is much slowest.Indeed,it often leads to exponential time complexity in the worst case. On the other hand, if applied carefully, It can lead to algorithms that run reasonably fast on average.

​

• The general idea of branch and bound is BFS like search for optimal solution but not all the nodes get expanded. Rather, a carefully selected criterion determining which node to expand and when and another criteria tells the algorithm when a optimal solution has been found.

• Both BFS and DFS generalizes to branch and bound strategies

1.BFS is an FIFO search in terms of live nodes. List of live nodes is a

queue.

2.DFS is an LIFO search in terms live node. List of live nodes is a stack

3.Least cost search based on the minimum cost.

​

• Just like in backtracking, we will use bounding functions to avoid generating subtrees that do not contain an answer node.

​

• The branch and Bound refers to all the state space search method in which all the children of an E-node are generated before any other live node become the E-node.

Example:

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

Here c^ is a ranking function

1

2

3

4

5

6

7

8

C^=2

C^=3

C^=4

C^=3

C^=2

C^=1

C^=5

• Branch and bound method of algorithm design involves:

1.Tree organization of solution space

2.Use of bounding functions to limit the search that is to avoid the

generation of subtrees that do not contain answer node

• The application of branch and bound technique is

1.0/1 knapsack problem

2.Travelling Sales person problem

3.Job sequencing with deadlines

​

• Bounds can be used in Least cost branch and bound(LCBB)

1.Lower bound(c^)

2.Upper bound(u^)

• While calculating the c^ for a node in state space tree, fractions are allowed.
• While calculating the u^ for a node in state space tree, fractions are not allowed.
• Which node of c^ is minimum that node can be expanded, that node becomes the E-node.
• In case of FIFO branch and bound we have to calculate three bounds

1.Lower bound(c^(x))

2.Upper bound(u^(x)) where x is a any node

3.Global Upper Bound(U^(x))

​

​

• To expand a node in FIFO, the following constraints is used

if a lower bound of a node c^(x) is greater than global upper bound then we

kill the node otherwise we have to expand the node

The Traveling salesman problem

• Let G=(V,E) be a directed graph defining an instance of TSP.

where V is set of vertices and E is set of edges

The edges are given along with their cost C_ij where C_ij >0 for all i,j

​

cost(i,j) C_ij if (i,j) ϵ E(G)

ꝏ if (i,j) ϵ E(G)

​

Let |V|=n

• The solution space S is given by S={1,∏,1/∏ is permutation of (2,3,…..n)} then |S|=(n-1)!

​

• The size of S can be reduced by restricting S so that (1, i₁, i₂, i₃,….. i_n-1,1) ϵ S

iff < i_j, i_j+1 > ϵ E , 0≤j≤n-1 and i₀, i_n ϵ1

• To use least cost branch and bound to search TSP state space tree, we need to define a cost function C and two other function C^ and u such that C^(r)≤C(r)≤u(r) for all nodes r

​

• Subtracting a constant ‘t’ from every entry in row or column reduce the cost of tour by t.

1.Substract from row: subtract t from each out going edge of i

2.Substract from column: Subtract t from each in coming edge j

​

• A matrix is reduced iff every row and column is reduced.

Example: Solve the following TSP problem using LCBB.

If (R,S) is an edge

Cost(R)=sum of minimum value of each row + sum of minimum value from each column

Cost(R)=21+4=25

​

Finding the cost for node 2

Node 2 🡪include the edge <1,2>

​

1.Change all the entries in row ‘i’ and column ‘j’ to ꝏ (prevents use of any more vertex leaving ‘i’ or entering ‘j’ )

​

2.Set C¹(j,1)=ꝏ (which prevents use of edge <j,1>

​

3.Reduce all rows and columns in resulting matrix except for rows and columns containing ꝏ

r=total subtracted in reduction (3)

The resultant matrix is C² is

Finding the cost for node 3

Node 3-> include the edge <1,3>

​

​

​

Finding the cost for node 4

Finding the cost for node 5

Similarly find the cost for node 6,7,8 and expand the least cost node

Find the cost for node 6

​

​

​

​

​

​

​

​

​

3+25+0=28

Similarly find cost for node 7 and node 8

Next node to be expanded is node 6 since it has least cost

Next node to be expanded is node 6 since it has least cost

Similarly find cost for node 10,the cost(10)=28

Next node to be expanded is node 10 since it has least cost

Node 10 includes <2,5> edge

Step1:Make row 2 and column 5 as ꝏ

Step 2: C⁶ [5,1] as ꝏ

Step 3:Reduce rows and column

ꝏ ꝏ ꝏ ꝏ ꝏ

ꝏ ꝏ ꝏ ꝏ ꝏ

0 ꝏ ꝏ ꝏ ꝏ

11 ꝏ 0 ꝏ ꝏ

​

Cost(10)= C⁶ [2,5] + cost(parent) + r

=0+28+0=28

find cost for node 10,the cost(10)=28

Next node to be expanded is node 10 since it has least cost

Find cost for node 11,the cost(11)=28

The tour is 1-4-2-5-3-1

0/1 knapsack Problem

Notion of Branch-and-Bound

• In 0/1 knapsack problem. We define upper(the global variable) and c’(x) and u(x) for each node.

​

• c’(x) is the used to find the cost of the node(or effort) starting from the root.

In 0/1 knapsack c’(x) means the maximum profit at that node(with fractions ).

​

• u(x) is used to find an improved upper bound value.

In 0/1 knapsack u(x) means the maximum profit at that node (without fractions).

​

• After the E-node is expanded
• It generates a list of live nodes
• c’(x) and u(x) is calculated for each generated live node.
• If an improved u(x) is generated for any newly generated live node then, update upper to u(x).
• Kill the nodes whose c’(x) is greater than upper(updated)

​

• The selection of next E-node is depends on the approach used.
• LC BB – selects whose live nodes cost is least
• FIFO BB – selects from next live node from the queue
• LIFO BB- selects from next live node from the stack

0/1 knapsack Problem-using Least Cost(LC) BB

1

c’(1)= -38

u (1)= -32

Consider the knapsack instance with n =4, (p1,p2,p3,p4)=(10,10,12,18) ,

(w1,w2,w3,w4) = (2,4,6,9) and m=15 .

Cost function - c’(x) - The profit obtained using the given instance (with fractions allowed)i.e; c’(1) =

Improved upper bound - u(x) – The profit obtained using the given instance(without allowing fractions) i.e., u(1) =

Note: Since, object 4 cannot be placed in the bag ,so fraction

of it i.e., 3/9 can be placed .

upper = -32

1

c’(1)= -38

u (1)= -32

Consider the knapsack instance with n =4, (p1,p2,p3,p4)=(10,10,12,18) ,

(w1,w2,w3,w4) = (2,4,6,9) and m=15 .

c’(3) (with fractions allowed) =

u(3) (without allowing fractions) =

Note: Since, object 4 cannot be placed in the bag ,so fraction

of it i.e., 5/9 can be placed .

2

3

x₁=1

x₁=0

c’(3)= -32

u(3)= -22

c’(2)= -38

u (2)= -32

• Among the live nodes 2 and 3

which node to expand?

• The least cost node to be expanded i.e.,

Node 2 is expanded. Since , c’(2)<c’(3)

upper = -32

1

c’(1)= -38

u (1)= -32

Consider the knapsack instance with n =4, (p1,p2,p3,p4)=(10,10,12,18) ,

(w1,w2,w3,w4) = (2,4,6,9) and m=15 .

c’(5) =

u(5)=

Note: Since, object 4 cannot be placed in the bag ,so fraction

of it i.e., 7/9 can be placed .

2

3

x₁=1

x₁=0

c’(3)= -32

u (3)= -22

c’(2)= -38

u (2)= -32

• Among the live nodes 3,4 and 5

which node to expand?

• The least cost node to be expanded i.e.,

Node 4 is expanded. Since , c’(4)<{c’(3), c’(5)}

4

5

x₂=1

x₂=0

c’(4)= -38

u(4)= -32

c’(5)= -36

u(5)= -22

upper = -32

1

c’(1)= -38

u (1)= -32

Consider the knapsack instance with n =4, (p1,p2,p3,p4)=(10,10,12,18) ,

(w1,w2,w3,w4) = (2,4,6,9) and m=15 .

c’(7) =

u(7)=

2

3

x₁=1

x₁=0

c’(3)= -32

u (3)= -22

c’(2)= -38

u(2)= -32

• Among the live nodes 6,7 ,5 and 3

which node to be expand?

• The least cost node to be expanded i.e., either Node 6 or Node 7. Node 3 and 5 are killed

4

5

x₂=1

x₂=0

c’(4)= -38

u(4)= -32

c’(5)= -36

u(5)= -22

6

7

x₃=1

x₃=0

c’(7)= -38

u(7)= -38

c’(4)= -38

u(4)= -32

upper = -32

• Update the upper value to -38. since -38 < -32. So, kill the nodes whose cost is > upper.

-38

1

c’(1)= -38

u (1)= -32

Consider the knapsack instance with n =4, (p1,p2,p3,p4)=(10,10,12,18) ,

(w1,w2,w3,w4) = (2,4,6,9) and m=15 .

c’(9) =

u(9)=

2

3

x₁=1

x₁=0

c’(3)= -32

u (3)= -22

c’(2)= -38

u(2)= -32

• Kill all the live nodes ,whose nodes cost c’(x) >= upper.

4

5

x₂=1

x₂=0

c’(4)= -38

u(4)= -32

c’(5)= -36

u(5)= -22

6

7

x₃=1

x₃=0

c’(7)= -38

u(7)= -38

c’(4)= -38

u(4)= -32

8

9

c’(8)= -38

u(8)= -38

x₄=1

x₄=0

c’(9)= -20

u(9)= -20

upper = -38

1

c’(1)= -38

u (1)= -32

2

3

x₁=1

x₁=0

c’(3)= -32

u (3)= -22

c’(2)= -38

u(2)= -32

• Kill the live nodes ,whose nodes cost c’(x) > upper.

​

• Node 6 and 8 are the live nodes.

​

• Node 8 is answer node.

​

• The path traversed includes the objects

8 --- > 7 ---> 4 ---> 2 ----> 1

​

• (x4,x3,x2,x1)=(1 ,0,1,1)

​

• Profit = 38

​

​

4

5

x₂=1

x₂=0

c’(4)= -38

u(4)= -32

c’(5)= -36

u(5)= -22

6

7

x₃=1

x₃=0

c’(7)= -38

u(7)= -38

c’(4)= -38

u(4)= -32

8

9

c’(8)= -38

u(8)= -38

x₄=1

x₄=0

c’(9)= -20

u(9)= -20

Solution to 0/1 knapsack problem using LCBB

upper = -38

1

c’(1)= -38

u (1)= -32

Consider the knapsack instance with n =4, (p1,p2,p3,p4)=(10,10,12,18) ,

(w1,w2,w3,w4) = (2,4,6,9) and m=15 .

2

3

x₁=1

x₁=0

c’(3)= -32

u(3)= -22

c’(2)= -38

u (2)= -32

4

5

6

7

x₂=1

x₂=0

x₂=0

x₂=1

c’(6) = -32

u(6) = -22

c’(7) = -30

u(7) = -30

c’(5) = -36

u(5) = -22

c’(4) = -38

u(4) = -32

8

9

x₃=1

x₃=0

c’(8) = -38

u(8) = -32

c’(9) = -38

u(9) = -38

10

11

12

13

x₄=1

x₄=0

x₄=0

x₄=1

c’(13) = -20

u(13) = -20

c’(12) = -38

u(12) = -38

upper = -32

-38

c’(11) = -32

u(11) = -32

Infeasible node . So ,it is killed

Solution to 0/1 knapsack problem using FIFO BB

4 5

2 3

6 7

8 9

After node 9 is generated, upper is updated to -38. The nodes 5,6, and 7 are killed because the cost of 5, 6 and 7 are greater than upper.

11

12 13

Node 11 and 13 are killed because c’(11) and c’(13) are > upper

The only live node available is Node 12 , which is the answer node.

List of live nodes

Control abstraction for Least cost search

​

Introduction to Complexity classes

1. P and NP Problems

​

• NP-Complete Problems

Introduction to Complexity classes

P (Polynomial Time):

• The class of problems that can be solved by an algorithm in polynomial time.

​

• Polynomial time means that the time it takes to solve the problem can be expressed as a polynomial function of the input size n, such as O(n^2) or O(n^3).

​

• Essentially, P includes problems that are "feasible" to solve efficiently on a computer as they get larger. Examples include basic operations like sorting numbers, finding the shortest path in a graph, or basic arithmetic.

NP (Nondeterministic Polynomial Time):

• The class of problems for which a proposed solution can be verified in polynomial time.
• This doesn’t necessarily mean we can find a solution in polynomial time; rather, if we’re given a candidate solution, we can check if it’s correct relatively quickly (in polynomial time).
• Examples include the Subset Sum Problem (given a set of numbers, is there a subset that sums to a given target?) and Graph Coloring (can we color a graph with a certain number of colors without adjacent nodes sharing the same color?).
• Key point: Every problem in P is also in NP (since if you can solve it quickly, you can verify it quickly), but the reverse isn’t necessarily true.

Is P = NP?

• If P = NP: It would mean that any problem for which we can verify a solution efficiently can also be solved efficiently. This would revolutionize computing, as currently hard problems (like many in cryptography) would become tractable.

​

• If P ≠ NP: It would confirm that there are some problems that are inherently harder to solve than to verify, meaning there’s no efficient way to solve certain types of complex problems as they scale

NP-Complete Problems

Within NP, there is a subset called NP-Complete problems, which are the "hardest" problems in NP:

• An NP-Complete problem is one that, if we can solve it in polynomial time, would mean we can solve all NP problems in polynomial time.

​

• NP-Complete problems have the property that any other NP problem can be reduced to them. This means we can transform any NP problem into an NP-Complete problem efficiently.

​

• Examples include the Traveling Salesman Problem, the Knapsack Problem, and the Boolean Satisfiability Problem (SAT).

The End