5 5- 2 Outlines 5- 1 The Breadth-First Search 5-2 Depth-First Search 5-3 Hill Climbing 5-4 Best-First Search Strategy 5-5 The Branch-and-Bound Strategy 5-6 A Personnel Assignment Problem Solved by the Branch-and-Bound Strategy 5-7 The Traveling Salesperson Optimization Problem Solved by the Branch-and-Bound Strategy

Outlines:

5 5- 3 Outlines 5-8 The 0/1 Knapsack Problem Solved by the Branch-and-Bound Strategy 5-9 A Job Scheduling Problem Solved by the Branch-and-Bound Approach 5-10 The A* Algorithm 5-11 A Channel Routing Problem Solved by a Specialized A* Algorithm 5-12 The Linear Block Code Decoding Problem Solved by the A*Algorithm

Introduction:

5 5- 4 Introduction In this chapter, we shall show that the solutions of many problems may be represented by trees and therefore the solving of these problems becomes a tree searching problem. Satisfiability problem : Given a set of clauses , one method of determining whether this set of clauses are satisfiable is to examine all possible assignments. That is, if then are n variables x 1 , x 2 , ... , x n , then we simply examine all 2 n possible assignment. In each assignment, x i is assigned either T or F.

Satisfiability problem :

5 5- 5 Satisfiability problem Tree representation of 8 assignments. If there are n variables x 1 , x 2 , …,x n , then there are 2 n possible assignments.

Slide 6:

5 5- 6 An instance (a set of clauses): -x 1 …… .. …… (1) x 1 ………… ..(2) x 2 v x 5 … . … .(3) x 3 …… . …… .(4) -x 2 …… . …… .(5) A partial tree to determine the satisfiability problem. We may not need to examine all possible assignments .

8-Puzzle Problem:

5 5- 7 8-Puzzle Problem We show a square frame which can hold 9 items. However, only 8 items exist and therefore there is an empty spot. Our problem is to move these numbered tiles around so that the final state is reached. The numbered tiles can be moved only horizontally or vertically to the empty spot.

Initial &Goal:

5 5- 8 Initial &Goal

Possible Moves:

5 5- 9 Possible Moves

Hamiltonian circuit problem:

5 5- 10 Hamiltonian circuit problem Given a graph G=(V,E) which is a connected graph with n vertices, a Hamiltonian circuit is a round trip path along n edges of G which visits every vertex once and returns to its starting position.

Example :

5 5- 11 Example

Slide 12:

5 5- 12 The tree representation of whether there exists a Hamiltonian circuit. goal goal

Slide 13:

5 5- 13

5.1 Breadth-first search (BFS) :

5 5- 14 5.1 B readth-first search (BFS) 8-puzzle problem The breadth-first search uses a queue to holds all expanded nodes.

Breadth-First Search:

5 5- 15 Breadth-First Search Step 1. Form a one-element queue consisting of the root node. Step 2. Test to see if the first element in the queue is a goal node. If it is, stop. Otherwise, go to Step 3. Step 3. Remove the first element from the queue. Add the first element's descendants, if any, to the end of the queue. Step 4. If the queue is empty. then failure. Otherwise, go to Step 2.

5-2. Depth-first search (DFS):

5 5- 16 5-2. Depth-first search (DFS) e.g. sum of subset problem S={7, 5, 1, 2, 10} S ’ S sum of S ’ = 9 ? A stack can be used to guide the depth-first search. A sum of subset problem solved by depth-first search.

DFS-tree for Hamiltonian cycle:

5 5- 17 DFS-tree for Hamiltonian cycle

DFS (Depth-First Search):

5 5- 18 DFS ( Depth-First Search) Step 1. Form a one-element stack consisting of the root node. Step 2. Test to see if the top element in the stack is a goal node. If it is, then stop: otherwise, go to Step 3. Step 3 . Remove the top element from the stack and add the first elements descendants, if any, to the top of the stack. Step 4. If the stack is empty, then failure. Otherwise, go to Step 2.

5-3 Hill climbing :

5 5- 19 5-3 Hill climbing Among all the descendants, which node should be selected by us to expand? Hill climbing is a variant of depth-first search in which some greedy method is used to help us decide which direction to move in the search space. Usually, the greedy method uses some heuristics measure to order the choices. And, the better the heuristics, the better the hill climbing is .

