E Lesson 8

IDOL Institute of Distance and Online Learning ENHANCE YOUR QUALIFICATION, ADVANCE YOUR CAREER.

MCA 2 All right are reserved with CU-IDOL DESIGN AND ANALYSIS OF ALGORITHMS Course Code: MCA 632 Semester: Third e-Lesson: 8 SLM Unit: 10,11 www.cuidol.in Unit-10-11(MCA 632)

Design and Analysis of Algorithms 33 OBJECTIVES INTRODUCTION  Student will be able to learn about Backtracking.  In this unit we are going to learn about Student will be able to learn about Branch and algorithm analysis Backtracking.  Bound. Under this you will learn and understand the concept of Branch and Bound. Student will be able to learn about N Queen   problem, Graph coloring problem. Assignment Problem and Travelling Student will be able to learn about travelling salesperson problem. salesperson problem.  N Queen problem, graph coloring problem.  www.cuidol.in Unit-10-11(1M-MCACA63623)2) INSTITUTE OF DAIlSlTAriNgChEt aArNeDreOsNeLrvINeEd LwEiAthRNCIUN-GIDOL

TOPICS TO BE COVERED 4 Backtracking 1: General method: N-Queens problem Sum of subset problem Graph coloring Hamilton cycles. Backtracking 2: Branch and Bound: Assignment Problem Travelling Sales Person problem www.cuidol.in Unit-10-11(MCA 632) All right are reserved with CU-IDOL

Backtracking 5  One strategy would be to try going through Portion A of the maze.  If you get stuck before you find your way out, then you \"backtrack\" to the junction  At this point in time you know that Portion A will NOT lead you out of the maze, so you then start searching in Portion B Clearly, at a single junction you could have even more than 2 choices. The backtracking strategy says to try each choice, one after the other, if you ever get stuck, \"backtrack\" to the junction and try the next choice. If you try all choices and never found a way out, then there is no solution to the maze. www.cuidol.in Unit-10-11(MCA 632) All right are reserved with CU-IDOL

Eight Queen Problem 6 • Find an arrangement of 8 queens on a single chess board such that no two queens are attacking one another. • In chess, queens can move all the way down any row, column or diagonal (so long as no pieces are in the way). • Due to the first two restrictions, it's clear that each row and column of the board will have exactly one queen. Fig: Queen Problem www.cuidol.in Unit-10-11(MCA 632) All right are reserved with CU-IDOL

