Chapter 1 Introduction

Size: px

Start display at page:

Download "Chapter 1 Introduction"

惇谓麴
5 years ago
Views:

1 Chapter 9 Branch-and-Bound and Backtracking C.K. Liang al-09 Branch-and-Bound

2 Introduction Graph: Graphs are a pervasive data structure in computer science, and algorithms for working with graphs are fundamental to the computer science Goal of this chapter: Show how can we represent a graph on a computer Discuss algorithms based on searching a graph using either breadth-first search or depth-first search Discuss the problem of computing shortest paths between vertices Show how to compute a maximum flow of material in a network C.K. Liang al-09 Branch-and-Bound

3 Representations of graphs How to represent a graph: G=(V,E) Adjacency-matrix : dense graphs Adjacency-list : sparse graphs Example 5 4 Adjacency-matrix Adjacency-list C.K. Liang al-09 Branch-and-Bound

4 Representation of problem Example: 8-puzzle problem State : node Action : edge Goal: Find a path from initial state to final state Representation by graph: C.K. Liang al-09 Branch-and-Bound 4

5 Representation of problem C.K. Liang al-09 Branch-and-Bound 5

6 Hamiltonian circuit problem C.K. Liang al-09 Branch-and-Bound 6

7 Hamiltonian circuit problem C.K. Liang al-09 Branch-and-Bound 7

8 Searching on a graph Breadth-first search: Given a graph G=(V,E) and a source vertex s, breadth-first search explores the edges of G to discover every vertex that is reachable from s. Breadth-first search discovers all vertices at distance k from s before discovering any vertex at distance k+. Breadth-first search tree: a tree with root s that contains all reachable vertices by breadth-first search approach. Steps:. Form a queue consisting of the root node.. Test to see if the first elements in the queue is a goal node. If it is, stop. Otherwise, go to step.. Remove first element from queue. Add the first element descendants, if any, to end of queue. 4. If queue is empty, then failure else go to. Time :O(V + E) C.K. Liang al-09 Branch-and-Bound 8

9 Breadth-first search C.K. Liang al-09 Branch-and-Bound 9

10 Depth-first search Depth-first search: In depth-first search, edges are explored out of the most recently discovered vertex v that still has unexplored edges leaving it. When all of v s edges have been explored, the search backtracks to explore edges leaving the vertex from which v was discovered. This process continues until we have discovered all the vertices that are reachable from the source vertex. Steps:. Form a stack consisting of the root node.. Test to see if the top elements in the stack is a goal node. If it is, stop. Otherwise, go to step.. Remove the top element from stack. Add the first element descendants, if any, to the top of the stack. 4. If the stack is empty, then failure. Otherwise, go to step. Time : O(V + E) C.K. Liang al-09 Branch-and-Bound 0

11 Depth-first search C.K. Liang al-09 Branch-and-Bound

12 0/ Knapsack Problem P = (40,0,50,0) W = (, 5, 0, 5) Use binary tree to represent the decision process (state space tree) Use DFS to find the optimal solution Use BFS to find the optimal solution C.K. Liang al-09 Branch-and-Bound

13 Backtracking Backtracking: A procedure that after determining that a node can lead to nothing but dead end, we go back to the node s parent and proceed with the search on the next child Consists on doing a depth-first search of a state space tree, checking whether each node is promising, and, if it is nonpromising, backtracking to the node s parent. Nonpromising node: A node that cannot possibly lead to a solution Promising node: Otherwise C.K. Liang al-09 Branch-and-Bound

14 4-Queen Problem 4 queens are placed into a 4-by-4 chessboard No two queens may be in the same row, column, or diagonal. Use tree to represent the state space Use (i,j) to represent the state of a node, where (i,j) means that the queen in the i-th row is placed in the j-th column The tree will have 56 leaves Use backtracking to find the solution C.K. Liang al-09 Branch-and-Bound 4

15 Sum-of-Subset Problem Example N =, W = 6 w =, w = 4, w = 5 Use tree to represent the state space Use backtracking to find the solution Example : (do it by yourself!!) N = 4, W = w =, w = 4, w = 5, w4 = 6 C.K. Liang al-09 Branch-and-Bound 5

16 Hill-climbing Question: Among all the descendants, which node should be selected by us to expand? Solution: 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. The better the heuristics, the better the hill climbing is. C.K. Liang al-09 Branch-and-Bound 6

17 Hill-climbing Example: 8-puzzle problem f(n)=d(n)+w(n) d(n):depth of node n in the search tree w(n): number of misplaced tiles in node n 8 4 starting node => f(n) = 0 + = C.K. Liang al-09 Branch-and-Bound 7

18 Hill-climbing C.K. Liang al-09 Branch-and-Bound 8

19 Best-first search Best-first search: Best-first search strategy is a way of combining the advantages of both depth-first and breadth-first search into a single method. Steps:. Form a list consisting of the root node.. Remove the first element from the list. Expand the first element. If one of the descendants of the first element is a goal node, then stop. Otherwise, add the descendants into the list.. Sort the entire list by the values of some estimation function. 4. If the list is empty, then failure. Otherwise, go to step. C.K. Liang al-09 Branch-and-Bound 9