Hill Climbing:

5 5- 20 Hill Climbing A variant of depth-first search The method selects the locally optimal node to expand. e.g. 8-puzzle problem evaluation function f(n) = d(n) + w(n) where d(n) is the depth of node n w(n) is # of misplaced tiles in node n.

Scheme of Hill Climbing:

5 5- 21 Scheme of Hill Climbing Step 1. Form a one-element stack consisting of the root node. Step 2. Test to see if the top element in the stack is a goal node. If it is. Stop: otherwise, go to Step 3. Step 3. Remove the top element from the stack and expand the element. Add the descendants of the element into the stack ordered by the evaluation function. Step 4. If the list is empty. failure. Otherwise, go to Step 2.

Slide 22:

5 5- 22 An 8-puzzle problem solved by a hill climbing method.

5-4 Best-first search strategy :

5 5- 23 5-4 Best-first search strategy Combing depth-first search and breadth-first search. Selecting the node with the best estimated cost among all nodes. This method has a global view.

5.4 Best-First Search Scheme :

5 5- 24 5.4 Best-First Search Scheme Step1: Construct a heap by using the evaluation function. First, form a 1-element heap consisting of the root node. Step2: Test to see if the root element in the heap is a goal node. If it is, stop; otherwise, go to Step 3. Step3: Remove the root element from the heap and expand the element. Add the descendants of the element into the heap. Step4: If the heap is empty, then failure. Otherwise, go to Step 2.

Slide 25:

5 5- 25 An 8-puzzle problem solved by a best-first search scheme .

5-5 Branch-and-bound strategy :

5 5- 26 5-5 Branch-and-bound strategy This strategy can be used to efficiently solve optimization problems . One of the most efficient strategies to solve a large combinatorial problem. Basically, it suggests that a problem may have feasible solutions. However, one should try to cut down the solution space by finding out that many feasible solutions can not be optimal solutions. e.g. A multi-stage graph searching problem.

Example -exhaustive search:

5 5- 27 Example -exhaustive search

Hill climbing:

5 5- 28 Hill climbing 5 X X X X

Slide 29:

5 5- 29 Solved by branch-and-bound

Branch & Bound:

5 5- 30 Branch & Bound This strategy consists of two important mechanisms: A mechanism to generate branchings and a mechanism to generate a bound so that many branchings can be terminated. Although the branch-and-bound strategy is usually very efficient. in worst cases, a very large tree may still be generated. Thus, we must realize that the branch-and-bound strategy is efficient in the sense of average cases.

5.6 Personnel assignment problem :

5 5- 31 5.6 Personnel assignment problem A linearly ordered set of persons P={P 1 , P 2 , … , P n } where P 1 <P 2 < … <P n A partially ordered set of jobs J={J 1 , J 2 , … , J n } Suppose that P i and P j are assigned to jobs f(P i ) and f(P j ) respectively. If f(P i ) f(P j ), then P i P j . If f(P i ) f(P j ), then f(P i ) f(P j ). Cost C ij is the cost of assigning P i to J j . We want to find a feasible assignment with the minimum cost. i.e. X ij = 1 if P i is assigned to J j X ij = 0 otherwise. Minimize i,j C ij X ij

topological sorting:

5 5- 32 topological sorting For a n partial ordering set S, a linear sequence S 1 , S 2 , ... , S n , is topologically sorted respect to S if S i < S j in the partial ordering implies that S i is located before S j in the sequence. topologically sorted sequence is 1, 3, 7, 4, 9, 2, 5, 8, 6.

A feasible assignment:

5 5- 33 A feasible assignment Let P 1 J k1 , P 2 J k2 , … , P n J kn , be a feasible assignment . According to our problem definition, the jobs are partially ordered and persons are linearly ordered. Therefore, J k1 , J k2 , … , J kn must be a topologically sorted sequence with respect to the partial ordering of jobs. Let us illustrate our idea by an example. Consider J = {J 1 , J 2 , J 3 , J 4 } and P = {P 1 , P 2 , P 3 , P 4 }.

Slide 34:

5 5- 34 e.g. A partial ordering of jobs After topological sorting, one of the following topologically sorted sequences will be generated: One of feasible assignments: P 1 → J 1 , P 2 → J 2 , P 3 → J 3 , P 4 → J 4 J 1 J 2 ↓ ↘ ↓ J 3 J 4 J 1 , J 2 , J 3 , J 4 J 1 , J 2 , J 4 , J 3 J 1 , J 3 , J 2 , J 4 J 2 , J 1 , J 3 , J 4 J 2 , J 1 , J 4 J 3