Eight Queen Problem(Cont..) 7 The backtracking strategy is as follows: 1) Place a queen on the first available square in row 1. 2) Move onto the next row, placing a queen on the first available square there (that doesn't conflict with the previously placed queens). 3) Continue in this fashion until either: a) you have solved the problem, or b) you get stuck. When you get stuck, remove the queens that got you there, until you get to a row where there is another valid square to try. www.cuidol.in Unit-10-11(MCA 632) All right are reserved with CU-IDOL

Sum of Subset 8 • given n positive integers (weights) w1, w2, ...,wn • given a positive integer W • finding all subsets of n integers that sum to W • e.g., wi+wj+...+wk=W • create a state space tree • each left edge denotes we include wi (weight wi) • each right edge denotes we exclude wi (weight 0) • any path from root to a leaf forms a subset www.cuidol.in Unit-10-11(MCA 632) All right are reserved with CU-IDOL

Sum of Subset (Cont..) 9 www.cuidol.in Unit-10-11(MCA 632) All right are reserved with CU-IDOL

Sum of Subset (Cont..) 10 significant signs (backtracking) • sorting the weights in non-decreasing order • weight be the subtotal from root to node i at level I • weight +wi+1 > W • any descendant of node i will be non-promising ( because is wi+1 the lightest weight remaining) • weight + all remaining items < W • any descendant of node i will be non-promising www.cuidol.in Unit-10-11(MCA 632) All right are reserved with CU-IDOL

Graph Coloring 11 Let G be undirected graph and let c be an integer. Assignment of colors to the vertices or edges such that no two adjacent vertices are to be similarly colored. We want to minimize the number of colors used. The smallest c such that a c-coloring exists is called the graph‟s chromatic number and any such c-coloring is an optimal coloring. 1.The graph coloring optimization problem: find the minimum number of colors needed to color a graph. 2.The graph coloring decision problem: determine if there exists a coloring for a given graph which uses at most m colors. www.cuidol.in Unit-10-11(MCA 632) All right are reserved with CU-IDOL

Two colors Graph Coloring (Cont…) 12 Practical applications: scheduling, time-tabling, register allocation for compilers, coloring of maps. A simple graph coloring algorithm - choose a color and an arbitrary starting vertex and color all the vertices that can be colored with that color. Choose next starting vertex and next color and repeat the coloring until all the vertices are colored. Four colors Unit-10-11(MCA 632) All right are reserved with CU-IDOL Fig. 3.13: Graph Coloring www.cuidol.in

Graph Coloring Algorithm 13 Given an undirected graph and a number m, determine if the graph can be colored with at most m colors such that no two adjacent vertices of the graph are colored with same color. Here coloring of a graph means assignment of colors to all vertices. A 2D array graph [V][V] where V is the number of vertices in graph and graph [V][V] is adjacency matrix representation of the graph. A value graph [i][j] is 1 if there is a direct edge from i to j, otherwise graph [i][j] is 0. An integer m which is maximum number of colors that can be used. Output: An array color [V] that should have numbers from 1 to m. color[i] should represent the color assigned to the ith vertex. The code should also return false if the graph cannot be colored with m colors. www.cuidol.in Unit-10-11(MCA 632) All right are reserved with CU-IDOL

Contd… 14 Algorithm: If all colors are assigned, print vertex assigned colors Else a. Trying all possible colors, assign a color to the vertex b. If color assignment is possible, recursively assign colors to next vertices c. If color assignment is not possible, de-assign color, return False www.cuidol.in Unit-10-11(MCA 632) All right are reserved with CU-IDOL

Contd… 15 All right are reserved with CU-IDOL Code: def is_safe (n, graph, colors, c): # Iterate trough adjacent vertices # and check if the vertex color is different from c for i in xrange (n): if graph[n][i] and c == colors[i]: return False return True # n = vertex nb def graphColoringUtil (graph, color_nb, colors, n): # Check if all vertices are assigned a color if color_nb+1 == n : return True www.cuidol.in Unit-10-11(MCA 632)

Hamiltonian Cycles 16 Hamiltonian cycle (HC): is a cycle which passes once and exactly once through every vertex of G (G can be digraph). Hamiltonian path: is a path which passes once and exactly once through every vertex of G (G can be digraph). A graph is Hamiltonian if a Hamiltonian cycle (HC) exists. www.cuidol.in Unit-10-11(MCA 632) Fig. 3.14: Cycle All right are reserved with CU-IDOL

Hamiltonian Algorithm 17 • Recurse(Path p, endpoint e) • While (e has unvisited neighbors) { GetNewNode x; (add x node to P) PruneGraph. (Prune graph. If result graph does not permit a HC forming, remove x from P and continue) FormCycle (If P includes all nodes then try to form cycle. Fail, remove x and continue; Succ, return success) BackTrack: Recurse(P,x) } Return fail. www.cuidol.in Unit-10-11(MCA 632) All right are reserved with CU-IDOL

Hamiltonian Cycle 18 • Search all the potential solutions • Employ pruning of some kind to restrict the amount of researching • Advantage: Find all solution, can decide HC exists or not • Disadvantage Worst case, needs exponential time. Normally, take a long time www.cuidol.in Unit-10-11(MCA 632) 1A8ll right are reserved with CU-IDOL

Branch and Bound 19 The branch-and-bound problem solving method is very similar to backtracking in that a state space tree is used to solve a problem. The differences are that B&B (1) does not limit us to any particular way of traversing the tree and (2) is used only for optimization problems. A B&B algorithm computes a number (bound) at a node to determine whether the node is promising. The number is a bound on the value of the solution that could be obtained by expanding the state space tree beyond the current node. Fig. 3.15: Branch & Bound www.cuidol.in Unit-10-11(MCA 632) 1A9ll right are reserved with CU-IDOL

B & B Algorithm • Algorithm Branch-and-Bound(x): 20 Input: A problem instance x for a hard optimization problem 2A0ll right are reserved with CU-IDOL Output: A solution for x or “no solution” if none exists F •{(x, Ø)}. b •{(+∞, Ø)}. while F ≠ Ø do select from F the most “promising” configuration (x, y) expand (x, y), yielding new configurations (x1, y1), …, (xk, yk) for each new configuration (xi, yi) do perform a simple consistency check on (xi, yi) www.cuidol.in Unit-10-11(MCA 632)

Contd… if the check returns “solution found” then 21 All right are reserved with CU-IDOL if the cost c of the solution for (xi, yi) beats b then b •(c, (xi, yi)) else discard the configuration (xi, yi) if the check returns “dead end” then discard the configuration (xi, yi) else if lb(xi, yi) is less than the cost of b then F •F U {(xi, yi)}. www.cuidol.in Unit-10-11(MCA 632)

Contd… 22 else discard the configuration (xi, yi) return b ww1w3.c-0ui3d-o2l.i0n20 Unit-10-11(MCA 632) 2A2ll right are reserved with CU-IDOL

B&B :Types of Traversal 23 When implementing the branch-and-bound approach there is no restriction on the type of state-space tree traversal used. Backtracking, for example, is a simple type of B&B that uses depth-first search. A better approach is to check all the nodes reachable from the currently active node (breadth-first) and then to choose the most promising node (best-first) to expand next. An essential element of B&B is a greedy way to estimate the value of choosing one node over another. This is called the bound or bounding heuristic. It is an underestimate for a minimal search and an overestimate for a maximal search. When performing a breadth-first traversal, the bound is used only to prune the unpromising nodes from the state-space tree. In a best-first traversal the bound cab also used to order the promising nodes on the live- node list. www.cuidol.in Unit-10-11(MCA 632) All right are reserved with CU-IDOL

Travelling Salesperson B&B 24 In the most general case the distances between each pair of cities is a positive value with dist(A,B) /= dist(B,A). In the matrix representation, the main diagonal values are omitted (i.e. dist(A,A) = 0). www.cuidol.in Fig. 3.16: Travelling Salesperson All right are reserved with CU-IDOL Unit-10-11(MCA 632)

Travelling Salesperson B&B 25 Obtaining an Initial Tour Use the greedy method to find an initial candidate tour. We start with city A (arbitrary) and choose the closest city (in this case E). Moving to the newly chosen city, we always choose the closest city that has not yet been chosen until we return to A. Our candidate tour is A-E-C-G-F-D-B-H-A with a tour length of 28. We know that a minimal tour will be no greater than this. It is important to understand that the initial candidate tour is not necessarily a minimal tour nor is it unique. If we start with city E for example, we have, E-A-B-H-C-G-F-D-E with a length of 30 www.cuidol.in Unit-10-11(MCA 632) All right are reserved with CU-IDOL

Travelling Salesperson B&B Now we must define a bounding heuristic that provides an 26 underestimate of the cost to complete a tour from any node using local information. In this example we choose to use the actual cost to reach a node plus the minimum cost from every remaining node as our bounding heuristic. h(x) = a(x) + g(x) a(x) - actual cost to node x g(x) - minimum cost to complete Since we know the minimum cost from each node to anywhere we know that the minimal tour cannot be less than 25. www.cuidol.in Unit-10-11(MCA 632) All right are reserved with CU-IDOL

Travelling Salesperson B&B 27 Finding the Minimal Tour 1. Starting with node A determine the actual cost to each of the other nodes. 2. Now compute the minimum cost from every other node 25-4=21. 3. Add the actual cost to a node a(x) to the minimum cost from every other node to determine a lower bound for tours from A through B,C,. . ., H. www.cuidol.in Fig. 3.17: Travelling Salesperson B & B All right are reserved with CU-IDOL Unit-10-11(MCA 632)

Travelling Salesperson 28 B&B 4. Since we already have a candidate tour of 28 we can prune all branches with a lower-bound that is ? 28. This leaves B, D and E as the only promising nodes. 5. We continue to expand the promising nodes in a best-first order (E1,B1,,D1). 5. We continue to expand the promising nodes in a best-first order (E1,B1,,D1). www.cuidol.in Fig. 3.18: Travelling Salesperson B & B All right are reserved with CU-IDOL Unit-10-11(MCA 632)

Travelling Salesperson B&B 6. We have fully expanded node E so it is removed from our live-node list and we have two new nodes 29 to add to the list. When two nodes have the same bounding values we will choose the one that is closer to the solution. So the order of nodes in our live-node list is (C2,B1,B2,D1). www.cuidol.in Fig. 3.19: Travelling Salesperson B & B All right are reserved with CU-IDOL Unit-10-11(MCA 632)

Travelling Salesperson B&B 30 7. We remove node C2 and add node G3 to the live-node list. (G3,B1,B2,D1). www.cuidol.in Unit-10-11(MCA 632) All right are reserved with CU-IDOL

Travelling Salesperson B&B 31 8. Expanding node G gives us two more promising nodes F4 and H4. Our live-node list is now (F4,B1,H4,B2,D1). www.cuidol.in Unit-10-11(MCA 632) All right are reserved with CU-IDOL

Travelling Salesperson B&B 32 9. A 1st level node has moved to the front of the live-node list. (B1,D5,H4,B2,D1) 10. (H2,D5,H4,B2,D1) 11. (D5,H4,B2,D1) 12. (H4,B2,D1) 13. (B2,D1) 14. (H3,D1) www.cuidol.in Unit-10-11(MCA 632) All right are reserved with CU-IDOL

Travelling Salesperson 33 B&B 15. (D1) www.cuidol.in Unit-10-11(MCA 632) 3A3ll right are reserved with CU-IDOL

Travelling Salesperson 34 B&B 16. We have verified that a minimal tour has length >= 28. Since our candidate tour has a length of 28 we now know that it is a minimal tour, we can use it without further searching of the state-space tree. www.cuidol.in Unit-10-11(MCA 632) All right are reserved with CU-IDOL

B&B 35  FIFO branch and bound finds solution closest to root.  Backtracking may never find a solution because tree depth is infinite (unless repeating configurations are eliminated).  Least-cost branch and bound directs the search to parts of the space most likely to contain the answer. So it could perform better than backtracking. www.cuidol.in Unit-10-11(MCA 632) All right are reserved with CU-IDOL

Decision and Optimization 36 Problems Decision Problem: computational problem with intended output of “yes” or “no”, 1 or 0 Optimization Problem: computational problem where we try to maximize or minimize some value Introduce parameter k and ask if the optimal value for the problem is a most or at least k. Turn optimization into decision www.cuidol.in Unit-10-11(MCA 632) All right are reserved with CU-IDOL

Class P 37 The class P consists of those problems that are solvable in polynomial time. More specifically, they are problems that can be solved in time O(nk) for some constant k, where n is the size of the input to the problem The key is that n is the size of input www.cuidol.in Unit-10-11(MCA 632) All right are reserved with CU-IDOL

NP 38 NP is not the same as non-polynomial complexity/running time. NP does not stand for not polynomial. NP = Non-Deterministic polynomial time NP means verifiable in polynomial time Verifiable? If we are somehow given a „certificate‟ of a solution we can verify the legitimacy in polynomial time www.cuidol.in Unit-10-11(MCA 632) All right are reserved with CU-IDOL

Relation of P and NP 39 P is a subset of NP “P = NP”? Language L is in NP, complement of L is in co-NP co-NP ≠ NP P ≠ co-NP www.cuidol.in Unit-10-11(MCA 632) All right are reserved with CU-IDOL

NP-Hard and NP-Complete 40 Language M is NP-hard if every other language L in NP is polynomial-time reducible to M For every L that is a member of NP, LpolyM If language M is NP-hard and also in the class of NP itself, then M is NP-complete www.cuidol.in Unit-10-11(MCA 632) All right are reserved with CU-IDOL

Polynomial-Time Reducibility 41 Language L is polynomial-time reducible to language M if there is a function computable in polynomial time that takes an input x of L and transforms it to an input f(x) of M, such that x is a member of L if and only if f(x) is a member of M. Shorthand, LpolyM means L is polynomial-time reducible to M www.cuidol.in Unit-10-11(MCA 632) All right are reserved with CU-IDOL

NP-Hard and NP-Complete 42 Restriction: A known NP-complete problem M is actually just a special case of L Local replacement: reduce a known NP-complete problem M to L by dividing instances of M and L into “basic units” then showing each unit of M can be converted to a unit of L Component design: reduce a known NP-complete problem M to L by building components for an instance of L that enforce important structural functions for instances of M. ww1w3.c-0ui3d-o2l.i0n20 Unit-10-11(MCA 632) 4A2ll right are reserved with CU-IDOL

MULTIPLE CHOICE QUESTIONES 43 1. The optimal solution to a problem is a combination of optimal solutions to its sub-problems. This is known as A).Principleof Duality B) Principle of Feasibility C) Principle of Optimality D) Principle of Dynamicity 2.The _______ is a touring problem in which each city must be visited exactly once. The aim is to find the shortest tour. A) Finding shortest path between a source and a destination B) Travelling Salesman problem C) Map coloring problem D) Depth first search traversal on a given map represented as a graph www.cuidol.in Unit-10-11(MCA 632) All right are reserved with CU-IDOL

