Backtracking
Backtracking is a technique based on algorithm to solve problem. It uses recursive calling to find the solution by building a solution step by step increasing values with time. It removes the solutions that doesn't give rise to the solution of the problem based on the constraints given to solve the problem.
Backtracking algorithm is applied to some specific types of problems,
∙ Decision problem used to find a feasible solution of the problem.
∙ Optimisation problem used to find the best solution that can be applied.
∙ Enumeration problem used to find the set of all feasible solutions of the problem.
In backtracking problem, the algorithm tries to find a sequence path to the solution which has some small checkpoints from where the problem can backtrack if no feasible solution is found for the problem.
Example:
Here,
Green is the start point, blue is the intermediate point, red are points with no feasible solution, dark green is end solution.
Here, when the algorithm propagates to an end to check if it is a solution or not, if it is then returns the solution otherwise backtracks to the point one step behind it to find track to the next point to find solution.
Find the other possible solution for 4-queen problem 1 2 3 4
1
2
3
4
Solution Vector (3,1,4,2)
1 2 3 4
1
2
3
4
Fig shows the complete state space for 4 - queens problem. But we can use backtracking method to generate the necessary node and stop if the next node violates the rule, i.e., if two queens are attacking.
1) Solve 8 queen problem for a feasible sequence<6,4,7,1> Solution:
As a feasible sequence is given, we will place the queen accordingly and then try out the other remaining places.
1 2 3 4 5 6 7 8
1
2
3
4
5
6
7
8
(6,4,7,1,3,5,2,8)
2) Solve 8 queen problem for a feasible sequence<7,5,3,1> 1 2 3 4 5 6 7 8
1
2
3
4
5
6
7
8
Subset-Sum Problem
The Subset-Sum Problem is to find a subset's' of the given set S = (S1 S2 S3...Sn) where the elements of the set S are n positive integers in such a manner that s'∈S and sum of the elements of subset's' is equal to some positive integer 'X.'
The Subset-Sum Problem can be solved by using the backtracking approach. In this implicit tree is a binary tree. The root of the tree is selected in such a way that represents that no decision is yet taken on any input. We assume that the elements of the given set are arranged in increasing order:
S1 ≤ S2 ≤ S3... ≤ Sn
The left child of the root node indicated that we have to include 'S1' from the set 'S' and the right child of the root indicates that we have to execute 'S1'. Each node stores the total of the partial solution elements. If at any stage the sum equals to 'X' then the search is successful and terminates.
The dead end in the tree appears only when either of the two inequalities exists:
o The sum of s' is too large i.e.
s'+ Si + 1 > X
o The sum of s' is too small i.e.
Example: Given a set S = (3, 4, 5, 6) and X =9. Obtain the subset sum using Backtracking approach.
Solution:
1. Initially S = (3, 4, 5, 6) and X =9.
2. S'= (∅)
3. The implicit binary tree for the subset sum problem is shown as fig:
The number inside a node is the sum of the partial solution elements at a particular level.
Thus, if our partial solution elements sum is equal to the positive integer 'X' then at that time search will terminate, or it continues if all the possible solution needs to be obtained.
Problem statement:
Let, S = {S1 …. Sn} be a set of n positive integers, then we have to find a subset whose sum is equal to given positive integer d.It is always convenient to sort the set’s elements in ascending order. That is, S1 ≤ S2 ≤…. ≤ Sn
Algorithm:
Let, S is a set of elements and m is the expected sum of subsets. Then:
1. Start with an empty set.
2. Add to the subset, the next element from the list.
3. If the subset is having sum m then stop with that subset as solution.
4. If the subset is not feasible or if we have reached the end of the set then backtrack through the subset until we find the most suitable value.
5. If the subset is feasible then repeat step 2.
6. If we have visited all the elements without finding a suitable subset and if no backtracking is possible then stop without solution.
Example: Solve following problem and draw portion of state space tree M=30,W ={5, 10, 12, 13, 15, 18} Solution:
The state space tree is shown as below in figure. {5, 10, 12, 13, 15, 18}
Example:
Apply backtracking algorithm solve the instance of the sum of subset problem S = {1, 3, 4, 5} and d=11
Solution:
Consider sets S = {1, 3, 4, 5}
We do not obtained sum = d = 11, Hence no such sum of subset can be choosen.
The state space tree can be:
0
With 1 W / O 1
10
With 3W / O 3 41
W / O 4
W 3 W/o 3 3 0
With 4 W / O 4 8 4
W 4
51
W 4W/o 4 73
With 5
W / O 5
W 5
4 9
W 5
10
W 5W /o 512 7
13 8 >11
Draw the solution space tree for fixed size and available tuple for the following array and positive integer A = { 12,16,9,25,10} sum = 35 find the solution nodes.
Solution :
Consider A = { 12,16,9,25,10} and sum = 35
Arrange the element in non decreasing order i.e. {9,10,12,16,25}
State Space Tree
0
With 9 W/o 9
90
With 10.W / O 10 19 9
W / O 4
W 3 W/o 3 3 0
W 12 W / O 12 31 19
W 4
51
W 4W/o 4 73
W 16
W / O 16
47 31
W 16
4 35
W 5
10
W 5W /o 5 12 7
>11
Hamiltonian Cycle/Circuit Problems
Given a graph G = (V, E) we have to find the Hamiltonian Circuit using Backtracking approach. We
start our search from any arbitrary vertex say 'a.' This vertex 'a' becomes the root of our implicit tree. The first element of our partial solution is the first intermediate vertex of the Hamiltonian Cycle that is to be constructed. The next adjacent vertex is selected by alphabetical order. If at any stage any arbitrary vertex makes a cycle with any vertex other than vertex 'a' then we say that dead end is reached. In this case, we backtrack one step, and again the search begins by selecting another vertex and backtrack the element from the partial; solution must be removed. The search using backtracking is successful if a Hamiltonian Cycle is obtained.
Example: Consider a graph G = (V, E) shown in fig. we have to find a Hamiltonian circuit using Backtracking method.
Solution: Firstly, we start our search with vertex 'a.' this vertex 'a' becomes the root of our implicit tree.
Next, we choose vertex 'b'
Next, we select 'e' adjacent to 'd.'
Next, we select vertex 'f' adjacent to 'e.' The vertex adjacent to 'f' is d and e, but they have already visited. Thus, we get the dead end, and we backtrack one step and remove the vertex 'f' from partial solution.
From backtracking, the vertex adjacent to 'e' is b, c, d, and f from which vertex 'f' has already been checked, and b, c, d have already visited. So, again we backtrack one step. Now, the vertex adjacent to d are e, f from which e has already been checked, and adjacent of 'f' are d and e. If 'e' vertex, revisited them we get a dead state. So again we backtrack one step.
Now, adjacent to c is 'e' and adjacent to 'e' is 'f' and adjacent to 'f' is 'd' and adjacent to 'd' is 'a.' Here, we get the Hamiltonian Cycle as all the vertex other than the start vertex 'a' is visited only once. (a - b - c - e - f -d - a).
Again Backtrack
a
cd
b d e
b d f
d
f
Dead end
e
f
d
a
e # e
f
b f Dead end
e
b
fd Dead end
Backtrack to a
a
d
c ef
d
b e
b c f
c e
e f
b
c b
b e e b
1) a—c—b—e—f—d—a
2) a—b—c—e—f—d—a
3)
Example 2:
Implemented Hamiltonian path on the following graph
1
2
4 3
The state space tree:
1
24 1 2
3 3 42 11
4 3
So Hamiltonian cycle is 1---2---3---4---1 & 1---4---3---2---1 Example 3:
Explain how to find Hamiltonian cycle by using backtracking in given graph.
1 2
3 4
6 78
5
The State Space Tree is: 1
2 3 6
3 5
6
4 7
7
8 7
6 8 54
3 8
6
5
Dead End
4
8
1---2---5---6---7—8---4---3--1
4
3
1
Solution
State Space Tree:
Black
Red
A Black
Green B E
C D E
Red
D
0
AAA
BlackGreen Red
Example 2:
Implement a graph colouring on the following graph and generate the solution space tree if number of permitted colour = 3
1 4
2 3
State Space Tree :
0
1 1 1 R G B
2 2
2 2 G B
R 2 B 2
G R B G
3 3 R 3 3 B R G
3 3 G B
3 3
G R
3 3 B R
4
3 3
4 4 4 G B G
4 4 4 G
G B
4 4
4 4 R B
4
4
B
G
4 4 4 G R R
R
R B
Example 4:
1
2
4 4 R G
4 3
Graph Colouring Problem
Graph colouring problem is a classical combination problem.A graph G with n nodes and a positive integer m are given.Using m colours only, to colour all the nodes of graph G in such a way that no two adjacent node have the same colour. This problem is called the m colouring decision problem. The integer m is called the chromatic number of the graph.
Graph Coloring Problem
- Assign colors to the vertices of a graph so that no adjacent vertices share the same color - Vertices i , j are adjacent if there is an edge from vertex i to vertex j. • Find all m-colorings of a graph - Find all ways to color a graph with at most m colors. -m is called chromatic number Graph coloring The m-Coloring problem Finding all ways to color an undirected graph using at most m different colors, so that no two adjacent vertices are the same color.
- Usually the m-Coloring problem consider as a unique problem for each value of m.
Graph Coloring Planar graph
It can be drawn in a plane in such a way that no two edges cross each other.
Graph Coloring
corresponded planar graph
Graph Coloring
- The top level call to m_coloring
- m_coloring(0)
- The number of nodes in the state space tree for this algorithm Nextvalue(k) X[1]x[k-1] have been assigned integer value in the range [1,m) such that adjacent vertices have distinct integer. A value for x[k] is determined in the range (0,m). X[k] is assigned the next highest numbered color while maintaining distinctness from the adj. vertices of vertex k. If no such color exists, then x[k] is 0 1. Algorithm Nextvalue(k) 2. { repeat 3. {X[k]:= (x[k]+1) mod (m+1); //next higher color
7. if ((G[k,j]!= 0) and (x[k] = x[j]))
Graph coloring
Graph Coloring
Graph-Colour Problem 7. For j ⬅️ 1 to n Do //checking distinctness of colours
If g[k][j]!=0 and T[k]=T[j] Then
x ⬅️1 exit
8. If j=n+1 Then //consider new colour x ⬅️ 0 return x 9. If T[k]=0 Then Dead ⬅️0
Return dead 10. If k=n Then For r ⬅️ 1 to n Do
Write T[k]
11. Else Graph-Colour-Prob-Back(k+1)
12. return Analysis:
- Total time required by the algorithm for n vertices is T(n)=O(nm^n).
- If man then T(n)=O(n^n)
Graph-Colour Problem
Example 1. Colour the following graph with minimum no of distinct colours using backtracking approach.
Graph-Colour Problem
- Consider the vertex A as the starting node of the implicit tree and colour the nodes in the following way
- Let C= Set of different colours used and S= Set of vertices having same colour .Both are initially empty
- STEP 1:Colour vertex A with a colour say,Black.
Graph-Colour Problem
Explore B. Step 3. Consider vertex C.Colour C taking from the colour set C if possible .Black is taken since it is not afjacent to A. C={black,green},No new colour is considered. No change in S=(A,B,C).Explore C.
The Knight’s tour problem | Backtracking
Backtracking is an algorithmic paradigm that tries different solutions until finds a solution that “works”. Problems which are typically solved using backtracking technique have the following property in common. These problems can only be solved by trying every possible configuration and each configuration is tried only once. A Naive solution for these problems is to try all configurations and output a configuration that follows given problem constraints. Backtracking works in an incremental way and is an optimization over the Naive solution where all possible configurations are generated and tried.
For example, consider the following Knight’s Tour problem. Problem Statement:
Given a N*N board with the Knight placed on the first block of an empty board. Moving according to the rules of chess knight must visit each square exactly once. Print the order of each the cell in which they are visited.
Knight's tour is a problem in which we are provided with a NxN chessboard and a knight.
For a person who is not familiar with chess, the knight moves two squares horizontally and one square vertically, or two squares vertically and one square horizontally as shown in the picture given below.
Thus if a knight is at (3, 3), it can move to the (1, 2) ,(1, 4), (2, 1), (4, 1), (5, 2), (5, 4), (2, 5) and (4, 5) cells.
Thus, one complete movement of a knight looks like the letter "L", which is 2 cells long.
According to the problem, we have to make the knight cover all the cells of the board and it can move to a cell only once.
There can be two ways of finishing the knight move - the first in which the knight is one knight's move away from the cell from where it began, so it can go to the position from where it started and form a loop, this is called closed tour; the second in which the knight finishes anywhere else, this is called open tour.
Approach to Knight's Tour Problem
Similar to the N-Queens problem, we start by moving the knight and if the knight reaches to a cell from where there is no further cell available to move and we have not reached to the solution yet (not all cells are covered), then we backtrack and change our decision and choose a different path.
So from a cell, we choose a move of the knight from all the moves available, and then recursively check if this will lead us to the solution or not. If not, then we choose a different path.
We keep the track of the moves in a matrix. This matrix stores the step number in which we visited a cell. For example, if we visit a cell in the second step, it will have a value of 2.
This matrix also helps us to know whether we have covered all the cells or not. If the last visited cell has a value of N*N, it means we have covered all the cells.
Thus, our approach includes starting from a cell and then choosing a move from all the available moves. Then we check if this move will lead us to the solution or not. If not, we choose a different move. Also, we store all the steps in which we are moving in a matrix.
Objective : A knight’s tour is a sequence of moves of a knight on a chessboard such that the knight visits every square only once. If the knight ends on a square that is one knight’s move from the beginning square (so that it could tour the board again immediately, following the same path), the tour is closed, otherwise it is open.
Approach:
∙ Create a solution matrix of the same structure as chessboard.
∙ Start from 0,0 and index = 0. (index will represent the no of cells has
∙ been covered by the knight)
∙ Check current cell is not already used if not then mark that cell (start with 0 and keep incrementing it, it will show us the path for the knight).
∙ Check if index = N*N-1, means Knight has covered all the cells. return true and print the solution matrix.
∙ Now try to solve rest of the problem recursively by making index +1. Check all 8 directions. (Knight can move to 8 cells from its current position.) Check the boundary conditions as well
∙ If none of the 8 recursive calls return true, BACKTRACK and undo the changes ( put 0 to corresponding cell in solution matrix) and return false.
Approximate Algorithms
Introduction:
An Approximate Algorithm is a way of approach NP COMPLETENESS for the optimization problem. This technique does not guarantee the best solution. The
goal of an approximation algorithm is to come as close as possible to the optimum value in a reasonable amount of time which is at the most polynomial time. Such algorithms are called approximation algorithm or heuristic algorithm.
o For the traveling salesperson problem, the optimization problem is to find the shortest cycle, and the approximation problem is to find a short cycle.
o For the vertex cover problem, the optimization problem is to find the vertex cover with fewest vertices, and the approximation problem is to find the vertex cover with few vertices.
Performance Ratios
Suppose we work on an optimization problem where every solution carries a cost. An Approximate Algorithm returns a legal solution, but the cost of that legal solution may not be optimal.
For Example, suppose we are considering for a minimum size vertex-cover (VC). An approximate algorithm returns a VC for us, but the size (cost) may not be minimized.
Another Example is we are considering for a maximum size Independent set (IS). An approximate Algorithm returns an IS for us, but the size (cost) may not be maximum. Let C be the cost of the solution returned by an approximate algorithm, and C* is the cost of the optimal solution.
We say the approximate algorithm has an approximate ratio P (n) for an input size n, where
Intuitively, the approximation ratio measures how bad the approximate solution is distinguished with the optimal solution. A large (small) approximation ratio measures the solution is much worse than (more or less the same as) an optimal solution.
Observe that P (n) is always ≥ 1, if the ratio does not depend on n, we may write P. Therefore, a 1-approximation algorithm gives an optimal solution. Some problems have polynomial-time approximation algorithm with small constant approximate ratios, while others have best-known polynomial time approximation algorithms whose approximate ratios grow with n.
Vertex Cover
A Vertex Cover of a graph G is a set of vertices such that each edge in G is incident to at least one of these vertices.
The decision vertex-cover problem was proven NPC. Now, we want to solve the optimal version of the vertex cover problem, i.e., we want to find a minimum size vertex cover of a given graph. We call such vertex cover an optimal vertex cover C*.
An approximate algorithm for vertex cover:
1. Approx-Vertex-Cover (G = (V, E))
2. {
3. C = empty-set;
4. E'= E;
5. While E' is not empty do
6. {
7. Let (u, v) be any edge in E': (*)
8. Add u and v to C;
9. Remove from E' all edges incident to
10. u or v;
11. }
12. Return C;
13. }
The idea is to take an edge (u, v) one by one, put both vertices to C, and remove all the edges incident to u or v. We carry on until all edges have been removed. C is a VC. But how good is C?
VC = {b, c, d, e, f, g}
Traveling-salesman Problem
In the traveling salesman Problem, a salesman must visits n cities. We can say that salesman wishes to make a tour or Hamiltonian cycle, visiting each city exactly once and finishing at the city he starts from. There is a non-negative cost c (i, j) to travel from the city i to city j. The goal is to find a tour of minimum cost. We assume that every two cities are connected. Such problems are called Traveling-salesman problem (TSP).
We can model the cities as a complete graph of n vertices, where each vertex represents a city.
It can be shown that TSP is NPC.
If we assume the cost function c satisfies the triangle inequality, then we can use the following approximate algorithm.
Triangle inequality
Let u, v, w be any three vertices, we have
One important observation to develop an approximate solution is if we remove an edge from H*, the tour becomes a spanning tree.
1. Approx-TSP (G= (V, E))
2. {
3. 1. Compute a MST T of G;
4. 2. Select any vertex r is the root of the tree;
5. 3. Let L be the list of vertices visited in a preorder tree walk o f T;
6. 4. Return the Hamiltonian cycle H that visits the vertices in th e order L;
7. }
Traveling-salesman Problem
Intuitively, Approx-TSP first makes a full walk of MST T, which visits each edge exactly two times. To create a Hamiltonian cycle from the full walk, it bypasses some vertices (which corresponds to making a shortcut)
Biconnected graph
Before Biconnected Components, let's first try to understand what a Biconnected Graph is and how to check if a given graph is Biconnected or not.
A graph is said to be Biconnected if:
1. It is connected, i.e. it is possible to reach every vertex from every other vertex, by a simple path.
2. Even after removing any vertex the graph remains connected. For example, consider the graph in the following figure
The given graph is clearly connected. Now try removing the vertices one by one and observe. Removing any of the vertices does not increase the number of connected components. So the given graph is Biconnected. Now consider the following graph which is a slight modification in the previous graph.
In the above graph if the vertex 2 is removed, then here's how it will look:
Clearly the number of connected components have increased. Similarly, if vertex 3 is removed there will be no path left to reach vertex 0 from any of the vertices 1, 2, 4 or 5. And same goes for vertex 4 and 1. Removing vertex 4 will disconnect 1 from all other vertices 0, 2, 3 and 4. So the graph is not Biconnected.
Now what to look for in a graph to check if it's Biconnected. By now it is said that a graph is Biconnected if it has no vertex such that its removal increases the number of connected components in the graph. And if there exists such a vertex then it is not Biconnected. A vertex whose removal increases the number of connected components is called an Articulation Point.
An undirected graph is called Biconnected if there are two vertex-disjoint paths between any two vertices. In a Biconnected Graph, there is a simple cycle through any two vertices.
By convention, two nodes connected by an edge form a
biconnected graph, but this does not verify the above properties. For a graph with more than two vertices, the above properties must be there for it to be Biconnected.
Or in other words:
A graph is said to be Biconnected if:
1) It is connected, i.e. it is possible to reach every vertex from every other vertex, by a simple path.
2) Even after removing any vertex the graph remains connected. Following are some examples.
Articulation Points (or Cut Vertices) in a Graph
A vertex in an undirected connected graph is an articulation point (or cut vertex) iff removing it (and edges through it) disconnects the graph. Articulation points represent vulnerabilities in a connected network – single points whose failure would split the network into 2 or more components. They are useful for designing reliable networks.
For a disconnected undirected graph, an articulation point is a vertex removing which increases number of connected components.
Following are some example graphs with articulation points encircled with red color.
How to find all articulation points in a given graph?
A simple approach is to one by one remove all vertices and see if removal of a vertex causes disconnected graph. Following are steps of simple approach for connected graph. 1) For every vertex v, do following
…..a) Remove v from graph
..…b) See if the graph remains connected (We can either use BFS or DFS)
…..c) Add v back to the graph
Biconnected Components,
A biconnected component is a maximal biconnected subgraph.
In above graph, following are the biconnected components:
∙ 4–2 3–4 3–1 2–3 1–2
∙ 8–9
∙ 8–5 7–8 5–7
∙ 6–0 5–6 1–5 0–1
∙ 10–11
Comments
Post a Comment