A solution tree:

5 5- 35 A solution tree All possible solutions can be represented by a solution tree.

Tree generated Steps (topology sorted order):

5 5- 36 Tree generated Steps (topology sorted order) Take an element which is not preceded by any other element in the partial ordering. Select this element as an element in a topologically sorted sequence. Remove this element just selected from the partial ordering set. The resulting set is still partially ordered.

5 5- 38 Cost matrix Jobs Persons 1 2 3 4 1 29 19 17 12 2 32 30 26 28 3 3 21 7 9 4 18 13 10 15 Reduced cost matrix to find lower bound (LB) Jobs Persons 1 2 3 4 1 17 4 5 0 (-12) 2 6 1 0 2 (-26) 3 0 15 4 6 (-3) 4 8 0 0 5 (-10) (-3) Reduced cost matrix Lower bound: least cost we need to find the solution. No solution can have a cost lower than LB. A higher LB will lead to an earlier termination.

Slide 39:

5 5- 39 A reduced cost matrix can be obtained: subtract a constant from each row and each column respectively such that each row and each column contains at least one zero. Total cost subtracted: 12+26+3+10+3 = 54 This is a lower bound of our solution.

Branch-and-bound for the personnel assignment problem:

5 5- 40 Branch-and-bound for the personnel assignment problem Bounding of sub-solutions: solution

5.7 The traveling salesperson optimization problem:

5 5- 41 The basic principle of using the branch-and-bound strategy to solve the traveling salesperson optimization problem (TSP) consists of two parts. There is a way to split the solution space. There is a way to predict a lower bound for a class of solutions. There is also a way to find an upper bound of an optimal solution. If the lower bound of a solution exceeds this upper bound, this solution cannot be optimal. Thus, we should terminate the branching associated with this solution. 5.7 The traveling salesperson optimization problem

5 5- 43 Our branch-and-bound strategy splits a solution into two groups: one group including a particular arc and the other excluding this arc . Each splitting incurs a lower bound and we shall traverse the searching tree with the "lower" lower bound. If a constant subtracted from any row or any column of the cost matrix, an optimal solution does not change. B&B for TSP

5 5- 45 Another reduced matrix j i 1 2 3 4 5 6 7 1 ∞ 0 83 9 30 6 50 2 0 ∞ 66 37 17 12 26 3 29 1 ∞ 19 0 12 5 4 32 83 66 ∞ 49 0 80 5 3 21 56 7 ∞ 0 28 6 0 85 8 42 89 ∞ 0 7 18 0 0 0 58 13 ∞ (-7) (-1) (-4) Total cost reduced: 84+7+1+4 = 96 (lower bound) Arc 4-6 will cause the largest increase of lower bound. The larger LB the searching will terminate easier Minimal cost not use 4-6 6 12 1 32 3 0 0

Slide 46:

5 5- 46 The highest level of a decision tree: Why use 4-6? LB for include 4-6? LB for exclude 4-6? If we use arc 3-5 to split, the difference on the lower bounds is 17+1 = 18. TREE for TSP

Slide 47:

5 5- 47 A reduced cost matrix if arc (4,6) is included in the solution. Arc (6,4) is changed to be infinity since it can not be included in the solution and set to . No zero can be reduced

5 5- 49 A branch-and-bound solution of a traveling salesperson problem. 2-1 2-1

Slide 50:

5 5- 50 In general, if paths i 1 -i 2 - … -i m and j 1 -j 2 - … -j n have already been included and a path from i m , to j 1 is to be added, then path from j n to i 1 must be prevented .

5.8 The 0/1 knapsack problem :

5 5- 51 5.8 The 0/1 knapsack problem Positive integer P 1 , P 2 , … , P n (profit) W 1 , W 2 , … , W n (weight) M (capacity) Maximization problem Minimization problem

Branching mechanism:

5 5- 52 Branching mechanism

B&B process:

