Unit-IV

By

SARVANI ANANDARAO

​

​

Backtracking

Backtracking

• It is used to solve problems in which a sequence of objects is chosen from a specified set so that the sequence satisfy some criterion.

​

• When?? - When we have different choices, where sufficient information is not available on the best choice

​

• How?? – A Backtracking is a systematic method of trying out various sequence of decisions until you find out that works

​

Start(live node)

dead end

dead end

dead node

dead node

success node

E-node(as it leads to success node

Live Node

Cont…

• Live Node: Which can be further generate

​

​

• Enode: The Child node that leads to successor(success node)

​

​

• Deadnode: Which cannot be extended further

2 types of constraints are

1. Implicit : Rules that satisfy, specify each element in a tuple should be related

​

​

• Explicit: Rules that restrict, each element to be chosen from a given set

Applications

1. N queen problem
2. Sum of subsets
3. Graph Colouring
4. Hamiltonian cycle

N Queen Problems

• Consider NxN cheese board. ‘N’ queens must be places such that ‘No’ two queens can attack. Should not be placed on same row,same column and same diagonal
• N = 2

​

​

• N = 3

Q2 cannot be placed

Q3 cannot be placed

• N= 4

​

As q3 cannot be placed in 3^rd row. Backtrack to q2 and move the position of q2

As q4 cannot be placed in 4^th row. Backtrack to q3 and move the position of q3

Q3 cannot be placed in another position, so backtrack to ‘q2’. Even ‘q2’ cannot be placed in another position so, backtrack to ‘q1’. After moving the position Q1, correspondingly Q2,Q3 must be moved.

Solution Set

​

​

The above are Column numbers

• State Space Tree

3

2

4

1

3

2

4

1

4

3

1

2

4

3

2

1

4

3

2

4

2

3

1

3

2

4

1

4

2

1

2

3

1

3

1

2

3

4

1

4

4

3

3

1

4

2

4

1

1

2

3

2

3

1

2

1

4

2

3

2

4

3

4

1

q1

q2

q3

q4

8 Queen problem in Backtracking

Sum of Subsets

• Among set of ‘n’ integers, we select subset of integers whose sum is ‘m’
• {1,2,3,4,5,6,7} ; m=10

​

• Solution1 = {1,2,3,4} = 10
• Solution2 = {4,6}=10
• Solution3 = {3,7} = 10

X_k=1

X_k=0

• Example: {7,11,13,24}, m=31

​

X1=1

X1=0

X2=1

X2=0

X2=1

X2=0

X3=1

X3=0

X3=1

X3=0

X3=1

X3=0

X3=1

X3=0

X4=1

Solution 1

Solution 2

Cont….

Graph Colouring Problem

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

​

​

a

d

c

e

b

• The Problem has two versions:
• m – Colourability Decision Problem
• m- Colourability Optimization Problem

​

Chromatic Number: The Minimum number of colours required to colour all the vertices of the given graph is called chromatic number.

​

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

​

d=2,d+1 = 3 colours

Example

• degree = 2,
• degree+1 = 2+1 = 3
• So we need minimum ‘3’

Colours to colour the adjacent graph

A

D

C

B

CONT…

• State Space Tree : For a 4 node graph with 3 colours, there are 18 solutions[Number of leaf nodes]

​

• (x1,x2,x3,x4) = (1/2/3,1/2/3,1/2/3,1/2/3)

​

• Time Complexity = ⃝(n.mⁿ)

Assignment

1

2

3

4

5

1

4

5

2

3

• Cons 1: All the vertices must be visited
• Cons2: Every verticex must be visited only once except the starting verticex

​

​

Hamiltonian Cycle Problem in Backtracking

​

​

• Let G=(V,E) is a connected graph with ‘V’ vertices. A Hamiltonian cycle is a round trip path along ‘E’ edges of ‘G’ that visits each and every vertex exactly once except the starting and ending vertex and returns to the starting vertex

​

Example

​

​

​

​

​

• 1-2-8-7-6-5-4-3-1[except starting vertex, we have visited all other vertices exactly once].
• 4-3-1-2-8-7-6-5-4
• 3-4-5-6-7-8-2-1-3

​

​

​

1

2

3

8

7

6

5

4

​

​

​

​

​

​

​

• This is not Hamiltonian Cycle because it contains junction
• 1-5-2-4-3-2-1 ------🡪 ‘2’ is visited two times

​

1

4

5

2

3

Junction –Orticulation Point

​

​

​

​

​

​

​

• Not Hamiltonian cycle.
• 1-2-4-3-6-5-3-1.-----’3’ is visited two times

1

4

2

3

6

5

Junction Point

​

​

​

​

​

​

​

​

​

​

• Not Hamiltonian Cycle: 1-2-4-5-4-3-1
• ‘4’ is visited two times. Here ‘5’ and ‘6’ are pendant vertex. If the graph consists of pendant vertex then it is not Hamiltonian cycle.

1

4

2

3

5

6

Pendant Vertex

Pendant Vertex

​

​

​

​

​

​

​

​

• 1-2-3-7-6-4-1
• But No visiting of 5 vertex
• So this is not Hamiltonian Cycle. According to definition all the vertices must be visited.

1

6

4

7

2

3

5

​

​

​

​

​

​

​

​

​

​

• A-B-F-E-D-C-A.--- In this path all the vertices are visited and no vertex is repeated. Finally reached the source vertex “A”
• A-D-E-F-B-C-A--- In this path all the vertices are visited and no vertex is repeated. Finally reached the source vertex “A”

​

• B-F-E-D-A-C-B--- In this path all the vertices are visited and no vertex is repeated. Finally reached the source vertex “A”

​

​

• This is Hamiltonian cycle.

​

D

A

C

E

F

B

• In the paths
• [A-B-C-E-D]. F is not present , not visited. So not Hamiltonian cycle
• [A-B-C-E-F]: D is not visited. So not Hamiltonian cycle
• [A-B-C-D-E-F]: not a Hamiltonian cycle because after reaching F. There is no direct edge from F to A. To go to ‘A’ we need to again visit ‘B’ vertex. Then vertex ‘B’ will be visited two times.
• [A-B-E-C-D]: ‘F’ not visited. This is not Hamiltonian cycle
• [A-B-E-F]: ‘C’,’D’, is not visited. This is not Hamiltonian cycle
• [A-B-F-E-C-D]: This is Hamiltonian cycle because from ‘D’ we can visit to A
• [A-C-B-E-D]: ‘F’ is not there. This is not Hamiltonian cycle
• [A-C-B-E-F] : D is not visited. This is not Hamiltonian cycle
• [A-C-B-F-E-D]: This is Hamiltonian cycle.

​

Cont…

Hamiltonian cycle are:

1. A-B-F-E-C-D-A
2. A-B-F-E-D-C-A
3. A-C-B-F-E-D-A
4. A-C-D-E-F-B-A
5. A-D-E-F-B-C-A

​

END OF UNIT-IV