20 Best-first search C.K. Liang al-09 Branch-and-Bound 0

21 Branch-and-bound Branch-and-bound strategy: One of the most efficient strategies to solve a large combinatorial problem. Example: Find a shortest path from S to T. A 5 4 D 4 S B E T C 7 F C.K. Liang al-09 Branch-and-Bound

22 Branch-and-bound S A B C 5 S A B C D F D F D E E F T T T C.K. Liang al-09 Branch-and-Bound

23 Branch-and-bound The assignment problem: Cost matrix 4 A B C A B C D Possible upper bound : 7 Possible upper bound : 87 (no good) Possible lower bound : 58 Possible lower bound : 49 ( no good) C.K. Liang al-09 Branch-and-Bound

24 Branch-and-bound The assignment problem: Cost matrix 4 A-> 60 A B C D A-> A-> Possible upper bound : 7 Possible lower bound : 58 A->4 78* C.K. Liang al-09 Branch-and-Bound 4

25 Branch-and-bound The assignment problem: Cost matrix A-> 60 A->, B-> 68 A-> A->, B-> 59 A-> 65 A->, B->4 64 A->4 78* C.K. Liang al-09 Branch-and-Bound 5

26 Branch-and-bound The assignment problem: Cost matrix A-> 60 A->, B-> 68* A->,B->,C->,D->4 64 A-> A->, B-> A->,B->,C->4,D-> 65* A-> 65* A->, B->4 64* A->4 78* C.K. Liang al-09 Branch-and-Bound 6

27 Branch-and-bound The assignment problem: Cost matrix A->, B-> 68* A->,B->,C->,D->4 69* A-> A->, B-> A->, B->4 66* A->,B->,C->4,D-> 6 C.K. Liang al-09 Branch-and-Bound 7

28 Branch-and-bound Exercise Cost matrix 4 A B C D C.K. Liang al-09 Branch-and-Bound 8

29 Branch-and-bound The Traveling Salesperson Problem V V V V4 V5 V V V V V [] [,] [,] [,4] 0 [,5] 4 C.K. Liang al-09 Branch-and-Bound 9

30 補充

31 補 : n- 皇后問題所謂 n 皇后問題是指如何將 n 顆西洋棋中的皇后棋子擺放在一個具有 n 列 n 行的棋盤中, 但是這 n 顆棋子彼此不會吃掉對方, 也就是這 n 顆皇后棋子彼此不允許在同一列同一行或是同一個對角線以下是四皇后問題示例 :

32 利用暴力式的直覺作法, 可能有下列兩種解題方法 : 作法 : n 個皇后需放置於不同列上, 並且檢查每個皇后在其所屬之列上的哪一個行才是其應放置的位置第一列可擺放的位置有 n 個, 第二列可擺放的位置有 n 個, 第三列可擺放的位置有 n 個,, 第 n 列可擺放的位置有 n 個 n n n n = n n 作法 : n 個皇后需放置於不同列不同行之位置上且除了與先前擺放之皇后的同行位置外, 需檢查每個皇后在其所屬之列上的哪一個行才是其應放置的位置第一列可擺放的位置有 n 個, 第二列可擺放的位置有 n- 個, 第三列可擺放的位置有 n- 個,, 第 n 列可擺放的位置有個 n (n-) (n-) = n! 以暴力法來解決 n 皇后問題, 似乎採用作法較為明智!!

33 以四皇后問題為例, 上述兩種暴力作法之解答空間為 : [ 作法 ] 4 4 = = 56 個可能解 [ 作法 ] 4! = 4 = 4 個可能解因此,n- 皇后問題屬於排列問題 ( 採用暴力法 )

34 四皇后問題的狀態空間樹 : 假設 x i 表示在第 i 列的皇后棋子所在之行位置 ( 課本上是以 col(i) 表示 x i ), 其中 i = ~n X 4 X X X

35 如何判斷兩個皇后間是否互吃假設 Q 皇后所在的位置是 (a, x a ),Q 皇后所在的位置是 (b, x b ), 下列位置皆會造成兩皇后互吃如果 b = a, 則表示 Q 皇后和 Q 皇后在同一列如果 x b = x a, 則表示 Q 皇后和 Q 皇后在同一行如果 (x b - x a ) = b a, 則表示 Q 皇后和 Q 皇后皆在右斜 45 o 線如果 (x b - x a ) = -(b a), 則表示 Q 皇后和 Q 皇后皆在左斜 45 o 線

36 利用回溯法解 4 皇后問題 4 皇后問題的狀態空間樹如下 : 邊界函數為前面四個互吃之判斷條件 ( ) ( ) 9

38 四皇后問題的解答

ENGG1410-F Tutorial 6

ENGG1410-F Tutorial 6 Jianwen Zhao Department of Computer Science and Engineering The Chinese University of Hong Kong 1/16 Problem 1. Matrix Diagonalization Diagonalize the following matrix: A = [ ] 1 2 4 3 2/16 Solution The