5 5- 53 B&B process We split solutions into two groups. For each group, a lower bound is found. At the same time, we try to search for a feasible solution. Whenever a feasible solution is found, an upper bound is found . Our branch-and-bound strategy terminates the expansion of a node if and only if one of the following conditions is satisfied: (1) The node itself represents an infeasible solution . Then no further expansion makes any sense. (2) The lower bound of this node is higher than or equal to the presently found lowest upper bound .

Improvement for 0/1-Knapsack:

5 5- 54 Improvement for 0/1-Knapsack For each group, not only a lower bound is found, but also an upper hound is found by finding a feasible solution . As we expand a node, we hope to find a solution with lower cost. This means that we wish to find a lower upper bound as we expand a node. If we know that our upper bound cannot be lowered because it is already equal to its lower bound, then we should not expand this node any more. In general, we terminate the branching if and only if one of the following conditions is satisfied: The node itself represents an infeasible solution. The lower bound of this node is higher than or equal to the presently found lowest upper bound. The lower bound of this node is equal to the upper bound of this node.

How to find an upper bound and a lower bound?:

5 5- 55 How to find an upper bound and a lower bound? Lower bound can be considered as the value of best solution you can achieve. A lower bound of this node therefore corresponds to highest possible profit associated with this partial constructed solution. Upper bound : the cost of a feasible solution corresponding to this partially constructed solution.

Find upper bound:

5 5- 56 e.g. n = 6, M = 34 A feasible solution can be found by staring from the smallest available i , scanning towards the larger i ’ s until M is exceeded. A feasible solution: X 1 = 1, X 2 = 1, X 3 = 0, X 4 = 0, X 5 = 0, X 6 = 0 -(P 1 +P 2 ) = -16 ( upper bound ) Any solution higher than -16 can not be an optimal solution. i 1 2 3 4 5 6 P i 6 10 4 5 6 4 W i 10 19 8 10 12 8 (P i /W i P i+1 /W i+1 for i=1, 2, …, 6 sorting ) Find upper bound

Find lower bound by relaxing the restriction:

5 5- 57 Find lower bound by relaxing the restriction X i is restricted to 0 an 1. Relax our restriction from X i = 0 or 1 to 0 X i 1 (knapsack problem) 0/1 knapsack problem -> knapsack problem (greedy method) Defined as : Positive integer P 1 , P 2 , … , P n (profit) W 1 , W 2 , … , W n (weight) M (capacity)

Relax the restriction to find lower bound:

5 5- 58 Relax the restriction to find lower bound X i is restricted to 0 an 1. Relax our restriction from X i = 0 or 1 to 0 X i 1 (knapsack problem)

Upper bound and lower bound:

5 5- 59 Upper bound and lower bound We can use the greedy method to find an optimal solution for knapsack problem: X 1 = 1, X 2 =1, X 3 = 5/8 , X 4 = 0, X 5 = 0, X 6 =0 -(P 1 +P 2 +5/8P 3 ) = -18.5 (lower bound) -18 is our lower bound. (only consider integers) -18 optimal solution -16 optimal solution : X 1 = 1, X 2 = 0, X 3 = 0, X 4 = 1, X 5 = 1, X 6 = 0 -(P 1 +P 4 +P 5 ) = -17

Slide 60:

5 5- 60 0/1 knapsack problem solved by branch-and-bound strategy. Expand the node with the best lower bound.

5-9 A Job Scheduling Problem Solved by the Branch-and Bound Approach (skip):

5 5- 61 5-9 A Job Scheduling Problem Solved by the Branch-and Bound Approach ( skip ) Assumptions: All the processors are identical and any job can be executed on any processor. There is a partial ordering of jobs. A job cannot be executed if one of its ancestor jobs, if it exists, has not been executed yet. Whenever a processor is idle and a job is available, this processor must start working on the job. Each job takes equal time for execution. A time profile is given which specifies the number of processors that can be used simultaneously in each time slot. The object of the scheduling is to minimize the maximum completion time , which is the time slot in which the last job is finished.

Example:

5 5- 62 Example

Solution 1:

5 5- 63 Solution 1

Solution 2:

5 5- 64 Solution 2

Slide 65:

5 5- 65

Slide 66:

5 5- 66

Slide 67:

5 5- 67

Slide 68:

5 5- 68

Slide 69:

5 5- 69

Slide 70:

5 5- 70

Slide 71:

5 5- 71

Slide 72:

5 5- 72

5-10 The A* algorithm :

