{"id":35,"date":"2018-07-18T11:21:01","date_gmt":"2018-07-18T11:21:01","guid":{"rendered":"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/?post_type=chapter&#038;p=35"},"modified":"2018-07-25T05:53:51","modified_gmt":"2018-07-25T05:53:51","slug":"exhaustive-searching-and-combinatorial-optimization-problems","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/chapter\/exhaustive-searching-and-combinatorial-optimization-problems\/","title":{"rendered":"Exhaustive Searching and Combinatorial Optimization Problems"},"content":{"raw":"<div>\r\n<div style=\"text-align: center\">\r\n\r\n<strong>Module 9:<\/strong>\r\n<p class=\"hanging-indent\"><strong>Exhaustive Search and Combinatorial Optimization Problem<\/strong><\/p>\r\n\r\n<\/div>\r\n<p style=\"text-align: justify\">This module 9 focuses on the basics of the combinatorial optimization problems. The Learning objectives of this module are as follows:<\/p>\r\n\r\n<ul>\r\n \t<li style=\"text-align: justify\">To introduce Combinatorial Optimization Problems and brute force approach<\/li>\r\n \t<li style=\"text-align: justify\">To understand the concept of Exhaustive Searching<\/li>\r\n \t<li style=\"text-align: justify\">To know about 15-Puzzle game<\/li>\r\n \t<li style=\"text-align: justify\">To know about 8-Queen Problem<\/li>\r\n \t<li style=\"text-align: justify\">To know about Knapsack Problem<\/li>\r\n \t<li style=\"text-align: justify\">To understand assignment Problem<\/li>\r\n<\/ul>\r\n<p style=\"text-align: justify\"><strong>What is a brute force approach?<\/strong><\/p>\r\n<p style=\"text-align: justify\">A brute force approach is a straight forward approach based on the problem statement and definitions of the concepts involved [2]. The general framework of brute force approach of brute force approach is as follows:<\/p>\r\n\r\n<ol>\r\n \t<li style=\"text-align: justify\">Generate all combinatorial structures that represent all feasible solutions. The combinatorial structures are sets, trees, graphs, permutations, and Catalan families.<\/li>\r\n \t<li style=\"text-align: justify\">Search for the best solution among the generated feasibility solutions.<\/li>\r\n<\/ol>\r\n<p class=\"hanging-indent\"><strong>The advantages of the brute force approach is as follows:<\/strong><\/p>\r\n\r\n<ol>\r\n \t<li style=\"text-align: justify\">Wide applicability of brute force approaches. Brute force approach can be applied for all variety of problems.<\/li>\r\n \t<li style=\"text-align: justify\">Simplicity of the brute force approach.<\/li>\r\n \t<li style=\"text-align: justify\">Brute force approach can yield reasonable algorithms for all important problems.<\/li>\r\n \t<li style=\"text-align: justify\">Brute force approach can yield algorithms that can be used as a benchmark for comparing\u00a0<strong style=\"font-size: 1em\">algorithms of other design <\/strong><span style=\"font-size: 1em\">approaches<\/span><strong style=\"font-size: 1em\">.<\/strong><\/li>\r\n<\/ol>\r\n<p style=\"text-align: justify\"><strong>The disadvantage of brute force approaches are<\/strong><\/p>\r\n\r\n<ol>\r\n \t<li style=\"text-align: justify\">Often brute force algorithms are inefficient.<\/li>\r\n \t<li style=\"text-align: justify\">There is not much constructive or creativity involved in brute force algorithms.<\/li>\r\n<\/ol>\r\n<\/div>\r\n<div style=\"text-align: justify\">\r\n\r\n<strong>Optimization Problem and Exhaustive Searching<\/strong>\r\n<p style=\"text-align: justify\">Exhaustive searching is a strategy usually employed for combinatorial problems. What is an optimization problem? An optimization problem has<\/p>\r\n\r\n<ol>\r\n \t<li style=\"text-align: justify\">Objective function: This is in the form of maximization or minimization of some constraint.<\/li>\r\n \t<li style=\"text-align: justify\">Predicate P that specifies the feasibility criteria<\/li>\r\n \t<li style=\"text-align: justify\">Solution space U with all possible solutions and extremum requirements<\/li>\r\n \t<li style=\"text-align: justify\">The aim is to find solution that satisfies the feasibility criteria.<\/li>\r\n<\/ol>\r\n<p style=\"text-align: justify\">Some of the examples of optimization problems that are discussed in module are 15-puzzle problem, 8-Queen problem, Knapsack problem and Assignment problem. Combinatorial optimization problem uses combinatorial structures such as sets, trees, graphs, permutations, and Catalan families.<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">Exhaustive search is a strategy for solving combinatorial optimization problems is to use exhaustive search. Exhaustive search involves these steps:<\/p>\r\n\r\n<ol>\r\n \t<li style=\"text-align: justify\">List all solutions of the problem<\/li>\r\n \t<li style=\"text-align: justify\">Often state space tree is used to represent all possible solutions.<\/li>\r\n \t<li style=\"text-align: justify\">Then the solution is searched in the state space tree that has least cost or optimal using a search technique.<\/li>\r\n<\/ol>\r\n<p style=\"text-align: justify\">This approach is using a brute force to search for finding solutions. The advantage is the guaranteed solution. But the disadvantage of this approach is a problem called \u201cCombinatorial explosion\u201d where the increase in input is associated with the rapid increase in output.<\/p>\r\n&nbsp;\r\n\r\nLet us discuss about applying brute force approach for some of the important problems now:\r\n\r\n<\/div>\r\n<div style=\"text-align: justify\">\r\n\r\n<strong>Solution Space and Unintelligent Search techniques:<\/strong>\r\n<p style=\"text-align: justify\">The solution space is in the form of a graph. A sample solution space is shown in Fig. 2. Some of the important terminologies used in association with the solution space is given below:<\/p>\r\n\r\n<ol>\r\n \t<li style=\"text-align: justify\">Root: Root of a graph has no predecessor. In solution space, it is the initial configuration.<\/li>\r\n \t<li style=\"text-align: justify\">Solution Space: All the configurations in the form of a state space tree is called solution space. The target configuration is somewhere in the solution space.<\/li>\r\n \t<li style=\"text-align: justify\">Search techniques: Once a solution space is available, then the tree can be searched using search techniques like DFS and BFS.<\/li>\r\n<\/ol>\r\nLet us review about DFS and BFS now:\r\n\r\n&nbsp;\r\n<p class=\"hanging-indent\"><strong>DFS Search<\/strong><\/p>\r\n<p style=\"text-align: justify\">Depth First Search (DFS) is an unintelligent search that is used to search a graph. DFS uses a stack for traversing a graph. Initially, the root node is pushed onto a stack. Then, it is checked for goal node. If it is a goal node, then DFS reports success. Otherwise, its children is generated and pushed onto a stack. This procedure is repeated till stack is empty.<\/p>\r\n&nbsp;\r\n\r\nThe procedure of DFS is given below:\r\n\r\n&nbsp;\r\n\r\nPut the root node on a stack S;\r\n\r\nwhile (S is not empty) {\r\n\r\nremove a node from the S;\r\n\r\nif (node = goal node) return success;\r\n\r\nput all children of node onto the S;\r\n\r\n}\r\n\r\n&nbsp;\r\n\r\nreturn failure;\r\n\r\n&nbsp;\r\n\r\nThe following example illustrates usage of DFS.\r\n\r\n<\/div>\r\n<div style=\"text-align: justify\">\r\n<p style=\"text-align: justify\"><strong>Example 1: Assume goal nodes are N and J. Show the DFS search of the following graph shown in Fig. 1 for finding the goal nodes?<\/strong><\/p>\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n<img class=\"aligncenter size-full wp-image-203\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M09Pic1-1.png\" alt=\"\" width=\"384\" height=\"423\" \/>\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n<p style=\"text-align: center\"><strong>Fig 1: A sample Graph<\/strong><\/p>\r\n&nbsp;\r\n<p class=\"hanging-indent\"><strong>Nodes that are explored in the order are ; A B D E L M N I O C F G J<\/strong><\/p>\r\n&nbsp;\r\n<p class=\"hanging-indent\"><strong>BFS Search<\/strong><\/p>\r\n<p style=\"text-align: justify\">Breadth First Search (BFS) is also an unintelligent search that is used to search a graph. BFS traverse a graph level-by-level. It uses a queue data structure for traversing a graph. Initially, the root node is added onto a queue. Then, it is checked for goal node. If it is a goal node, then BFS reports success. Otherwise, its children is generated and pushed onto a rear end of the queue Q. This procedure is repeated till Queue is empty.<\/p>\r\n\r\n<\/div>\r\n<div style=\"text-align: justify\">\r\n\r\n<strong>The procedure of BFS is given below:<\/strong>\r\n\r\n&nbsp;\r\n\r\nPut the root node on a queue Q;\r\n\r\nwhile (Q is not empty) {\r\n\r\nremove a node from the queue Q;\r\n\r\nif (node = goal node) return success;\r\n\r\nput all children of node onto the queue Q;\r\n\r\n}\r\n\r\nreturn failure;\r\n\r\n&nbsp;\r\n\r\nThe following example illustrates usage of BFS.\r\n\r\n&nbsp;\r\n\r\n<strong>Example 2: Assume goal nodes are N and J. Show the BFS search of the following graph shown in Fig. 2 for finding the goal nodes?<\/strong>\r\n\r\n<img class=\"aligncenter size-full wp-image-204\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M09Pic2.png\" alt=\"\" width=\"413\" height=\"415\" \/>\r\n\r\n&nbsp;\r\n<p style=\"text-align: center\"><strong>Fig 2: A sample Graph<\/strong><\/p>\r\n\r\n<\/div>\r\n<p style=\"text-align: justify\"><strong>\u00a0<\/strong><\/p>\r\n\r\n<div style=\"text-align: justify\">\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n<p class=\"hanging-indent\">The nodes that are explored in BFS order is :\u00a0 A B C D E F G H I J L M N O<\/p>\r\n&nbsp;\r\n<p class=\"hanging-indent\"><strong>15-Puzzle Problem<\/strong><\/p>\r\n<p style=\"text-align: justify\">In 1878, Sam Lloyd designed a puzzle called 15-puzzle game. It is a game where a initial and target configuration is given. The game is about moving tile so that the target configuration is reached from the initial configuration. In other words, the objective of the game is to change initial state to goal state. The possible configurations of moving the up, down, right or left using the empty tile. So a node can have at most possible four moves. A sample initial and target configuration is given below in Fig. 3.<\/p>\r\n&nbsp;\r\n\r\n<img class=\"aligncenter size-full wp-image-205\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M09Pic3.png\" alt=\"\" width=\"267\" height=\"142\" \/>\r\n\r\n&nbsp;\r\n<p style=\"text-align: center\"><strong>Fig. 3. : Initial and Target configuration<\/strong><\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">A brute force algorithm can be written to generate the solution space. The repeated application of the legal moves, top, bottom, right and left results in a graph called state space or <strong>solution space<\/strong>. This is shown in Fig. 4.<\/p>\r\n<img class=\"aligncenter size-full wp-image-206\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M09Pic4.png\" alt=\"\" width=\"642\" height=\"237\" \/>\r\n\r\n&nbsp;\r\n<p style=\"text-align: center\">Fig. 4: <strong>Portion of a Graph<\/strong><strong style=\"text-align: justify;font-size: 1em\">\u00a0<\/strong><\/p>\r\n\r\n<\/div>\r\n<div style=\"text-align: justify\">\r\n<p style=\"text-align: justify\">The goal state may be present somewhere in the solution space. Now, Exhaustive search technique is about finding the path from the starting node to the goal state. This may be done using DFS or BFS.<\/p>\r\n&nbsp;\r\n<p class=\"hanging-indent\">Formal Algorithm<\/p>\r\n<p class=\"hanging-indent\">The formal algorithm based on [1] for 15-puzzle is given as follows:<\/p>\r\n&nbsp;\r\n\r\nAlgorithm 15puzzle (G, root, goal)\r\n\r\n%%\u00a0\u00a0 Input: State space tree with root and target goal state\r\n\r\n%%\u00a0\u00a0 Path from root to goal node\r\n\r\nBegin\r\n\r\nfor all nodes make visit = 0\r\n\r\n%%\u00a0\u00a0 Let root be the starting node visited[root] = 1\r\n\r\ngenerate children w for root for all w do\r\n\r\nIf (visited[w] = 0) and (w is not goal node) then call DFS(G,w)\r\n\r\nend if\r\n\r\nend for\r\n\r\nEnd\r\n\r\n&nbsp;\r\n<p class=\"hanging-indent\"><strong>Complexity Analysis<\/strong><\/p>\r\n<p style=\"text-align: justify\">This brute force algorithm for 15-Puzzle game is inefficient and unrealistic. For 15-puzzle\u00a0\u00a0problem<span style=\"text-align: initial;font-size: 1em\">, there will be 16! (\u00bb 20.9 X 1012) different arrangements of tiles. Hence <\/span>searching\u00a0\u00a0<span style=\"text-align: initial;font-size: 1em\">for the solution takes exponential time.<\/span><\/p>\r\n\r\n<\/div>\r\n<div style=\"text-align: justify\">\r\n\r\n<strong>8-Queen Problem<\/strong>\r\n<p style=\"text-align: justify\">The problem of eight queens is that of placing 8 queens in a non-attacking position. The problem of 8-queen problem is to generate a board configuration where the queens are in non-attacking positions.<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">The movement of queen is shown in Fig. 5. It can be observed that a queen can move in horizontal, vertical and diagonal ways.<\/p>\r\n<img class=\"aligncenter size-full wp-image-207\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M09Pic5.png\" alt=\"\" width=\"261\" height=\"254\" \/>\r\n<p style=\"text-align: center\"><strong>Fig. 5: The movement of a Queen<\/strong><\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">The brute force algorithm would be to try all possible combinations to check out the placement of the queens such that they are in a non-attacking position.<\/p>\r\n&nbsp;\r\n\r\nThe informal algorithm is as follows:\r\n<ol>\r\n \t<li>Try all combinations<\/li>\r\n \t<li>Check whether the queens are in attacking position<\/li>\r\n \t<li>Repeat steps 1 and 2 until a valid configuration is possible.<\/li>\r\n<\/ol>\r\n<\/div>\r\n<div style=\"text-align: justify\">\r\n\r\nThe formal algorithm based on [1] is given as follows:\r\n\r\n&nbsp;\r\n\r\nAlgorithm 8queen(n)\r\n\r\n%% Input: A 8 x 8 chess board and \u20188\u2019 queens\r\n\r\n%%\u00a0\u00a0\u00a0\u00a0 <strong>Output<\/strong>: Solution of 8-queen problem Begin<strong>\u00a0<\/strong>\r\n\r\nn = 8<strong>\u00a0<\/strong>\r\n\r\nfor i1 = 1 to n do for i2 = 1 to n do for i3 = 1 to n do for i4 = 1 to n do<strong>\u00a0<\/strong>\r\n\r\nfor i5 = 1 to n do for i6 = 1 to n do for i7 = 1 to n do for i8 = 1 to n do\r\n\r\nsol = [i1, i2, i3, i4, i5, i6, i7, i8]\r\n\r\n%%\u00a0\u00a0 check the solution with respect to constraints of\r\n\r\n%%\u00a0\u00a0 non-attacking queen\r\n\r\nif sol is correct then print sol\r\n\r\nEnd if\r\n\r\nEnd for\r\n\r\nEnd for\r\n\r\nEnd for\r\n\r\nEnd for\r\n\r\nEnd for\r\n\r\nEnd for\r\n\r\nEnd for\r\n\r\nEnd for\r\n\r\nEnd.\r\n\r\n&nbsp;\r\n<p class=\"hanging-indent\"><strong>Complexity Analysis:<\/strong><\/p>\r\n<p style=\"text-align: justify\">Even though, the solution for 8-queen problem looks simple, in reality solution involves a\u00a0<span style=\"font-size: 1em;text-align: initial\">combination of\u00a0\u00a0<\/span><span style=\"text-align: initial;font-size: 1em\">64!<\/span><span style=\"text-align: initial;font-size: 1em\">56!\u00a0<\/span><span style=\"text-align: initial;font-size: 1em\">positions (56 = 64-8). This makes <\/span>exhaustive<span style=\"text-align: initial;font-size: 1em\"> search a difficult process.<\/span><\/p>\r\n\r\n<\/div>\r\n<p style=\"text-align: justify\"><span style=\"text-align: initial;font-size: 1em\">There are many solutions <\/span>for<span style=\"text-align: initial;font-size: 1em\"> the 8-queen problem.<\/span><\/p>\r\n\r\n<div style=\"text-align: justify\">\r\n\r\n<strong>Knapsack problem<\/strong>\r\n<p style=\"text-align: justify\">Knapsack problem is one of the most popular algorithms that we often encounter in our daily life. It was designed by Denzig in 1950. A Knapsack problem has a knapsack of capacity K.<\/p>\r\n<p style=\"text-align: justify\">There are n different items, each of which is associated with <em>W<\/em><em>i<\/em> and profit Pi (It is also called as value). The objective of knapsack problem is to load knapsack to maximize profit subjected to the capacity of knapsack.<\/p>\r\n&nbsp;\r\n<p class=\"hanging-indent\"><strong>Mathematical Formulation:<\/strong><\/p>\r\n<img class=\"aligncenter size-full wp-image-208\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M09Pic6.png\" alt=\"\" width=\"402\" height=\"179\" \/>\r\n\r\n<\/div>\r\n<div style=\"text-align: justify\">\r\n<p style=\"text-align: justify\">There are two types pf knapsack problem. It is easy to solve <strong>fractional knapsack problem.\u00a0<\/strong><strong>This problem allows loading of knapsack with fractional items. This is possible if the items to be loaded are like <\/strong>cloth, liquid, gold dust, etc. On the other hand, Integer knapsack problem, also known as 0\/1 knapsack, is hard to solve. This problem is applicable for items which can either be loaded full or not at all. The items here are like electronic items, machineries or any items that can be broken.<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">Let us consider a scenario where there are three bottles of Salt with their weights and profits as shown in Fig. 6.<\/p>\r\n\r\n<\/div>\r\n<div style=\"text-align: justify\">\r\n\r\n<img class=\"aligncenter size-full wp-image-209\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M09Pic7.png\" alt=\"\" width=\"1614\" height=\"1367\" \/>\r\n<p style=\"text-align: center\"><strong>Fig.6 : Knapsack problem<\/strong><\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">The bigger bottle is knapsack. The capacities and profits are are shown in Fig. 6. So the question here is how to fill the knapsack effectively so that profit is higher subjected to the capacity of the knapsack.<\/p>\r\n\r\n<\/div>\r\n<div style=\"text-align: justify\">\r\n\r\n<strong>Informal Algorithm:<\/strong>\r\n<ol>\r\n \t<li>Generate all possible sets. There will be 2<em>n<\/em>\u00a0 possible subsets for \u2018n\u2019 items.<\/li>\r\n \t<li>Generate a binary string of length<\/li>\r\n \t<li>If the binary bit is 1, then include, otherwise exclude the item subjected to the constraints.<\/li>\r\n \t<li>Compute the maximum profit and Weight for all combinations and report maximum profit.<\/li>\r\n \t<li>Exit.<\/li>\r\n<\/ol>\r\n<strong>Formal Algorithm:<\/strong>\r\n\r\n&nbsp;\r\n<p class=\"hanging-indent\">Formally, the knapsack problem based on [1] is given as follows:<\/p>\r\n&nbsp;\r\n\r\nAlgorithm knapsack(K, w[1..n],p[1..n])\r\n\r\n%%\u00a0\u00a0 Input: Knapsack with capacity K , weights and profits\r\n\r\n%%\u00a0\u00a0 Output: Knapsack items and maximum weight and profit\r\n\r\nBegin\r\n\r\nglobalprofit = 0\r\n\r\nchoice = 0 index = 1\r\n\r\nwhile (index &lt;= 2n ) do\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 %% for all 2n subsets\r\n\r\nprofit = 0\r\n\r\nweight = 0\r\n\r\nfor i = 1 to n do\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 %% for all n items\r\n\r\nif (binary(index, i) == 0) \u00a0then\u00a0\u00a0\u00a0\u00a0 %% Item is excluded if binary bit is 0 profit = profit + 0\r\n\r\nweight = weight +0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 %% generate binary bit i for item index else profit = profit + p[i]\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 %% Update if Binary bit is 1\r\n\r\nweight = weight +w[i] End if\r\n\r\n<span style=\"text-align: initial;text-indent: 1em;font-size: 1em\">End for<\/span>\r\n\r\nif ((weight &lt;= K) and (profit &gt; globalprofit)) then %% Check the constraints globalprofit = profit\r\n\r\nchoice = i\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 %% Note the combination\r\n\r\nEnd if\r\n\r\nindex = index +1\r\n\r\nEnd while\r\n\r\nEnd\r\n\r\n<\/div>\r\n<div style=\"text-align: justify\">\r\n\r\nThis is illustrated in Example 3.\r\n<p class=\"hanging-indent\"><strong>Example 3: <\/strong>Consider three items. Generate all the possibilities:<\/p>\r\nThe possibilities are\r\n\r\n\u03c6\r\n\r\n{1}\r\n\r\n{2}\r\n\r\n{3}\r\n\r\n{1, 2}\r\n\r\n{1, 3}\r\n\r\n{2, 3}\r\n\r\n{1,2,3}\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Then all combinations are tried out subjected to the constraints. The profit is computed for every case and maximum profit is reported.<\/p>\r\n&nbsp;\r\n<p class=\"hanging-indent\"><strong>Complexity Analysis:<\/strong><\/p>\r\n<p style=\"text-align: justify\">This involves generation of 2\u00a0 n\u00a0 combinations. Hence, the complexity of the algorithm leads\u00a0\u00a0<span style=\"text-align: initial;text-indent: 1em;font-size: 1em\">to a \u038f (2n) algorithm. The implication of NP-hard is that it would be difficult to solve the problem.<\/span><\/p>\r\n&nbsp;\r\n<p class=\"hanging-indent\"><strong>Assignment Problem<\/strong><\/p>\r\n<p class=\"indent\" style=\"text-align: justify\"><span style=\"text-align: justify;font-size: 1em\">Assignment problem is to assign m persons to n jobs such that the cost is minimized. This problem can be solved using brute force approach. All possible combinations are tried out and cost is computed. Finally, the least cost assignment is reported.<\/span><\/p>\r\n\r\n<\/div>\r\n<div style=\"text-align: justify\">\r\n\r\n<strong>Informal Algorithm<\/strong>\r\n<p class=\"hanging-indent\">The informal algorithm is stated as below;<\/p>\r\n\r\n<ol>\r\n \t<li>Generate all permutation of assignments<\/li>\r\n \t<li>Compute the cost for all assignments<\/li>\r\n \t<li style=\"text-align: justify\">Choose the minimum cost assignment and report.<\/li>\r\n \t<li>End.<\/li>\r\n<\/ol>\r\n<strong>Formal Algorithm<\/strong>\r\n\r\n&nbsp;\r\n\r\nThe formal algorithm based on [1] is given below:\r\n\r\nAlgorithm Assign(person[1..n],job[1..n])\r\n\r\n%%\u00a0\u00a0 Input; person and jobs\r\n\r\n%%\u00a0\u00a0 Output: Optimal assignment of person to job Begin\r\n\r\npermutate all legitimate assignments ai\r\n\r\ncompute the assignment [a1, a2,.., an] whose cost is minimum assign as per minimum cost and return min_cost\r\n\r\nEnd\r\n\r\n&nbsp;\r\n\r\nThe following Example 4 illustrates the application of this algorithm:\r\n\r\n&nbsp;\r\n\r\n<strong>Example 4:<\/strong>\u00a0\u00a0\u00a0 A sample assignment Table in given in table 1.\r\n\r\n&nbsp;\r\n\r\nTable 1: Sample assignment Table\r\n\r\n&nbsp;\r\n\r\n<img class=\"size-full wp-image-44 aligncenter\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/Untitled-9.png\" alt=\"\" width=\"549\" height=\"176\" \/>\r\n\r\nUse assignment algorithm and find optimal cost?\r\n\r\n<\/div>\r\n<div style=\"text-align: justify\">\r\n<p style=\"text-align: justify\">There are 3 persons and 3 jobs. The question is how to assign the jobs to persons in an optimal manner based on the cost matrix given above. For example, if a random assignment is made like assign the job 1 to person 1 (C(1,1)), job 2 to person 2 (C(2,2)) and job 3 to person 3(C(3,3)), then the cost of the assignment would be<\/p>\r\n&nbsp;\r\n\r\n&lt; 1 2 3&gt;\u00a0\u00a0 =\u00a0\u00a0\u00a0 3 + 3 + 2 = 8\r\n\r\n&nbsp;\r\n\r\nFor the above problem, all the possible cost assignments are given below in Table 2.\r\n\r\n&nbsp;\r\n<p style=\"text-align: center\"><strong>Table 2: Possible assignments<\/strong><\/p>\r\n\r\n<table style=\"height: 281px\" width=\"823\">\r\n<tbody>\r\n<tr>\r\n<td style=\"width: 100.063px\">J1<\/td>\r\n<td style=\"width: 114.063px\">J2<\/td>\r\n<td style=\"width: 114.063px\">J3<\/td>\r\n<td style=\"width: 438.063px\">Cost<\/td>\r\n<\/tr>\r\n<tr>\r\n<td style=\"width: 100.063px\">1<\/td>\r\n<td style=\"width: 114.063px\">2<\/td>\r\n<td style=\"width: 114.063px\">3<\/td>\r\n<td style=\"width: 438.063px\">3 + 3 + 2 = 8<\/td>\r\n<\/tr>\r\n<tr>\r\n<td style=\"width: 100.063px\">1<\/td>\r\n<td style=\"width: 114.063px\">3<\/td>\r\n<td style=\"width: 114.063px\">2<\/td>\r\n<td style=\"width: 438.063px\">3 + 7 + 9 = 19<\/td>\r\n<\/tr>\r\n<tr>\r\n<td style=\"width: 100.063px\">2<\/td>\r\n<td style=\"width: 114.063px\">1<\/td>\r\n<td style=\"width: 114.063px\">3<\/td>\r\n<td style=\"width: 438.063px\">4 + 2 + 2 = 8<\/td>\r\n<\/tr>\r\n<tr>\r\n<td style=\"width: 100.063px\">2<\/td>\r\n<td style=\"width: 114.063px\">3<\/td>\r\n<td style=\"width: 114.063px\">1<\/td>\r\n<td style=\"width: 438.063px\">4 + 7 + 8 = 19<\/td>\r\n<\/tr>\r\n<tr>\r\n<td style=\"width: 100.063px\">3<\/td>\r\n<td style=\"width: 114.063px\">1<\/td>\r\n<td style=\"width: 114.063px\">2<\/td>\r\n<td style=\"width: 438.063px\">5 + 2 + 9 = 16<\/td>\r\n<\/tr>\r\n<tr>\r\n<td style=\"width: 100.063px\">3<\/td>\r\n<td style=\"width: 114.063px\">2<\/td>\r\n<td style=\"width: 114.063px\">1<\/td>\r\n<td style=\"width: 438.063px\">5 + 3 + 8 = 16<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n<p style=\"text-align: justify\">It can be observed that the optimal order is &lt; 1 2 3&gt; and &lt;2 1 3&gt; as they are associated least cost.<\/p>\r\n&nbsp;\r\n<p class=\"hanging-indent\"><strong>Complexity Analysis<\/strong><\/p>\r\n<p style=\"text-align: justify\">Again, the complexity analysis shows that the number of permutations are n!. Therefore, the complexity of the problem is O(n!).<\/p>\r\n&nbsp;\r\n<p class=\"hanging-indent\"><strong>Summary<\/strong><\/p>\r\n\r\n<\/div>\r\n<p style=\"text-align: justify\">In short, one can conclude as part of this module 9 that<\/p>\r\n\r\n<ul style=\"text-align: justify\">\r\n \t<li>Brute force guarantee solutions but it is inefficient.<\/li>\r\n \t<li>It is difficult to solve combinatorial optimization problems.<\/li>\r\n \t<li>15 Puzzle, 8-Queen, Knapsack and assignment problems are optimization problem that can be solved using brute force method.<\/li>\r\n<\/ul>\r\n<p style=\"text-align: justify\"><strong>References:<\/strong><\/p>\r\n\r\n<ol>\r\n \t<li style=\"text-align: justify\">S.Sridhar \u2013 Design and Analysis of Algorithms, Oxford University Press, 2014.<\/li>\r\n \t<li style=\"text-align: justify\">A.Lvitin \u2013 Introduction to Design and Analysis of Algorithms, 2rd Edition, Pearson Education, 2014.<\/li>\r\n \t<li style=\"text-align: justify\">Cormen, T.H., C.E. Leiserson, and R.L. Rivest, Introduction to Algorithms, MIT Press, Cambridge, MA 1992.<\/li>\r\n \t<li style=\"text-align: justify\">URL: <a href=\"http:\/\/www.hbmeyer.de\/backtrack\/achtdamen\/eight.htm\">http:\/\/www.hbmeyer.de\/backtrack\/achtdamen\/eight.htm#up<\/a><\/li>\r\n<\/ol>","rendered":"<div>\n<div style=\"text-align: center\">\n<p><strong>Module 9:<\/strong><\/p>\n<p class=\"hanging-indent\"><strong>Exhaustive Search and Combinatorial Optimization Problem<\/strong><\/p>\n<\/div>\n<p style=\"text-align: justify\">This module 9 focuses on the basics of the combinatorial optimization problems. The Learning objectives of this module are as follows:<\/p>\n<ul>\n<li style=\"text-align: justify\">To introduce Combinatorial Optimization Problems and brute force approach<\/li>\n<li style=\"text-align: justify\">To understand the concept of Exhaustive Searching<\/li>\n<li style=\"text-align: justify\">To know about 15-Puzzle game<\/li>\n<li style=\"text-align: justify\">To know about 8-Queen Problem<\/li>\n<li style=\"text-align: justify\">To know about Knapsack Problem<\/li>\n<li style=\"text-align: justify\">To understand assignment Problem<\/li>\n<\/ul>\n<p style=\"text-align: justify\"><strong>What is a brute force approach?<\/strong><\/p>\n<p style=\"text-align: justify\">A brute force approach is a straight forward approach based on the problem statement and definitions of the concepts involved [2]. The general framework of brute force approach of brute force approach is as follows:<\/p>\n<ol>\n<li style=\"text-align: justify\">Generate all combinatorial structures that represent all feasible solutions. The combinatorial structures are sets, trees, graphs, permutations, and Catalan families.<\/li>\n<li style=\"text-align: justify\">Search for the best solution among the generated feasibility solutions.<\/li>\n<\/ol>\n<p class=\"hanging-indent\"><strong>The advantages of the brute force approach is as follows:<\/strong><\/p>\n<ol>\n<li style=\"text-align: justify\">Wide applicability of brute force approaches. Brute force approach can be applied for all variety of problems.<\/li>\n<li style=\"text-align: justify\">Simplicity of the brute force approach.<\/li>\n<li style=\"text-align: justify\">Brute force approach can yield reasonable algorithms for all important problems.<\/li>\n<li style=\"text-align: justify\">Brute force approach can yield algorithms that can be used as a benchmark for comparing\u00a0<strong style=\"font-size: 1em\">algorithms of other design <\/strong><span style=\"font-size: 1em\">approaches<\/span><strong style=\"font-size: 1em\">.<\/strong><\/li>\n<\/ol>\n<p style=\"text-align: justify\"><strong>The disadvantage of brute force approaches are<\/strong><\/p>\n<ol>\n<li style=\"text-align: justify\">Often brute force algorithms are inefficient.<\/li>\n<li style=\"text-align: justify\">There is not much constructive or creativity involved in brute force algorithms.<\/li>\n<\/ol>\n<\/div>\n<div style=\"text-align: justify\">\n<p><strong>Optimization Problem and Exhaustive Searching<\/strong><\/p>\n<p style=\"text-align: justify\">Exhaustive searching is a strategy usually employed for combinatorial problems. What is an optimization problem? An optimization problem has<\/p>\n<ol>\n<li style=\"text-align: justify\">Objective function: This is in the form of maximization or minimization of some constraint.<\/li>\n<li style=\"text-align: justify\">Predicate P that specifies the feasibility criteria<\/li>\n<li style=\"text-align: justify\">Solution space U with all possible solutions and extremum requirements<\/li>\n<li style=\"text-align: justify\">The aim is to find solution that satisfies the feasibility criteria.<\/li>\n<\/ol>\n<p style=\"text-align: justify\">Some of the examples of optimization problems that are discussed in module are 15-puzzle problem, 8-Queen problem, Knapsack problem and Assignment problem. Combinatorial optimization problem uses combinatorial structures such as sets, trees, graphs, permutations, and Catalan families.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Exhaustive search is a strategy for solving combinatorial optimization problems is to use exhaustive search. Exhaustive search involves these steps:<\/p>\n<ol>\n<li style=\"text-align: justify\">List all solutions of the problem<\/li>\n<li style=\"text-align: justify\">Often state space tree is used to represent all possible solutions.<\/li>\n<li style=\"text-align: justify\">Then the solution is searched in the state space tree that has least cost or optimal using a search technique.<\/li>\n<\/ol>\n<p style=\"text-align: justify\">This approach is using a brute force to search for finding solutions. The advantage is the guaranteed solution. But the disadvantage of this approach is a problem called \u201cCombinatorial explosion\u201d where the increase in input is associated with the rapid increase in output.<\/p>\n<p>&nbsp;<\/p>\n<p>Let us discuss about applying brute force approach for some of the important problems now:<\/p>\n<\/div>\n<div style=\"text-align: justify\">\n<p><strong>Solution Space and Unintelligent Search techniques:<\/strong><\/p>\n<p style=\"text-align: justify\">The solution space is in the form of a graph. A sample solution space is shown in Fig. 2. Some of the important terminologies used in association with the solution space is given below:<\/p>\n<ol>\n<li style=\"text-align: justify\">Root: Root of a graph has no predecessor. In solution space, it is the initial configuration.<\/li>\n<li style=\"text-align: justify\">Solution Space: All the configurations in the form of a state space tree is called solution space. The target configuration is somewhere in the solution space.<\/li>\n<li style=\"text-align: justify\">Search techniques: Once a solution space is available, then the tree can be searched using search techniques like DFS and BFS.<\/li>\n<\/ol>\n<p>Let us review about DFS and BFS now:<\/p>\n<p>&nbsp;<\/p>\n<p class=\"hanging-indent\"><strong>DFS Search<\/strong><\/p>\n<p style=\"text-align: justify\">Depth First Search (DFS) is an unintelligent search that is used to search a graph. DFS uses a stack for traversing a graph. Initially, the root node is pushed onto a stack. Then, it is checked for goal node. If it is a goal node, then DFS reports success. Otherwise, its children is generated and pushed onto a stack. This procedure is repeated till stack is empty.<\/p>\n<p>&nbsp;<\/p>\n<p>The procedure of DFS is given below:<\/p>\n<p>&nbsp;<\/p>\n<p>Put the root node on a stack S;<\/p>\n<p>while (S is not empty) {<\/p>\n<p>remove a node from the S;<\/p>\n<p>if (node = goal node) return success;<\/p>\n<p>put all children of node onto the S;<\/p>\n<p>}<\/p>\n<p>&nbsp;<\/p>\n<p>return failure;<\/p>\n<p>&nbsp;<\/p>\n<p>The following example illustrates usage of DFS.<\/p>\n<\/div>\n<div style=\"text-align: justify\">\n<p style=\"text-align: justify\"><strong>Example 1: Assume goal nodes are N and J. Show the DFS search of the following graph shown in Fig. 1 for finding the goal nodes?<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-203\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M09Pic1-1.png\" alt=\"\" width=\"384\" height=\"423\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M09Pic1-1.png 384w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M09Pic1-1-272x300.png 272w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M09Pic1-1-65x72.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M09Pic1-1-225x248.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M09Pic1-1-350x386.png 350w\" sizes=\"auto, (max-width: 384px) 100vw, 384px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: center\"><strong>Fig 1: A sample Graph<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p class=\"hanging-indent\"><strong>Nodes that are explored in the order are ; A B D E L M N I O C F G J<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p class=\"hanging-indent\"><strong>BFS Search<\/strong><\/p>\n<p style=\"text-align: justify\">Breadth First Search (BFS) is also an unintelligent search that is used to search a graph. BFS traverse a graph level-by-level. It uses a queue data structure for traversing a graph. Initially, the root node is added onto a queue. Then, it is checked for goal node. If it is a goal node, then BFS reports success. Otherwise, its children is generated and pushed onto a rear end of the queue Q. This procedure is repeated till Queue is empty.<\/p>\n<\/div>\n<div style=\"text-align: justify\">\n<p><strong>The procedure of BFS is given below:<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>Put the root node on a queue Q;<\/p>\n<p>while (Q is not empty) {<\/p>\n<p>remove a node from the queue Q;<\/p>\n<p>if (node = goal node) return success;<\/p>\n<p>put all children of node onto the queue Q;<\/p>\n<p>}<\/p>\n<p>return failure;<\/p>\n<p>&nbsp;<\/p>\n<p>The following example illustrates usage of BFS.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>Example 2: Assume goal nodes are N and J. Show the BFS search of the following graph shown in Fig. 2 for finding the goal nodes?<\/strong><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-204\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M09Pic2.png\" alt=\"\" width=\"413\" height=\"415\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M09Pic2.png 413w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M09Pic2-150x150.png 150w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M09Pic2-300x300.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M09Pic2-65x65.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M09Pic2-225x226.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M09Pic2-350x352.png 350w\" sizes=\"auto, (max-width: 413px) 100vw, 413px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: center\"><strong>Fig 2: A sample Graph<\/strong><\/p>\n<\/div>\n<p style=\"text-align: justify\"><strong>\u00a0<\/strong><\/p>\n<div style=\"text-align: justify\">\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p class=\"hanging-indent\">The nodes that are explored in BFS order is :\u00a0 A B C D E F G H I J L M N O<\/p>\n<p>&nbsp;<\/p>\n<p class=\"hanging-indent\"><strong>15-Puzzle Problem<\/strong><\/p>\n<p style=\"text-align: justify\">In 1878, Sam Lloyd designed a puzzle called 15-puzzle game. It is a game where a initial and target configuration is given. The game is about moving tile so that the target configuration is reached from the initial configuration. In other words, the objective of the game is to change initial state to goal state. The possible configurations of moving the up, down, right or left using the empty tile. So a node can have at most possible four moves. A sample initial and target configuration is given below in Fig. 3.<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-205\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M09Pic3.png\" alt=\"\" width=\"267\" height=\"142\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M09Pic3.png 267w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M09Pic3-65x35.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M09Pic3-225x120.png 225w\" sizes=\"auto, (max-width: 267px) 100vw, 267px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: center\"><strong>Fig. 3. : Initial and Target configuration<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">A brute force algorithm can be written to generate the solution space. The repeated application of the legal moves, top, bottom, right and left results in a graph called state space or <strong>solution space<\/strong>. This is shown in Fig. 4.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-206\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M09Pic4.png\" alt=\"\" width=\"642\" height=\"237\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M09Pic4.png 642w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M09Pic4-300x111.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M09Pic4-65x24.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M09Pic4-225x83.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M09Pic4-350x129.png 350w\" sizes=\"auto, (max-width: 642px) 100vw, 642px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: center\">Fig. 4: <strong>Portion of a Graph<\/strong><strong style=\"text-align: justify;font-size: 1em\">\u00a0<\/strong><\/p>\n<\/div>\n<div style=\"text-align: justify\">\n<p style=\"text-align: justify\">The goal state may be present somewhere in the solution space. Now, Exhaustive search technique is about finding the path from the starting node to the goal state. This may be done using DFS or BFS.<\/p>\n<p>&nbsp;<\/p>\n<p class=\"hanging-indent\">Formal Algorithm<\/p>\n<p class=\"hanging-indent\">The formal algorithm based on [1] for 15-puzzle is given as follows:<\/p>\n<p>&nbsp;<\/p>\n<p>Algorithm 15puzzle (G, root, goal)<\/p>\n<p>%%\u00a0\u00a0 Input: State space tree with root and target goal state<\/p>\n<p>%%\u00a0\u00a0 Path from root to goal node<\/p>\n<p>Begin<\/p>\n<p>for all nodes make visit = 0<\/p>\n<p>%%\u00a0\u00a0 Let root be the starting node visited[root] = 1<\/p>\n<p>generate children w for root for all w do<\/p>\n<p>If (visited[w] = 0) and (w is not goal node) then call DFS(G,w)<\/p>\n<p>end if<\/p>\n<p>end for<\/p>\n<p>End<\/p>\n<p>&nbsp;<\/p>\n<p class=\"hanging-indent\"><strong>Complexity Analysis<\/strong><\/p>\n<p style=\"text-align: justify\">This brute force algorithm for 15-Puzzle game is inefficient and unrealistic. For 15-puzzle\u00a0\u00a0problem<span style=\"text-align: initial;font-size: 1em\">, there will be 16! (\u00bb 20.9 X 1012) different arrangements of tiles. Hence <\/span>searching\u00a0\u00a0<span style=\"text-align: initial;font-size: 1em\">for the solution takes exponential time.<\/span><\/p>\n<\/div>\n<div style=\"text-align: justify\">\n<p><strong>8-Queen Problem<\/strong><\/p>\n<p style=\"text-align: justify\">The problem of eight queens is that of placing 8 queens in a non-attacking position. The problem of 8-queen problem is to generate a board configuration where the queens are in non-attacking positions.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">The movement of queen is shown in Fig. 5. It can be observed that a queen can move in horizontal, vertical and diagonal ways.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-207\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M09Pic5.png\" alt=\"\" width=\"261\" height=\"254\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M09Pic5.png 261w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M09Pic5-65x63.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M09Pic5-225x219.png 225w\" sizes=\"auto, (max-width: 261px) 100vw, 261px\" \/><\/p>\n<p style=\"text-align: center\"><strong>Fig. 5: The movement of a Queen<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">The brute force algorithm would be to try all possible combinations to check out the placement of the queens such that they are in a non-attacking position.<\/p>\n<p>&nbsp;<\/p>\n<p>The informal algorithm is as follows:<\/p>\n<ol>\n<li>Try all combinations<\/li>\n<li>Check whether the queens are in attacking position<\/li>\n<li>Repeat steps 1 and 2 until a valid configuration is possible.<\/li>\n<\/ol>\n<\/div>\n<div style=\"text-align: justify\">\n<p>The formal algorithm based on [1] is given as follows:<\/p>\n<p>&nbsp;<\/p>\n<p>Algorithm 8queen(n)<\/p>\n<p>%% Input: A 8 x 8 chess board and \u20188\u2019 queens<\/p>\n<p>%%\u00a0\u00a0\u00a0\u00a0 <strong>Output<\/strong>: Solution of 8-queen problem Begin<strong>\u00a0<\/strong><\/p>\n<p>n = 8<strong>\u00a0<\/strong><\/p>\n<p>for i1 = 1 to n do for i2 = 1 to n do for i3 = 1 to n do for i4 = 1 to n do<strong>\u00a0<\/strong><\/p>\n<p>for i5 = 1 to n do for i6 = 1 to n do for i7 = 1 to n do for i8 = 1 to n do<\/p>\n<p>sol = [i1, i2, i3, i4, i5, i6, i7, i8]<\/p>\n<p>%%\u00a0\u00a0 check the solution with respect to constraints of<\/p>\n<p>%%\u00a0\u00a0 non-attacking queen<\/p>\n<p>if sol is correct then print sol<\/p>\n<p>End if<\/p>\n<p>End for<\/p>\n<p>End for<\/p>\n<p>End for<\/p>\n<p>End for<\/p>\n<p>End for<\/p>\n<p>End for<\/p>\n<p>End for<\/p>\n<p>End for<\/p>\n<p>End.<\/p>\n<p>&nbsp;<\/p>\n<p class=\"hanging-indent\"><strong>Complexity Analysis:<\/strong><\/p>\n<p style=\"text-align: justify\">Even though, the solution for 8-queen problem looks simple, in reality solution involves a\u00a0<span style=\"font-size: 1em;text-align: initial\">combination of\u00a0\u00a0<\/span><span style=\"text-align: initial;font-size: 1em\">64!<\/span><span style=\"text-align: initial;font-size: 1em\">56!\u00a0<\/span><span style=\"text-align: initial;font-size: 1em\">positions (56 = 64-8). This makes <\/span>exhaustive<span style=\"text-align: initial;font-size: 1em\"> search a difficult process.<\/span><\/p>\n<\/div>\n<p style=\"text-align: justify\"><span style=\"text-align: initial;font-size: 1em\">There are many solutions <\/span>for<span style=\"text-align: initial;font-size: 1em\"> the 8-queen problem.<\/span><\/p>\n<div style=\"text-align: justify\">\n<p><strong>Knapsack problem<\/strong><\/p>\n<p style=\"text-align: justify\">Knapsack problem is one of the most popular algorithms that we often encounter in our daily life. It was designed by Denzig in 1950. A Knapsack problem has a knapsack of capacity K.<\/p>\n<p style=\"text-align: justify\">There are n different items, each of which is associated with <em>W<\/em><em>i<\/em> and profit Pi (It is also called as value). The objective of knapsack problem is to load knapsack to maximize profit subjected to the capacity of knapsack.<\/p>\n<p>&nbsp;<\/p>\n<p class=\"hanging-indent\"><strong>Mathematical Formulation:<\/strong><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-208\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M09Pic6.png\" alt=\"\" width=\"402\" height=\"179\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M09Pic6.png 402w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M09Pic6-300x134.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M09Pic6-65x29.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M09Pic6-225x100.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M09Pic6-350x156.png 350w\" sizes=\"auto, (max-width: 402px) 100vw, 402px\" \/><\/p>\n<\/div>\n<div style=\"text-align: justify\">\n<p style=\"text-align: justify\">There are two types pf knapsack problem. It is easy to solve <strong>fractional knapsack problem.\u00a0<\/strong><strong>This problem allows loading of knapsack with fractional items. This is possible if the items to be loaded are like <\/strong>cloth, liquid, gold dust, etc. On the other hand, Integer knapsack problem, also known as 0\/1 knapsack, is hard to solve. This problem is applicable for items which can either be loaded full or not at all. The items here are like electronic items, machineries or any items that can be broken.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Let us consider a scenario where there are three bottles of Salt with their weights and profits as shown in Fig. 6.<\/p>\n<\/div>\n<div style=\"text-align: justify\">\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-209\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M09Pic7.png\" alt=\"\" width=\"1614\" height=\"1367\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M09Pic7.png 1614w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M09Pic7-300x254.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M09Pic7-768x650.png 768w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M09Pic7-1024x867.png 1024w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M09Pic7-65x55.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M09Pic7-225x191.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M09Pic7-350x296.png 350w\" sizes=\"auto, (max-width: 1614px) 100vw, 1614px\" \/><\/p>\n<p style=\"text-align: center\"><strong>Fig.6 : Knapsack problem<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">The bigger bottle is knapsack. The capacities and profits are are shown in Fig. 6. So the question here is how to fill the knapsack effectively so that profit is higher subjected to the capacity of the knapsack.<\/p>\n<\/div>\n<div style=\"text-align: justify\">\n<p><strong>Informal Algorithm:<\/strong><\/p>\n<ol>\n<li>Generate all possible sets. There will be 2<em>n<\/em>\u00a0 possible subsets for \u2018n\u2019 items.<\/li>\n<li>Generate a binary string of length<\/li>\n<li>If the binary bit is 1, then include, otherwise exclude the item subjected to the constraints.<\/li>\n<li>Compute the maximum profit and Weight for all combinations and report maximum profit.<\/li>\n<li>Exit.<\/li>\n<\/ol>\n<p><strong>Formal Algorithm:<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p class=\"hanging-indent\">Formally, the knapsack problem based on [1] is given as follows:<\/p>\n<p>&nbsp;<\/p>\n<p>Algorithm knapsack(K, w[1..n],p[1..n])<\/p>\n<p>%%\u00a0\u00a0 Input: Knapsack with capacity K , weights and profits<\/p>\n<p>%%\u00a0\u00a0 Output: Knapsack items and maximum weight and profit<\/p>\n<p>Begin<\/p>\n<p>globalprofit = 0<\/p>\n<p>choice = 0 index = 1<\/p>\n<p>while (index &lt;= 2n ) do\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 %% for all 2n subsets<\/p>\n<p>profit = 0<\/p>\n<p>weight = 0<\/p>\n<p>for i = 1 to n do\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 %% for all n items<\/p>\n<p>if (binary(index, i) == 0) \u00a0then\u00a0\u00a0\u00a0\u00a0 %% Item is excluded if binary bit is 0 profit = profit + 0<\/p>\n<p>weight = weight +0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 %% generate binary bit i for item index else profit = profit + p[i]\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 %% Update if Binary bit is 1<\/p>\n<p>weight = weight +w[i] End if<\/p>\n<p><span style=\"text-align: initial;text-indent: 1em;font-size: 1em\">End for<\/span><\/p>\n<p>if ((weight &lt;= K) and (profit &gt; globalprofit)) then %% Check the constraints globalprofit = profit<\/p>\n<p>choice = i\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 %% Note the combination<\/p>\n<p>End if<\/p>\n<p>index = index +1<\/p>\n<p>End while<\/p>\n<p>End<\/p>\n<\/div>\n<div style=\"text-align: justify\">\n<p>This is illustrated in Example 3.<\/p>\n<p class=\"hanging-indent\"><strong>Example 3: <\/strong>Consider three items. Generate all the possibilities:<\/p>\n<p>The possibilities are<\/p>\n<p>\u03c6<\/p>\n<p>{1}<\/p>\n<p>{2}<\/p>\n<p>{3}<\/p>\n<p>{1, 2}<\/p>\n<p>{1, 3}<\/p>\n<p>{2, 3}<\/p>\n<p>{1,2,3}<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Then all combinations are tried out subjected to the constraints. The profit is computed for every case and maximum profit is reported.<\/p>\n<p>&nbsp;<\/p>\n<p class=\"hanging-indent\"><strong>Complexity Analysis:<\/strong><\/p>\n<p style=\"text-align: justify\">This involves generation of 2\u00a0 n\u00a0 combinations. Hence, the complexity of the algorithm leads\u00a0\u00a0<span style=\"text-align: initial;text-indent: 1em;font-size: 1em\">to a \u038f (2n) algorithm. The implication of NP-hard is that it would be difficult to solve the problem.<\/span><\/p>\n<p>&nbsp;<\/p>\n<p class=\"hanging-indent\"><strong>Assignment Problem<\/strong><\/p>\n<p class=\"indent\" style=\"text-align: justify\"><span style=\"text-align: justify;font-size: 1em\">Assignment problem is to assign m persons to n jobs such that the cost is minimized. This problem can be solved using brute force approach. All possible combinations are tried out and cost is computed. Finally, the least cost assignment is reported.<\/span><\/p>\n<\/div>\n<div style=\"text-align: justify\">\n<p><strong>Informal Algorithm<\/strong><\/p>\n<p class=\"hanging-indent\">The informal algorithm is stated as below;<\/p>\n<ol>\n<li>Generate all permutation of assignments<\/li>\n<li>Compute the cost for all assignments<\/li>\n<li style=\"text-align: justify\">Choose the minimum cost assignment and report.<\/li>\n<li>End.<\/li>\n<\/ol>\n<p><strong>Formal Algorithm<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>The formal algorithm based on [1] is given below:<\/p>\n<p>Algorithm Assign(person[1..n],job[1..n])<\/p>\n<p>%%\u00a0\u00a0 Input; person and jobs<\/p>\n<p>%%\u00a0\u00a0 Output: Optimal assignment of person to job Begin<\/p>\n<p>permutate all legitimate assignments ai<\/p>\n<p>compute the assignment [a1, a2,.., an] whose cost is minimum assign as per minimum cost and return min_cost<\/p>\n<p>End<\/p>\n<p>&nbsp;<\/p>\n<p>The following Example 4 illustrates the application of this algorithm:<\/p>\n<p>&nbsp;<\/p>\n<p><strong>Example 4:<\/strong>\u00a0\u00a0\u00a0 A sample assignment Table in given in table 1.<\/p>\n<p>&nbsp;<\/p>\n<p>Table 1: Sample assignment Table<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-44 aligncenter\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/Untitled-9.png\" alt=\"\" width=\"549\" height=\"176\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/Untitled-9.png 549w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/Untitled-9-300x96.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/Untitled-9-65x21.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/Untitled-9-225x72.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/Untitled-9-350x112.png 350w\" sizes=\"auto, (max-width: 549px) 100vw, 549px\" \/><\/p>\n<p>Use assignment algorithm and find optimal cost?<\/p>\n<\/div>\n<div style=\"text-align: justify\">\n<p style=\"text-align: justify\">There are 3 persons and 3 jobs. The question is how to assign the jobs to persons in an optimal manner based on the cost matrix given above. For example, if a random assignment is made like assign the job 1 to person 1 (C(1,1)), job 2 to person 2 (C(2,2)) and job 3 to person 3(C(3,3)), then the cost of the assignment would be<\/p>\n<p>&nbsp;<\/p>\n<p>&lt; 1 2 3&gt;\u00a0\u00a0 =\u00a0\u00a0\u00a0 3 + 3 + 2 = 8<\/p>\n<p>&nbsp;<\/p>\n<p>For the above problem, all the possible cost assignments are given below in Table 2.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: center\"><strong>Table 2: Possible assignments<\/strong><\/p>\n<table style=\"height: 281px; width: 823px;\">\n<tbody>\n<tr>\n<td style=\"width: 100.063px\">J1<\/td>\n<td style=\"width: 114.063px\">J2<\/td>\n<td style=\"width: 114.063px\">J3<\/td>\n<td style=\"width: 438.063px\">Cost<\/td>\n<\/tr>\n<tr>\n<td style=\"width: 100.063px\">1<\/td>\n<td style=\"width: 114.063px\">2<\/td>\n<td style=\"width: 114.063px\">3<\/td>\n<td style=\"width: 438.063px\">3 + 3 + 2 = 8<\/td>\n<\/tr>\n<tr>\n<td style=\"width: 100.063px\">1<\/td>\n<td style=\"width: 114.063px\">3<\/td>\n<td style=\"width: 114.063px\">2<\/td>\n<td style=\"width: 438.063px\">3 + 7 + 9 = 19<\/td>\n<\/tr>\n<tr>\n<td style=\"width: 100.063px\">2<\/td>\n<td style=\"width: 114.063px\">1<\/td>\n<td style=\"width: 114.063px\">3<\/td>\n<td style=\"width: 438.063px\">4 + 2 + 2 = 8<\/td>\n<\/tr>\n<tr>\n<td style=\"width: 100.063px\">2<\/td>\n<td style=\"width: 114.063px\">3<\/td>\n<td style=\"width: 114.063px\">1<\/td>\n<td style=\"width: 438.063px\">4 + 7 + 8 = 19<\/td>\n<\/tr>\n<tr>\n<td style=\"width: 100.063px\">3<\/td>\n<td style=\"width: 114.063px\">1<\/td>\n<td style=\"width: 114.063px\">2<\/td>\n<td style=\"width: 438.063px\">5 + 2 + 9 = 16<\/td>\n<\/tr>\n<tr>\n<td style=\"width: 100.063px\">3<\/td>\n<td style=\"width: 114.063px\">2<\/td>\n<td style=\"width: 114.063px\">1<\/td>\n<td style=\"width: 438.063px\">5 + 3 + 8 = 16<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p style=\"text-align: justify\">It can be observed that the optimal order is &lt; 1 2 3&gt; and &lt;2 1 3&gt; as they are associated least cost.<\/p>\n<p>&nbsp;<\/p>\n<p class=\"hanging-indent\"><strong>Complexity Analysis<\/strong><\/p>\n<p style=\"text-align: justify\">Again, the complexity analysis shows that the number of permutations are n!. Therefore, the complexity of the problem is O(n!).<\/p>\n<p>&nbsp;<\/p>\n<p class=\"hanging-indent\"><strong>Summary<\/strong><\/p>\n<\/div>\n<p style=\"text-align: justify\">In short, one can conclude as part of this module 9 that<\/p>\n<ul style=\"text-align: justify\">\n<li>Brute force guarantee solutions but it is inefficient.<\/li>\n<li>It is difficult to solve combinatorial optimization problems.<\/li>\n<li>15 Puzzle, 8-Queen, Knapsack and assignment problems are optimization problem that can be solved using brute force method.<\/li>\n<\/ul>\n<p style=\"text-align: justify\"><strong>References:<\/strong><\/p>\n<ol>\n<li style=\"text-align: justify\">S.Sridhar \u2013 Design and Analysis of Algorithms, Oxford University Press, 2014.<\/li>\n<li style=\"text-align: justify\">A.Lvitin \u2013 Introduction to Design and Analysis of Algorithms, 2rd Edition, Pearson Education, 2014.<\/li>\n<li style=\"text-align: justify\">Cormen, T.H., C.E. Leiserson, and R.L. Rivest, Introduction to Algorithms, MIT Press, Cambridge, MA 1992.<\/li>\n<li style=\"text-align: justify\">URL: <a href=\"http:\/\/www.hbmeyer.de\/backtrack\/achtdamen\/eight.htm\">http:\/\/www.hbmeyer.de\/backtrack\/achtdamen\/eight.htm#up<\/a><\/li>\n<\/ol>\n","protected":false},"author":4,"menu_order":3,"template":"","meta":{"pb_show_title":"on","pb_short_title":"","pb_subtitle":"","pb_authors":["mr-s-sridhar"],"pb_section_license":""},"chapter-type":[],"contributor":[58],"license":[],"class_list":["post-35","chapter","type-chapter","status-publish","hentry","contributor-mr-s-sridhar"],"part":3,"_links":{"self":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/pressbooks\/v2\/chapters\/35","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/pressbooks\/v2\/chapters"}],"about":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/wp\/v2\/types\/chapter"}],"author":[{"embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/wp\/v2\/users\/4"}],"version-history":[{"count":5,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/pressbooks\/v2\/chapters\/35\/revisions"}],"predecessor-version":[{"id":210,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/pressbooks\/v2\/chapters\/35\/revisions\/210"}],"part":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/pressbooks\/v2\/parts\/3"}],"metadata":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/pressbooks\/v2\/chapters\/35\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/wp\/v2\/media?parent=35"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/pressbooks\/v2\/chapter-type?post=35"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/wp\/v2\/contributor?post=35"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/wp\/v2\/license?post=35"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}