MULTIPLE CHOICE QUESTIONES 44 3. Which of the following is not a backtracking algorithm? A) Knight tour problem B) N queen problem C) Tower of hanoi D) M coloring proble 4. What is the type of the algorithm used in solving the 8 Queens problem? A) Greedy B) Dynamic C) Branch and Bound D) Backtracking. www.cuidol.in Unit-10-11(MCA 632) All right are reserved with CU-IDOL

ANSWERS 45 1. C) 2. B) 3. C) 4. D) www.cuidol.in Unit-10-11(MCA 632) All right are reserved with CU-IDOL

SUMMARY 46 This presentation includes both unit 10 and 11. After completion of Greedy approach and Dynamic approach we have further Backtracking and Branch and Bound techniques to solve optimisation problems. In Backtracking we use a tree path and traverse that state space tree by top to bottom covering whole path. And then go back to traverse another path. Some of its applications are N Queen problem, Graph coloring problem and Sum of Subset Problem. Further in branch and bound we traverse that state space tree from lest to right that is level wise. And its applications are Travelling salesperson problem and Assignment Problem. www.cuidol.in Unit-10-11(MCA 632) All right are reserved with CU-IDOL

FREQUENTLY ASKED QUESTION 47 Q1. Discuss Backtracking. Ans. This is an optimization technique by which we use a tree path and go backward to find the best route.. For Further details please refer to the SLM Q2. Design a TSP network for any given data. Ans. Go through previous slides to calculate the code. For Further details please refer to the SLM Q3. Discuss about NP hard and NP complete. Ans. These are non polynomial problems. For Further details please refer to the SLM www.cuidol.in Unit-10-11(MCA 632) All right are reserved with CU-IDOL

REFRENCES 48 1) Data Structures and Algorithms made easy By Narasimha Karumanchi. 2) The Algorithm Design Manual, 2nd Edition by Steven S Skiena 3) Fundamentals of Computer Algorithms - Horowitz and Sahani 4) https://www.geeksforgeeks.org/branch-and-bound-algorithm/ 5) https://www.geeksforgeeks.org/backtracking-algorithms/ www.cuidol.in Unit-10-11(MCA 632) All right are reserved with CU-IDOL

49 THANK YOU www.cuidol.in Unit-10-11(MCA 632) All right are reserved with CU-IDOL