5 5- 73 5-10 The A * algorithm Used to solve optimization problems. Using the best-first strategy. If a feasible solution (goal node) is obtained, then it is optimal and we can stop . Cost function of node n : f(n) f(n) = g(n) + h(n) g(n): cost from root to node n. h(n): estimated cost from node n to a goal node. h * (n): “ real ” cost from node n to a goal node. If we guarantee h(n) h*(n), then f(n) = g(n) + h(n) g(n)+h * (n) = f * (n)

Dominance rule for A*:

5 5- 74 Dominance rule for A* Find shortest path for S to T. Ignore S-V 2 -V 3 and S-V 1 -V 2

An example for A* algorithm:

5 5- 75 An example for A * algorithm A Graph to Illustrate A * Algorithm. Stop iff the selected node is also a goal node.

Slide 76:

5 5- 76 Step 1: V 1 V 3 V 2

Slide 77:

5 5- 77 Step 2: Expand node A. V 2 V 2 V 4 V 1 目前： f(C)=5, f(B)=6

Slide 78:

5 5- 78 Step 3: Expand node C. V 4 V 5 V 2 目前： f(B)=6, f(E)=7,

5 5- 81 Step 6: Expand node F. Node I is a goal node. Thus, the final solution has been obtained.

5-11 A* algorithm for the channel routing problem:

5 5- 82 5-11 A* algorithm for the channel routing problem Application on CAD. For the channel routing problem, as soon as a goal node is found, then the A* algorithm can be stopped and return a optimal solution . (not true for other problem) Whenever a node t is selected and produces a goal node as its immediate successor, then h(t)=h*(t)=0=f*(t). G(goal)=f(goal)=f*(t)

Slide 83:

5 5- 83

5-11The channel routing problem :

5 5- 84 5-11The channel routing problem A Channel Specification 8 nets Connections are fixed

Slide 85:

5 5- 85 Illegal wirings : We want to find a routing which minimizes the number of tracks .

A feasible routing:

5 5- 86 A feasible routing 7 tracks are needed.

An optimal routing:

5 5- 87 An optimal routing 4 tracks are needed. This problem is NP-complete .

A* algorithm for the channel routing problem:

5 5- 88 A* algorithm for the channel routing problem Horizontal constraint graph (HCG) e.g. net 8 must be to the left of net 1 and net 2 if they are in the same track. e.g. net 7 must be to the left of net 3, net 5 , and net 6 if they are in the same track.

Vertical constraint:

5 5- 89 Vertical constraint Eg. Net 1 must be realized before 2 as they share the same terminal 11. Vertical constraint graph:

Slide 90:

5 5- 90 Vertical constraint graph define a partial ordering , only those nets without predecessors in the vertical constraint graph can be assigned to a track. Horizontal constraint graph informs us which nets can be assigned to a track.

Slide 91:

5 5- 91 Maximum cliques in HCG: {1,8}, {1,3,7}, {5,7}. Each maximum clique can be assigned to a track. Clique : a clique of a graph is a subgraph in which every pair of vertices are connected. Maximal clique : is a clique who size cannot be made larger ( largest complete subgraph ). Theorem: each maximal clique can be assigned to a track .

Slide 92:

5 5- 92 Expand {7, 3, 1} After (7, 3, 1) are assigned the nets which can be assigned become {2, 4, 5, 8}. Possible cliques are {2,4}{2,8} {5}

Local density of point I:

5 5- 93 Local density of point I For the terminal i, draw a vertical line, if this vertical line intersects k horizontal lines, then the minimum number of tracks is k.

cost:

5 5- 94 cost f(n) = g(n) + h(n), g(n): the level of the tree (used to represent the number of tracks ) h(n): maximal local density , that is the maximum number of tracks which must be used after a certain number of tracks have been assigned. H(t)=h*(t)=1=g(goal)-g(t). A partial solution tree for the channel routing problem by using A * algorithm.

You do not have the permission to view this presentation. In order to view it, please
contact the author of the presentation.

Send to Blogs and Networks

Processing ....

Premium member

Use HTTPs

HTTPS (Hypertext Transfer Protocol Secure) is a protocol used by Web servers to transfer and display Web content securely. Most web browsers block content or generate a “mixed content” warning when users access web pages via HTTPS that contain embedded content loaded via HTTP. To prevent users from facing this, Use HTTPS option.