Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 9 đến 10 - Hồ Sĩ Đàm

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 9 đến 10 - Hồ Sĩ Đàm

1. CHƯƠNG IX: ĐỒ THỊ 1. Định nghĩa 2. Các khái niệm 3. Biểu diễn đồ thị trong máy tính 4. Các thuật toán tìm kiếm trên đồ thị 5. Bài toán tìm đường đi ngắn nhất 6. Bài toán cây khung 7. Tính liên thông của đồ thị
2. 1. Định nghĩa ◼ Là một cấu trúc rời rạc G= V là tập các đỉnh ( vertices) E là tập các cạnh ( Edges) - tập các cặp (u,v) mà u,v là hai đỉnh thuộc V.
3. 1. Định nghĩa ◼ Dựa vào đặc tính của tập E: G là đơn đồ thị nếu giữ hai đỉnh u và v bất kì có nhiều nhất một cạnh G là đa đồ thị nếu giữ hai đỉnh u và v bất kì có thể có nhiều hơn một cạnh
4. 1. Định nghĩa G-undirected graph nếu (u,v)=(v,u). G-directed graph nếu (u,v)<>(v,u), gọi là các cung.
5. 1. Định nghĩa Hình A Hình B Hình C Hình D ◼ Hình A: Đơn đồ thị, vô hướng ◼ Hình B: Đơn đồ thị, có hướng ◼ Hình C: Đa đồ thị, vô hướng ◼ Hình D: Đa đồ thị, có hướng
6. 2. Các khái niệm a) Cạnh liên thuộc, đỉnh kề, bậc Nếu e=(u,v) thì u,v kề nhau (adjacent) và e là liên thuộc với u và v Nếu e là một cung thì ta nói u nối tới v và v nối từ u. Cung e đi ra khỏi đỉnh u ( đỉnh đầu) và đi vào đỉnh v ( đỉnh cuối). Bậc (degree) của v ( deg(v)) là số cạnh liên thuộc với v.
7. 2. Các khái niệm Ví dụ 2 3 2 3 1 1 4 4 4 6 5 5 6
8. 2. Các khái niệm b) Đường đi và chu trình Một đường đi P=( v1 vp) mà cạnh vi-1vi thuộc E với mọi i 1<=i<=p). P gọi là đơn giản nếu tất cả các đỉnh trên đường đi đều phân biệt.
9. 2. Các khái niệm Một đường đi con của P là một đoạn liên tục dọc theo P. P gọi là đơn giản nếu tất cả các đỉnh đều là phân biệt. P gọi là chu trình (circuit) nếu v1=vp Một đồ thị vô hướng gọi là liên thông (connected) nếu với mọi cặp đỉnh (u,v) đều có u đến được v.
10. 3. Biểu diễn đồ thị trong máy tính a) Ma trận kề ◼ Đánh số thứ tự các đỉnh của đồ thị từ 1 đến n → biểu diễn đồ thị bằng một ma trận vuông cấp n gọi là ma trận kề: a[i,j]=1 nếu i, j là cạnh thuộc E. a[i,j]=0 nếu i, j là cạnh không thuộc E.
11. ◼ Các tính chất của ma trận kề: Đối với đồ thhị vô hướng thì ma trận kề là đối xứng (a[i,j]=a[j,i]). Tổng các số trên hàng i bằng tổng các số trên cột i =deg(i)
12. Ví dụ 1 1 0 0 1 1 0 0 0 1 0 0 0 0 0 1 1 0 0 0 1 0 5 2 1 0 0 0 1 5 2 0 0 0 0 1 A = 1 1 0 0 0 A = 1 0 0 0 0 0 1 1 0 0 0 1 0 0 0 4 3 4 3
13. Ví dụ Graphs - Data Structures • Vertices • Map to consecutive integers • Store vertices in an array • Edges • Adjacency Matrix • Booleans - TRUE - edge exists FALSE - no edge • O(|V|2) space
14. 2. Các khái niệm ◼ Nhận xét: Trực quan, dễ cài đặt Kích thước luôn là N2 dẫn đến lãng phí Kiểm tra các đỉnh kề của u, các cạnh liên thuộc của u cần xét tất cả các đỉnh v mà a[u,v]<>0 dẫn tới lãng phí bộ nhớ khi u là đỉnh cô lập hoặc đỉnh treo ( chỉ kề với 1 đỉnh).
15. 3. Biểu diễn đồ thị trong máy tính b) Danh sách cạnh (edge list) ◼ Liệt kê tất cả các cạnh của đồ thị trong một danh sách, mỗi phần tử của danh sách là một cặp (u,v) ◼ Danh sách được lưu trong bộ nhớ bằng mảng hoặc danh sách móc nối.
16. 1 2 5 4 3
17. 3. Biểu diễn đồ thị trong máy tính b) Danh sách cạnh (edge list) 1 2 3 4 5 6 (1, 2) (1, 3) (1, 5) (2, 3) (3, 4) (4, 5) (1, 2) (1, 3) (1, 5) (2, 3) (3, 4) (4, 5)
18. 3. Biểu diễn đồ thị trong máy tính ◼ Nhận xét Trong trường hợp đồ thị thưa, tiết kiệm Việc duyệt các cạnh dễ dàng hơn. Nhược điểm: khi duyệt với tất cả các đỉnh kề với v thì phải duyệt tất cả các cạnh và chọn tất cả các cạnh có chứa v → rất tốn thời gian, nhất là trong trường hợp ma trận dày.
19. 3. Biểu diễn đồ thị trong máy tính c) Danh sách kề (adjacency list) ◼ Với mỗi đỉnh ta cho tương ứng một danh sách các đỉnh kề với v.
20. 1 2 5 4 3
21. 1 2 3 4 5 6 7 8 9 10 11 12 2 3 5 1 3 1 2 4 3 5 1 4 1 2 3 4 5
22. CHƯƠNG IX: ĐỒ THỊ 3. Biểu diễn đồ thị trong máy tính c) Danh sách kề (adjacency list) List 1: 2 3 5 Graphs - Data Structures • Edges List 2: 1 3 • Adjacency Lists • For each vertex • List of vertices “attached” to it • For each edge List 3: 1 2 4 • 2 entries • One in the list for each end • O(|E|) space List 4: 3 5 Better for sparse graphs Undirected representation List 5: 1 4
23. ◼ Nhận xét. Duyệt tất cả các đỉnh kề của một đỉnh là hết sức dễ dàng. Khó kiểm tra (u,v) có phải là cạnh hay không.
24. 4. Các thuật toán tìm kiếm trên đồ thị ◼ Bài toán. Cho đồ thị G = , cần duyệt tất cả các đỉnh có thể đến được từ một đỉnh xuất phát nào đó với yêu cầu là không được bỏ sót hay lặp lại bất kì một đỉnh nào. ◼ Cần phải xây dựng các thuật toán duyệt một cách có hệ thống các đỉnh và gọi các thuật toán đó là thuật toán tìm kiếm trên đồ thị.
25. 4. Các thuật toán tìm kiếm trên đồ thị a) Tìm kiếm theo chiều sâu (Depth first search) Mọi đỉnh x kề với S sẽ đến được từ S. Với mỗi đỉnh x kề với S những đỉnh y kề với x cũng đến được từ S.
26. ◼ Xét thủ tục đệ quy DFS(u): duyệt từ đỉnh u bằng cách thăm đỉnh u và tiếp tục quá trình duyệt DFS(v) trong đó v là đỉnh chưa thăm kề với u
27. 4. Các thuật toán tìm kiếm trên đồ thị ◼ Ví dụ 2nd 5th 2 4 2 4 6 6 6th 1 7 1 7 8 8 1st 3 5 3 5 3rd 4th
28. 4. Các thuật toán tìm kiếm trên đồ thị Khi tất cả các đỉnh kề của đỉnh cuối cùng của quá trình đệ quy trên đã duyệt thì quay lại xét tương tự với đỉnh sát cuối, tiếp tục cho đến khi trỡ lại đỉnh u.
29. Chọn một đỉnh chưa thăm và lặp lại quá trình đệ quy như trên cho đến khi tất cả các đỉnh đều đã được thăm. Để tránh việc chưa thăm họăc thăm nhiều hơn 1 lần ta đánh dấu đỉnh đã thăm để bước duyệt đệ quy tiếp là không thăm lại đỉnh đó nữa.
30. 4. Các thuật toán tìm kiếm trên đồ thị Lưu lại đường đi xuất phát từ s, trong thủ tục DFS(u) trước khi gọi đệ quy DFS(v) với v là một đỉnh kề với u mà chưa đánh dấu, ta lưu lại đỉnh liền trước v trong đường đi từ u tới v bằng cách đặt Trace[v]=u (lưu lại đỉnh liền trước v trên đường đi từ s tới v). Khi kết thúc ta có đường đi từ S đến f là: f –p[1] = Trace(f)- p[2]= Trace[p[1]] s
31. 4. Các thuật toán tìm kiếm trên đồ thị a) Tìm kiếm theo chiều sâu (Depth first search) ◼ Nhận xét: Thủ tục DFS sẽ được gọi <= n ( n là số đỉnh) Có thể có nhiều đường đi từ S đến f nhưng thuật toán DFS luôn trã về một đường đi có thứ tự từ điển nhỏ nhất.
32. 4. Các thuật toán tìm kiếm trên đồ thị Quá trình tìm kiếm theo chiều sâu cho một cây gốc s với quan hệ cha con là: Nếu từ đỉnh u tới thăm đỉnh v ( DFS(u) gọi DFS(v)) thì u là nút cha của nút v.
33. Sau khi hoàn tất thăm cây ta có một rừng cây. Cần thiết phải đánh dấu với mỗi đỉnh các số hiệu xác định đỉnh đã được thăm và số hiệu xác định tất cả các đỉnh kề của nó đều đã được thăm. Trong cài đặt ta sử dụng Stack để ghi thứ tự xử lí các đỉnh.
34. 4. Các thuật toán tìm kiếm trên đồ thị a) Tìm kiếm theo chiều sâu (Depth first Graphssearch) - Depth-First struct t_graph { int n_nodes; Graph data graph_node *nodes; structure int *visited; AdjMatrix am; Adjacency Matrix ADT } static int search_index = 0; void search( graph g ) { int k; Mark all nodes “not visited” for(k=0;k n_nodes;k++) g->visited[k] = 0; search_index = 0; for(k=0;k n_nodes;k++) { Visit all the nodes if ( !g->visited[k] ) visit( g, k ); attached to node 0, } then }
35. Graphs - Depth-First Adjacency List version of visit void visit( graph g, int k ) { AdjListNode al_node; g->visited[k] = ++search_index; al_node = ListHead( g->adj_list[k] ); while( n != NULL ) { j = ANodeIndex( ListItem( al_node ) ); if ( !g->visited[j] ) visit( g, j ); al_node = ListNext( al_node ); } }
36. 4. Các thuật toán tìm kiếm trên đồ thị b) Tìm kiếm theo chiều rộng ( Breadth First) Đỉnh nào gần s hơn sẽ duyệt trước Sau khi đã duyệt xong tất cả các đỉnh liền kề của một đỉnh nào đó thì các đỉnh liền kề của đỉnh nào được duyệt trước sẽ duyệt trước.
37. ◼ Quá trình trên sẽ chấm dứt khi không thể đến thăm đỉnh nào nữa, khi đó lại xét với một đỉnh bất kì chưa thăm và lặp lại quá trình trên cho đến khi tất cả các đỉnh đều đã được thăm.
38. CHƯƠNG IX: ĐỒ THỊ 4. Các thuật toán tìm kiếm trên đồ thị b) Tìm kiếm theo chiều rộng ( Breadth First) S Graph - Breadth-first Traversal x x x 1 2 p • Breadth-first requires a FIFO queue static queue q; void search( graph g ) { u u u q = ConsQueue( g->n_nodes ); 1 2 q Phai duyet sau xp for(k=0;k n_nodes;k++) g->visited[k] = 0; search_index = 0; for(k=0;k n_nodes;k++) { if ( !g->visited[k] ) visit( g, k ); } void visit( graph g, int k ) { al_node al_node; int j; AddIntToQueue( q, k ); while( !Empty( q ) ) { k = QueueHead( q ); g->visited[k] = ++search_index;
39. 2nd 4th 2 4 2 4 6 6 6th 1 7 1 7 8 8 1st 3 5 3 5 3rd 5th
40. 4. Các thuật toán tìm kiếm trên đồ thị ◼ Nhận xét Có thể có nhiều đường đi từ s tới f nhưng BFS luôn cho đường đi ít cạnh nhất. Quá trình tìm kiếm cho một cây gốc s. Quan hệ cha-con: từ đỉnh u tới thăm đỉnh v thì thì u là nút cha của v. Khi kết thúc duyệt tạo thành một rừng cây. Trong cài đặt thuận lợi nhất là dùng hàng đợi để lưu các đỉnh đã được thăm nhưng chưa xem xét các đỉnh kề của nó.
41. 4. Các thuật toán tìm kiếm trên đồ thị c) Đánh giá độ phức tạp thuật toán ◼ Cách biểu diễn đồ thị có ảnh hưởng lớn đến thời gian thực hiện. Trong trường hợp biểu diễn bằng danh sách kề cả hai thuật toán đều có : O(n+m)=O(max(n,m)) ( n, m tương ứng là số đỉnh và số cạnh của đồ thị)
42. CHƯƠNG IX: ĐỒ THỊ 4. Các thuật toán tìm kiếm trên đồ thị Nếu biểu diễn bằng ma trận kề thì độ phức tạp sẽ là O(n+n2)=O(n2) Nếu biểu diễn theo danh sách cạnh thì việc duyệt những đỉnh kề với đỉnh u thì phải duyệt qua toàn bộ danh sách cạnh, O(n.m). ◼ Như vậy, độ phức tạp trong trường hợp biểu diễn bằng danh sách kề là tốt nhất
43. 5. Bài toán tìm đường đi ngắn nhất ◼ Ta gán mỗi cạnh đồ thị một số nào đó thì đồ thị gọi là có trọng số. Số gán đó gọi là trọng số của cạnh. ◼ Thường biểu diễn đồ thị này bằng ma trận trọng số T T[i,j]= trọng số của cạnh (i,j). T[i,i]=0 với mọi i T[ij]= một số nào đó để đánh dấu là không có cạnh (i,j), ví dụ là +∞ chẳng hạn.
44. 5. Bài toán tìm đường đi ngắn nhất ◼ Bài toán: Cho một đỉnh xuất phát s, và đỉnh kết thúc f, tìm đường đi ngắn nhất từ s đến f. ◼ Nếu không có đường đi từ s đến f thì thông báo.
45. 5. Bài toán tìm đường đi ngắn nhất a) Thuật toán E. Dijkstra Mỗi đỉnh v gán một nhãn d[v] là đường đi ngắn nhất từ s đến v. ◼ Bước khởi tạo d[s]=0 và d[v]= +∞ với mọi v <>s Nhãn có hai trạng thái: ◼ thay đổi: còn có thể tối ưu hơn ◼ xác định: đã đạt được tối ưu. Có thể dùng cách đánh dấu: free[v]= true hay false tương ứng là thay đổi hay xác định.
46. CHƯƠNG IX: ĐỒ THỊ 5. Bài toán tìm đường đi ngắn nhất Dijkstra’s Algorithm - Operation • Initialise d and • For each vertex, j, in V • dj = Initial estimates are all • j = nil No connections • Source distance, ds = 0 • Set S to empty • While V-S is not empty • Sort V-S based on d • Add u, the closest vertex in V-S, to S Add s first! • Relax all the vertices still in V-S connected to u
47. 5. Bài toán tìm đường đi ngắn nhất Dijkstra’s Algorithm - Operation • Initial Graph Source Red arrows show pre-decessors
48. a) Thuật toán E. Dijkstra ◼ Bước lặp Trong số các đỉnh thay đổi chọn đỉnh u mà d[u]= nhỏ nhất và xác định u; Sữa nhản tất cả các đỉnh thay đổi v và sữa theo công thức: d[v] = min ( d[v], d[u]+c[v,u])
49. Bước lặp sẽ kết thúc khi f được gán nhãn xác định. Nếu các nhãn thay đổi đều có d[v] =+∞ thì kết luận không có đường đi từ s đến f.
50. Dijkstra’s Algorithm - Operation Source is now in S Sort vertices and choose closest
51. 5. Bài toán tìm đường đi ngắn nhất a) Thuật toán E. Dijkstra ◼ Bước lặp Dijkstra’s Algorithm - Operation Change u’s pre-decessor also Source is now in S Relax y because a shorter path via x exists
52. Dijkstra’s Algorithm - Operation S is now { s, x } Sort vertices and choose closest
53. CHƯƠNG IX: ĐỒ THỊ 5. Bài toán tìm đường đi ngắn nhất a) Thuật toán E. Dijkstra ◼ Bước lặp Dijkstra’s Algorithm - Operation S is now { s, x, y } Sort vertices and choose closest, u
54. Dijkstra’s Algorithm - Operation S is now { s, x, y, u } Finally add v
55. Bước lặp sẽ kết thúc khi f được gán nhãn xác định. Nếu các nhãn thay đổi đều có d[v] =+∞ thì kết luận không có đường đi từ s đến f.
56. Dijkstra’s Algorithm - Operation S is now { s, x, y, u } Pre-decessors show shortest paths sub-graph
57. 5. Bài toán tìm đường đi ngắn nhất ) Thuật toán E. Dijkstra Bước kết hợp Lấy vết lưu trong quá trình sữa nhãn cho đường đi ngắn nhất tìm được hoặc thông báo không tồn tại đường đi (d[f]= +∞).
58. 5. Bài toán tìm đường đi ngắn nhất a) Thuật toán E. Dijkstra ◼ Độ phức tạp thuật toán Dùng không quá (n-1) bước lặp. Có thể xác định một đỉnh không thuộc D tại bước k dùng không quá n-1 phép so sánh Kết luận độ phức tạp thuật toán là O(n2)
59. 5. Bài toán tìm đường đi ngắn nhất b) Thuật toán Floyd Cho đồ thị có hướng , có trọng số với n đỉnh và m cạnh. Hãy tìm tất cả d(u,v) là khoảng cách ngắn nhất từ u đến v với mọi cặp đỉnh (u,v).
60. 5. Bài toán tìm đường đi ngắn nhất Từ ma trận trọng số TS tính lại các ts(u,v) thành độ dài ngắn nhất từ u tới v. Với mọi đỉnh k của đồ thị được xét theo thứ tự từ 1 tới n, xét mọi cặp u,v. Cực tiểu hóa ts(u,v) theo công thức: Ts(u,v)= min {ts (u,v), ts(u,k) +ts (k,v)}
61. 5. Bài toán tìm đường đi ngắn nhất Giả thiết ta đã xây dựng tsk-1 (u,v) khi đó tsk (u,v) được xác định: Nếu đường đi ngắn nhất u tới v chỉ đi qua các đỉnh trung gian thuộc tập 1,2, ,k mà: ◼ Không đi qua đỉnh k ( chỉ đi qua các đỉnh trung gian thuộc tập 1,2, k-1) thi: tsk (u,v) = tsk-1 (u,v)
62. ◼ Có đi qua đỉnh k thì đường đi đó sẽ nối hai đường đi từ u đến k và từ k đến v mà hai đường đi sau chỉ chứa các đỉnh thuộc tập 1,2, k-1: Tsk(u,v)=Tsk-1(u,k) + Tsk-1 (k,v)
63. 5. Bài toán tìm đường đi ngắn nhất Nhận xét Dựa trên nguyên lí tối ưu; nếu đỉnh k nằm trên đường đi ngắn nhất từ i đến j thì các đoạn đường từ i tới k và từ k tới j là ngắn nhất. Việc cài đặt thuật toán Floyd rất dễ dàng ( 03 vòng For lồng nhau). Do cách biểu diễn bằng ma trận kề nên khi n đủ lớn thì sẽ gặp khó khăn về không gian nhớ. Độ phức tạp thuật toán là O(n3).
64. 6. Bài toán cây khung ◼ Định nghĩa Cho đồ thị G= là đồ thị vô hướng, cây T= trong đó F là tập con của E. Khi đó T gọi là cây khung của G. Có nhận xét, với đồ thị vô hướng liên thông có thể có nhiều cây khung.
65. G T1 T2 T3
66. CHƯƠNG IX: ĐỒ THỊ 6. Bài toán cây khung a) Thuật toán hợp nhất Mỗi đỉnh đồ thị coi là một cây. Nếu có cạnh nối hai cây khác nhau thì bổ sung cạnh đó vào cây cho đến khi đủ n-1 cạnh là được.
67. b) Thuật toán áp dụng DFS và DBS Cả hai thuật toán đều duyệt mỗi đỉnh đúng một lần và nếu ta ghi dấu vết đi qua các cạnh nào thì bổ sung các cạnh đi qua đó là có được cây khung.
68. 1 1 2 3 2 3 4 5 6 7 4 5 6 7 8 9 10 11 8 9 10 11
69. 6. Bài toán cây khung c) Thuật toán J.Kruskal ◼ Trọng số của một cây là tổng trọng số tất cả các trọng số các cạnh của cây đó. Cây khung có trọng số nhỏ nhất gọi là cây khung nhỏ nhất. Bước 1. Khởi tạo n cây ,mỗi cây là 1 đỉnh. Bước 2. Xét tất cả các cạnh từ trọng số nhỏ nhất đến lớn nhất. Nếu thêm cạnh đó vào mà không tạo thành chu trình thì thêm cạnh đó vào cây. Bước 3. Lặp lại bước 2 cho đến khi đủ n-1 cạnh hoặc khi kết nạp thêm cạnh mới vào đều dẫn đến là luôn có chu trình, đồ thị không liên thông, không tồn tại cây khung.
70. ◼ Nhận xét Khi cài đặt cần sắp xếp danh sách cạnh theo thứ tự không giảm của trọng số. Muốn thêm một cạnh (u,v) vào cây để không thành chu trình thì cạnh (u,v) phải nối hai cây khác nhau ( nếu cả u và v đều thuộc cùng một cây thì sẽ tạo thành chu trình). Như vậy ban đầu có n cây sau mỗi bước hợp nhất hai cây thành một cây. Độ phức tạp phụ thuộc vào thuật toán sắp xếp danh sách cạnh, ví dụ sử dụng Heapsort có độ phức tạp là O(mlgn).
71. 6. Bài toán cây khung d) Thuật toán R. Prim ◼ Xét một cây T trong đồ thị G và một đỉnh v, gọi khoảng cách ngắn nhất từ v tới T là trọng số nhỏ nhất trong số các cạnh nối v với T: d[v] = min{ ts[u,v] với mọi u thuộc T}
72. Bước 1. Khởi tạo T chỉ gồm một đỉnh. Bước 2. Chọn đỉnh gần T nhất và kết nạp đỉnh đó và cạnh có khoảng cách ngắn nhất vào T. Bước 3. Lặp lại bước 2 cho đến khi hoặc cây T là cây đã có đủ n đỉnh hoặc là các đỉnh còn lại có khoảng cách đến T đều là vô cùng. Trường hợp này xẩy ra khi đồ thị không liên thông.
73. ◼ Nhận xét Độ phức tạp thuật toán R Prim là O(n2) Có thể kết hợp thuật toán R. Prim với việc sử dụng cấu trúc Heap, khi đó độ phức tạp là O( (m+n)lgn) Khi đồ thị dày thì nên dùng thuật toán R. Prim
74. 7. Tính liên thông của đồ thị ◼ Định nghĩa Đồ thị G= gọi là liên thông nếu tồn tại đường đi giữa hai đỉnh bất kì của G. Nếu đồ thị không liên thông thì nó sẽ là hợp của hai hay nhiều đồ thị con liên thông. Các đồ thị con từng đôi một rời nhau và gọi là thành phần liên thông.
75. G1 G2 G3
76. 7. Tính liên thông của đồ thị Định nghĩa Một đồ thị đầy đủ với n đỉnh là một đồ thị vô hướng mà giữa hai đỉnh bất kì của nó đều có cạnh nối. Từ đồ thị G người ta xây dựng đồ thị G’= với E’ được xác định: giữa hai đỉnh u và v có cạnh nối khi và chỉ khi giữa u và v trong G có đường đi. G’ gọi là bao đóng của G.
77. ◼ Nhận xét: Một đồ thị đầy đủ là liên thông. Một đơn đồ thị vô hướng là liên thông nếu và chỉ nếu bao đóng của nó là đồ thị đầy đủ Một đơn đồ thị vô hướng có k thành phần liên thông nếu và chỉ nếu bao đóng của nó có k thành phần đầy đủ.
78. ◼ Thuật toán Warshall (1959) Với đồ thị vô hướng G, với mọi đỉnh k xét theo thứ tự từ 1 đến n, với tất cả các cặp đỉnh (u,v) nếu có tồn tại cạnh nối (u,k) và cạnh nối (k,v) thì ta tự nối thêm cạnh (u,v) nếu chưa có.
79. CHƯƠNG X: CÁC KỸ THUẬT THIẾT KẾ THUẬT TOÁN 1. Phương pháp duyệt 2. Phương pháp ăn tham 3. Chia để trị và đệ quy 4. Quy hoạch động
80. CHƯƠNG X: CÁC KỸ THUẬT THIẾT KẾ THUẬT TOÁN 1. Phương pháp duyệt a) Duyệt tuyến tính Tư tưởng chính của duyệt tuyến tính là “vét cạn” một cách có hệ thống tất cả các khả năng có thể xẩy ra.
81. Duyệt toàn bộ ◼ Phương pháp rất cơ bản, thường dùng trong cuộc sống hàng ngày. ◼ Cho phép tìm ra một nghiệm hoặc tất cả các nghiệm ( nếu có). ◼ Ví dụ thuật toán tìm kiếm tuần tự ta đã sử dụng duyệt lần lượt từ số hạng thứ nhất cho đến số hạng sau cùng.
82. b) Phương pháp mắt lưới Ví dụ: cho phương trình y=f(x) liên tục trong đoạn [a,b], cần tìm x trong đoan [a,b] sao cho f(x)=0. Cách giải: Chia đoạn [a,b] thành n đoạn bằng nhau có kích thước epx đủ nhỏ để f(x)=0 với mọi x mà |x-x0| < epx Nếu trong đoạn [xi,xi+1] có nghiệm thì f(xi)*f(xi+1) < 0, từ đó x =(xi + xi+1 )/2 sẽ là nghiệm của phương trình.
83. c) Duyệt phi tuyến Tư tưởng chính là từng bước một tìm các khả năng có thể để xây dựng theo kiểu kiến thiết các thành phần của nghiệm theo cách “ thử sai”.
84. Tám con hậu ◼ Bài toán tám con hậu ◼ Cần đặt tám con hậu trên bàn cờ Quốc tế sao cho chúng không thể ăn nhau được ( không có quá 1 con hậu trên mỗi dòng, mỗi cột, mỗi đường chéo).
85. Tám con hậu ◼ Các con hậu được đánh số thứ tự từ 1 đến 8. Con hậu i đứng ở hàng thứ i và cột thứ ci (1 cj và các ô ( i, ci) và (j,cj) không nằm trên cùng một đường chéo. ◼ Các giá trị có thể tạo thành nghiệm thành phần tạo thành tập khả năng ( ví dụ tập {1,2, 8})
86. Tám con hậu ◼ Đây là một bài toán cổ điển có từ thế kĩ 18 mà các nhà toán học rất quan tâm cả hai khía cạnh: chỉ ra một cách xếp các con hậu và có bao nhiêu cách xếp hậu khác nhau.
87. Tám con Hậu ◼ Giả sử đã chọn được c1,c2, ,ci-1 ◼ Từ điều kiện của bài toán ta chọn các khả năng cho ci. Phạm vi chọn các khả năng phụ thuộc vào c1,c2, ,ci-1 đã chọn trước đó.Nghiệm thành phần cần “thư-̉ sai” để mở rộng, lặp lại quá trình đó cho đến khi xây dựng xong nghiệm.
88. Tám con hậu ◼ Nếu không chọn được khả năng cho ci ( đã thử hết với tất cả các khả năng nhưng vẫn không thành công thì phải “ quay lui” xây dựng lại ci-1 bằng cách “thử-sai với các khả năng còn lại. ◼ Nếu tất cả các khả năng của ci-1 đã thử hết mà không chọn được ci thì phải xây dựng lại ci-2 ◼ Quá trình trên được lặp lại cho đến khi hoặc xây dựng đủ n nghiệm thành phần hoặc bài toán trên thực tế không có nghiệm.
89. c1 c2 c3 c4 c5 c6 c7 c8 Tám con hậu x x x x x x x x
90. ◼ Nhận xét ◼ Thực chất là ta đã chia bài toán thành các bài toán thành phần và mô tả dưới dạng đệ quy. ◼ Do sự bùng nổ các phép toán (dạng cây) nên tùy điều kiện bài toán thường phải tìm cách phát hiện các điều có thể biết trước mà không cần thử sai để giảm bớt sự bùng nỗ phép toán.
91. Nhận xét ◼ Ví dụ, ở mỗi hàng có thể xem đều có 8 khả năng để đặt hậu. Tuy nhiên ở mỗi hàng, không cần thiết phải đặt hậu ở các cột mà tại đó đã có con hậu trên hàng nào đó trước đó. Do vậy, khi xét hàng i thì chỉ có (8-i+1) khả năng có thể lựa chọn để thử –sai mà thôi.
92. Nhận xét ◼ Nếu yêu cầu chỉ cần tìm ra một nghiệm của bài toán thì không nhất thiết phải “ duyệt toàn bộ” các khả năng. Việc làm đó chỉ xẩy ra khi đòi hỏi phải đưa ra tất cả các nghiệm hoặc khi để khẳng định bài toán không có nghiệm
93. CHƯƠNG X: CÁC KỸ THUẬT THIẾT KẾ THUẬT TOÁN 2. Phương pháp tham ăn ◼ Thường dùng để giải các bài toán tối ưu theo nghĩa tốt nhất có thể được mà do kích thước dữ liệu quá lớn không giải quyết bằng phương pháp duyệt toàn bộ được. Độ phức tạp của nhiều bài toán tối ưu nói chung là hàm mũ. Yêu cầu tối ưu đôi khi không phải là ưu tiên bắt buộc mà yêu cầu chỉ cần có nghiệm gần tối ưu chấp nhận được.
94. Ăn tham ◼ Ví dụ, cần chọn B tập con của tập A mà các phần tử tập B thỏa mãn một số tính chất nào đó. Tập con B như vậy được gọi là nghiệm chấp nhận được. ◼ Gắn với các nghiệm chấp nhận là một hàm mục tiêu. Nghiệm tối ưu là nghiệm chấp nhận có giá trị hàm mục tiêu tốt nhất.
95. Ăn tham ◼ Xây dựng tập B bằng kiến thiết, khởi tạo B là một tập rỗng. Tại mỗi bước, chọn một phần tử “hợp lí nhất” của tập A để kết nạp vào tập B và loại phần tử đó ra khỏi tập A. ◼ Lựa chọn dựa trên tiêu chí cho trước. Việc mở rộng B sẽ kết thúc khi thêm một phần tử mới vào B thì nó không còn thỏa mãn tiêu chí nữa.
96. Ăn tham ◼ Có hai vấn đề giải quyết: 1. Xây dựng cách chọn theo kiễu ăn tham. 2. Xây dựng cấu trúc tối ưu
97. CHƯƠNG X: CÁC KỸ THUẬT THIẾT KẾ THUẬT TOÁN 2. Phương pháp tham ăn Bài toán xử lí công việc ◼ Cho CV={1,2, N}. là tập N công việc cần sử dụng tài nguyên, mà tại mỗi thời điểm chỉ phục vụ cho một công việc. Giả thiết, công việc i có thời gian bắt đầu si và kết thúc là fi và thỏa mãn si fj hoặc sj>=fj.
98. ◼ Yêu cầu là chọn công việc đưa vào sử dụng sao cho càng nhiều công việc càng tốt. ◼ Không mất tính tổng quát ta giả thiết f1<=f2<= <=fn
99. 2. Phương pháp tham ăn Bài toán xử lí công việc (i) Xây dựng lựa chọn theo kiễu ăn tham. Tại mỗi thời điểm đang xét, chọn cái tốt. Vì f1 là nhỏ nhất ( việc một kết thúc sớm nhất) nên ta chọn CV1 đưa vào thực hiện trước tiên. Việc lựa chọn bây giờ cũng tương tự như bài toán xuất phát nhưng chỉ lựa chọn trong số (n- 1) công việc còn lại.
100. Ăn tham (ii) Xây dựng cấu trúc tối ưu. Nghiệm tối ưu của bài toán chứa nghiệm tối ưu của bài toán con. Thuật toán: ◼ Bước 1. CV:=[1]; ◼ Bước 2. j:=1; i:=1; ◼ Bước 3 Nếu i> N đưa ra CV và kết thúc; ◼ Bước 4. i:=i+1; ◼ Bước 5. Nếu si >= fj thì { CV:= CV+[i]; j:=i} ◼ Bước 6. Quay lại bước 3.
101. CHƯƠNG X: CÁC KỸ THUẬT THIẾT KẾ THUẬT TOÁN 2. Phương pháp tham ăn Bài toán xử lí công việc i si fi 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1* 1 4 x x x 2 3 5 3 0 6 4* 5 7 x x 5 3 8 6 5 9 7 6 10 8* 8 11 x x x 9 8 12 10 2 12 11 12 14 x x *
102. 2. Phương pháp tham ăn ◼ Nhận xét Nghiệm của bài toán nói chung không cho nghiệm tối ưu toàn cục. Tuy nhiên cũng không ít trường hợp nó cho nghiệm tối ưu. Một số trường hợp người ta tìm cách xây dựng lựa chọn ăn tham khác nhau. Với mỗi cách cho một nghiệm tối ưu gần đúng. Trong số các nghiệm tìm được đó chọn nghiệm tốt nhất.
103. 3. Chia để trị và đệ quy ◼ Giới thiệu Có thể hiểu chiến lược Chia-Để- Trị một cách đại thể như sau: Chia: Chia bài toán xuất phát, phức tạp, có kích thước Input lớn thành các bài toán con tương tự nhưng có kích thước Input nhỏ hơn.
104. Chia-Để- Trị Trị: Giải các bài toán con bằng đệ quy. Các bước Chia- Trị được lặp lại cho đến khi bài toán con hoặc là có lời giải hiển nhiên hoặc dẽ dàng nhận đươc lời giải. Kết hợp nghiệm (combaine): Nghiệm các bài toán con được kết hợp để cho nghiệm bài toán con lớn hơn và cuối cùng cho nghiệm của bài toán xuất phát.
105. 3. Chia để trị và đệ quy ◼ Nhận xét Sử dụng công cụ đệ quy: ◼ rất chặt chẽ, dễ cài đặt ◼ Thường đòi hỏi khối lượng tính toán rất lớn. Quá trình thực hiện Chia- Để trị diễn ra theo hai bước:
106. Chia-Để- Trị Bước chia để trị là đi “ từ trên xuống”( Top- Down) để xác định lời gọi đệ quy. Bước kết hợp nghiệm thì đi từ dưới lên ( Bottom-up), tại bước này thực hiện các tính toán và kết hợp nghiệm cho bài toán lớn hơn. Do nghiệm các bài toán con không được lưu trữ nên các bước sau, khi cần sử dụng thì phải tính lại.
107. CHƯƠNG X: CÁC KỸ THUẬT THIẾT KẾ THUẬT TOÁN 4. Quy hoạch động a) Định nghĩa ◼ Phương pháp quy hoạch động thường dùng để giải các bài toán tối ưu có bản chất đệ quy ◼ Trong QHĐ khi không biết phải giải bài toán con nào ta sẽ giải tất cả các bài toán con và lưu trữ lại tất cả các nghiệm của các bài toán con này và khi gặp lại thì không cần phải giải lại mà chỉ cần sử dụng các nghiệm đã được lưu trữ.
108. Quy hoạch động ◼ Bài toán có thõa mãn các yêu cầu: 1. Bài toán phải phân rã thành nhiều bài toán con mà sự kết hợp lời giải các bài toán con đó phải cho lời giải của bài toán lớn. 2. QHĐ cần có bộ nhớ để lưu trữ nên phải xem ta có đủ tài nguyên hay không. 3. Quá trình từ bài toán cơ sở tìm ra lời giải bài toán xuất phát phải qua hữu hạn bước.
109. 4. Quy hoạch động b) Thuật ngữ ◼ Công thức kết hợp nghiệm các bài toán con để có nghiệm của bài toán lớn hơn gọi là công thức truy hồi của QHĐ. ◼ Tập các bài toán nhỏ nhất có lời giải hiển nhiên để từ đó giải các bài toán lớn hơn gọi là cơ sở của QHĐ. ◼ Không gian dùng để lưu trữ nghiệm các bài toán con dùng đề tính nghiệm bài toán lớn hơn gọi là bảng phương án của QHĐ.
110. 4. Quy hoạch động c) Thuật toán QHĐ ◼ Bước 1: Lưu nghiệm của các bài toán cơ sở vào các vị trí tương ứng trong bảng phương án. ◼ Bước 2: Dùng công thức truy hồi, dựa vào nghiệm các bài toán con đã lưu trong bảng phương án để tính nghiệm bài toán lớn hơn và lưu kết quả vào vị trí tương ứng trong bảng phương án. Tiếp tục quá trình đó cho đến khi bảng phương án được tính xong hoàn toàn. ◼ Bước 3: Dựa vào bảng phương án, truy vết để tìm ra nghiệm tối ưu.
111. Ví dụ d) Một số ví dụ ◼ Dãy con đơn điệu tăng dài nhất Cho A là dãy số nguyên a1,a2, .an. Một dãy con của A là một cách chọn trong A một số phần tử giữ nguyên thứ tự. Nhận xét . Số lượng dãy con là 2n. Yêu cầu. Tìm dãy con đơn điệu tăng của A có độ dài lớn nhất. ◼ Kết luận: Độ dài xâu con dài nhất là 7 và bao gồm các phần tử thứ
112. Ví dụ ◼ Ta sẽ giải bài toán này bằng QHĐ. ◼ - Bổ sung vào dãy 02 phần tử là a[0]= -∞ và a[n+1]=+ ∞ ◼ - Khi đó dãy con dài nhất chắc chắn bắt đầu từ a[0] và kết thúc tại a[n+1] ◼ - Với mọi I 0<=i<=n+1 ta tính độ dài L[i] - độ dài dãy con dài nhất bắt đầu từ a[i].
113. Ví dụ (i) Cơ sở QHĐ. ◼ Rõ ràng L[n+1]=1
114. Ví dụ ◼ (ii) Bảng phương án. Gồm n+2 phần tử để lưu các kết quả tính độ dài dài nhât của tất cả các vị trí, đầu tiên ghi giá trị 1 vào phần tử cuối cùng của mảng L.
115. iii) Công thức truy hồi ◼ Giả sử i bắt đầu từ n giảm mỗi lần 1 cho đến khi i=0. Cần tính L[i] khi đã biết L[i+1], ,L[n+1]. ◼ Dãy con dài nhất từ vị trí a[i] được thành lập bằng cách ghép thêm a[i] vào đầu một trong số dãy con dài nhất bắt đầu từ vị trí a[j] đứng sau a[i].
116. Ví dụ ◼ Dãy nào sẽ được chọn? Rõ ràng là chỉ ghép a[i] vào dãy con bắt đầu từ a[j] mà a[j] >a[i] và phải chọn dãy con dài nhất. ◼ L[i] được tính: Xét tất cả chỉ số j trong khoảng từ i+1 đến n+1 mà a[j] >a[i] , chọn ra chỉ số jmax có L[jmax] dài nhất ◼ Đặt L[i] = L[jmax] +1
117. QHĐ ◼ (iV) Truy vết ◼ -Mỗi lần khi gán L[i] = L[jmax] +1ta đặt T[i] =jmax để chỉ rằng dãy con dài nhất bắt đầu từ a[i] có phần tử thứ 2 là a[jmax]. ◼ - Sau khi tính xong bảng phương án L và bảng ghi vết T, dãy sẽ bắt đầu từ T[0] – là phần tử đầu tiên được chọn. ◼ T[T[0]] là phần tử thứ 2, .
118. Ví dụ I 0 1 2 3 4 5 6 7 8 9 10 11 A[i] - ∞ 5 2 3 4 9 10 5 6 7 8 +∞ L[i] 9 5 8 7 6 3 2 5 4 3 2 1 T[i] 2 8 3* 4* 7* 6 11 8* 9* 10* 11