›
›

Bài giảng Thiết kế và đánh giá thuật toán - Phan Thị Hà Dương

ppt 231 trang phuongnguyen 120
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Thiết kế và đánh giá thuật toán - Phan Thị Hà Dương", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pptbai_giang_thiet_ke_va_danh_gia_thuat_toan_phan_thi_ha_duong.ppt

Nội dung text: Bài giảng Thiết kế và đánh giá thuật toán - Phan Thị Hà Dương

  1. Thiết kế và đánh giá thuật toán Cao học, khoa công nghệ thông tin Đại học quốc gia Hà nội. Phan Thị Hà Dương Viện Toán học. phan.haduong@gmail.com 1
  2. Chương trình Chương 1: Giới thiệu về thuật toán Chương 2: Phân tích tính hiệu quả của thuật toán Chương 3: Phương pháp “tham lam” Chương 4: Phương pháp “chia để trị” Chương 5: Phương pháp qui hoạch động Chương 6: Thuật toán trên đồ thị Chương 7: Phương pháp xác suất Chương 8: Về độ phức tạp tính toán 2
  3. Ví dụ: Chương 3: Phương pháp “tham lam” I. Giới thiệu chung II. Thuật toán trên đồ thị 1) Cây bao trùm nhỏ nhất 2) Đường đi ngắn nhất III. Thuật toán sắp xếp lịch làm việc IV. Thuật toán “heurisitic” 1) Tô màu đồ thị 2) Người đưa hàng 3
  4. Sách tham khảo 4
  5. Sách tham khảo 2. Algorithmique - conception et analyse G. Brassard and P.Bratley, Masson, Paris , 1987 3. Data structure and algorithms A. Aho, J. Hopcroft and J. Ullman, Addison Wesley Publishing Company 4. Lý thuyết độ phức tạp tính toán. Phan Đình Diệu. 5
  6. Chương 1: Giới thiệu về thuật toán I. Khái niệm thuật toán II. Một số ví dụ III. Đánh giá thuật toán trong trường hợp xấu nhất và theo trung bình IV. Về thuật toán hiệu quả V. Một số bài toán cụ thể VI. Cấu trúc dữ liệu 6
  7. Khái niệm về thuật toán Thuật toán: Quá trình tính toán Dữ kiện vào Một dãy các bước tính toán Thuật toán sắp xếp Một dãy số 7
  8. Một số từ khóa if (điều kiện) then { } else for (điều kiện) do { } while (điều kiện) do { } procedure (T, a, b) { } function(A) { return r; } 8
  9. Sắp xếp chèn vào 5 2 4 6 1 3 2 5 4 6 1 3 2 4 5 6 1 3 2 4 5 6 1 3 1 2 4 5 6 3 1 2 3 4 5 6 9
  10. Thuật toán xếp chèn vào Insertion-Sort (A) { for j = 2 to length (A) do { k = A[j]; // chèn A[j] vào dãy đã sắp A[1 j-1] j = j-1; while i > 0 and A[i] > k do { A[i+1] = A[i]; I = i-1; } A{i+1} = k; } } 10
  11. Thuật toán xen kẽ (merge sort) 11
  12. Sắp xếp xen kẽ Merge-Sort(A,p,r){ 1. if p < r then { 2. q = [(p+r-1)/2]; 3. Merge-Sort(A,p,q); 4. Merge-Sort(A,q+1,r); 5. Merge(A,p,q,r); } } 12
  13. Phân tích thuật toán Merge-Sort Đây là một thuật toán chia để trị. Chia: bước 2: θ(1) Trị: bước 3 và 4: 2T(n/2) Hợp lại: bước 5: θ(n) Tổng kết: T(n) = θ(1) nếu n=1 2T(n/2) + θ(n) nếu n >1 13
  14. Đánh giá thuật toán Giải quyết một bài toán. Mô hình hóa Viết thuật toán Lập chương trình Vấn đề: Có nhiều thuật toán. Chọn thuật toán nào ? 14
  15. Phương pháp đánh giá Phương pháp thực nghiệm: Lập trình, và thử trên các ví dụ xem thuật toán nào nhanh. Phương pháp lý thuyết: Tính toán thời gian, bộ nhớ, cần thiết của mỗi thuât toán dựa theo độ lớn của dữ liệu vào. Ưu điểm: - không phụ thuộc ngôn ngữ lập trình, loại máy tính - Biết được tính hiệu quả của thuật toán đối với các dữ liệu có kích thước lớn. 15
  16. Đánh giá thuật toán trong trường hợp xấu nhất và theo trung bình Ví dụ: Sắp xếp lựa chọn Select-Sort (A){ for i=1 to n-1 do { index = i; x = T[i]; for j= i+1 to n do { if T[j] < x then { index = j; x = T[j];} } T{index = T{i}; T{i} = x; } } 16
  17. Ví dụ Hãy chạy thuật toán Insertion-Sort Merge-Sort Đối với các bảng sau : A = [3,1,4,1,5,9,2,6,5,3] B = [1,2,3,4,5,6] C = [6,5,4,3,2,1] 17
  18. Thời gian chạy trong trường hợp xấu nhất: là cận trên đối với mọi dữ liệu vào. Thời gian chạy trung bình: thường khó phân tích và đánh giá hơn. 18
  19. Ví dụ: dãy Fibonacci Dãy Fibonacci được định nghĩa: F(0) = 0, F(1) = 1, và F(n) = F(n-1) + F(n-2) với n > 1. Tìm thuật toán tính số Fibonacci thứ n. 19
  20. Thuật toán thứ nhất và thứ hai fontion fib1(n){ if n < 2 then return n; else return f(n-1) + f(n-2); } fonction fib2(n){ a= 0; b = 1; for k = 1 to n do {c=b; b = a+b; a=c;} return b; } 20
  21. Thuật toán thứ ba fonction fib3(n){ i = 1; j = 0; k = 0; h = 1; while n>0 do { if (n lẻ) then { t = jh; j = ih + jk +t; i = ik +t;} t = h^2; h = 2kh+t; k = k^2+t; n = n div 2; } return j; } 21
  22. Ví dụ về thời gian chạy (Pascal, CDC Cyber 835) n 10 20 30 50 100 10000 1 000 10000 000 0000 fib1 8 ms 1 s 2 min 21 days fib2 1/6 1/3 ½ ms ¾ ms 3/2 150 15 s 25 ms ms ms ms min fib3 1/3 2/5 ½ ms ½ ms ½ ms 1 ms 3/2 2 ms ms ms ms 22
  23. Cấu trúc dữ liệu Dãy (list) 6 7 1 3 type tablist = structure{ value[1 lengthmax]: information elements; counter: 0 lengthmax;} type elem = structure{ value: information element; next: * elem;} 23
  24. Đồ thị 2 1 type adjgraph = structure { 3 value[1 n]: information elements; 4 adjacent[1 n, 1 n]: booleans;} type listgraph = array[1 n] of structure { value: information element; neighbours: list; } 24
  25. Cây type treenode = structure{ a value: information element; children: array[ ] of * treenodes; } b c type treenode = structure{ value: information element; first child: * treenode; next brother: * treenode; } d e f type binarytreenode = structure{ value: information element; left child, right child: * binarytreenode; } 25
  26. Tập hợp set[1 N]: integer; fonction find(x){ } // tìm phần tử có giá trị x procedure merge(a,b) // tìm hợp của hai tập được sắp 26
  27. Chương 2: Phân tích tính hiệu quả của thuật toán I. Các ký hiệu đánh giá tiệm cận II. Phân tích thuật toán III. Giải các phương trình đệ qui IV. Một số ví dụ 27
  28. Ký hiệu O: O(g(n)) = {f(n): tồn tại hằng số c và N để: 0 ≤ f(n)< c g(n) với mọi n ≥ N} Đây là một quan hệ thứ tự: phản xứng, “phi đối xứng” và bắc cầu. 28
  29. Ký hiệu Ω Ω(g(n)) = {f(n): tồn tại hằng số c và N để: f(n)≥ c g(n) với mọi n ≥ N} f(n) Є Ω (g(n)) ≈ g(n) Є O(f(n)) Đây là một quan hệ thứ tự: phản xứng, “phi đối xứng” và bắc cầu. 29
  30. Ký hiệu θ θ(g(n))={f(n): tồn tại 2 hằng c, d và N để: c g(n) ≤ f(n) ≤ d g(n) với mọi n ≥ N} f(n) = θ(g(n)) ≈ f(n) = O(g(n)) và f(n) = Ω(g(n)) Đây là một quan hệ tương đương: phản xứng, đối xứng và bắc cầu. 30
  31. Ký hiệu o o(g(n)) = {f(n): với mọi hằng c >0, tồn tại N để: 0 ≤ f(n)< c g(n) với mọi n ≥ N} Đây là một quan hệ thứ tự: phản xứng, “phi đối xứng” và bắc cầu. 31
  32. Ký hiệu ω ω(g(n)) = {f(n): với mọi hằng c >0, tồn tại N để: 0 ≤ c g(n) <f(n) với mọi n ≥ N} f(n) Є ω(g(n)) ≈ g(n) Є o(f(n)) Đây là một quan hệ thứ tự: phản xứng, “phi đối xứng” và bắc cầu 32
  33. Nhận xét f(n) = O (g(n)) ≈ a ≤ b f(n) = Ω (g(n)) ≈ a ≥ b f(n) = θ (g(n)) ≈ a = b f(n) = o (g(n)) ≈ a b 33
  34. Sắp xếp các hàm sau theo quan hệ 0 và θ 34
  35. Một số hàm cơ bản 1. n^b = o(a^n), với mọi a>1 và b 2. e^x = 1 + x + θ(x^2), với |x| ≤ 1 3. lg^b n = o(n^a), với mọi a > 0 4. n! = o(n^n) 5. n! = ω(2^n) 6. lg(n!)= θ(n lg n) 35
  36. Giải các phương trình đệ qui Ví dụ: T(n) = θ(1) nếu n= 1 2 T(n/2) + θ(n) nếu n >1 T(n) = θ(n lg n) 36
  37. Phương pháp truy hồi - Dự đoán kết quả - Chứng minh bằng truy hồi (quy nạp) Ví dụ: Cho T(n) = 2 T(n/2) + n. Ta chứng minh truy hồi rằng T(n) = O(n lg n). 37
  38. Đổi biến Ví dụ: T(n) = 2 T([√n]) + lg n Đặt m = lg n, ta có: T(2^m) = 2 T(2^{m/2}) + m Đặt S(m) = T(2^m), ta có: S(m)= 2 S(m/2) + m T(n) = S(m) = O(m lg m) = O(lg n lg lg n) 38
  39. Phương pháp tính dần từng bước Ví dụ T(n) = 3T(n/4)+n T(n) = n+ 3 T(n/4) = n + 3(n/4 + 3T(n/16)) = n + 3 n/4 + 3 (n/16 + 3T(n/64)) ≤ n + 3n/4 + 9n/16 + 39
  40. Ví dụ: Sắp xếp xen kẽ Merge-Sort(A,p,r){ 1. if p < r then { 2. q = [(p+r-1)/2]; 3. Merge-Sort(A,p,q); 4. Merge-Sort(A,q+1,r); 5. Merge(A,p,q,r); } } 40
  41. Phân tích thuật toán Merge-Sort Đây là một thuật toán chia để trị. Chia: bước 2: θ(1) Trị: bước 3 và 4: 2T(n/2) Hợp lại: bước 5: θ(n) Tổng kết: T(n) = θ(1) nếu n=1 2T(n/2) + θ(n) nếu n >1 41
  42. The Master Theorem Cho a≥1 và b>1 hằng số, hàm số f(n) và T(n) được định nghĩa: T(n) = aT(n/b) + f(n), Khi đó định lý sẽ cho biết giới hạn tiệm cận của T(n) 43
  43. Chương 3: Phương pháp “tham lam” I. Giới thiệu chung II. Thuật toán trên đồ thị 1) Cây bao trùm nhỏ nhất 2) Đường đi ngắn nhất III. Thuật toán sắp xếp lịch làm việc IV. Thuật toán “heurisitique” 1) Tô màu đồ thị 2) Người đưa hàng 44
  44. Giới thiệu chung (greedy algorithms) Các thuật toán tham lam chủ yếu để giải quyết các bài toán tối ưu. Ta có: - Một tập các đối tượng - Một dãy các đối tượng đã lựa chọn - Một hàm để xem một tập các đối tượng có lập thành một giải pháp hay không (không nhất thiết tối ưu) - Một hàm để xem một tập đối tượng có là tiềm năng hay không - Một hàm để lựa chọn ứng viên có triển vọng nhất - Một hàm đích cho giá trị của một giải pháp (để tối ưu hóa) 45
  45. Cách giải quyết Tìm một tập các đối tượng lập thành một giải pháp và tối ưu hóa hàm đích. Từng bước một: - Đầu tiên tập đối tượng là rỗng - Tại mỗi bước, ta cố thêm vào một đối tượng tốt nhất còn lại (nhờ hàm chọn) + Nếu tập mới không là tiềm năng, bỏ đối tượng này đi, chọn đối tượng khác + Ngược lại, đối tượng mới này xếp vào cuối tập + Kiểm tra xem tập mới có là một giải pháp 46
  46. Tính đúng đắn Một thuật toán “tham lam” chạy đúng nếu giải pháp được lựa chọn là tối ưu. 47
  47. Thuật toán sinh Thuật_toán Tham_lam{ // vào: tập hợp C các đối tượng // ra: tập S (giải pháp tối ưu) S = Ø; while(! solution(S) and C <> Ø) do { x = phần tử của C sao cho select(x) max; C = C \ {x}; if realisable(S U {x}) then S = S U {x};} if solution(S) then return S; else return “không có nghiệm”; } 48
  48. Cây bao trùm nhỏ nhất Bài toán: Cho đồ thị vô hướng liên thông G=(V,E). Mỗi cạnh e Є E có độ dài l(e). Tìm tập con T của E sao cho (V,T) vẫn liên thông và tổng Σ l(e) (e Є E) là nhỏ nhất. Vấn đề: Chứng minh (V,T) là một cây. “Cây bao trùm nhỏ nhất” 49
  49. Một số khái niệm Một tập cạnh là: - một giải pháp nếu nó tạo một cây bao trùm - một tiềm năng nếu nó không chứa xích - một tập tiềm năng là một triển vọng nếu có thể thêm cạnh vào nó để đạt một giải pháp tối ưu Một cạnh “nối” một tập đỉnh nếu đúng một đỉnh của nó nằm trong tập đỉnh này 50
  50. Mệnh đề: Cho đồ thị vô hướng liên thông G=(V,E). Mỗi cạnh e Є E có độ dài l(e). Cho B là một tập con (thực) của V. Cho T là một tập cạnh triển vọng sao cho không cạnh nào của T nối B. Cho e là một cạnh có độ dài min của B. Ta có: T U {e} là một triển vọng. 51
  51. Thuật toán Kruskal (ý tưởng) - Lúc đầu T rỗng - Tại mỗi thời điểm (V,T) là một hợp rời các thành phần liên thông (tplt): trong mỗi tplt, các cạnh của T lập thành một cây bao trùm nhỏ nhất. - Cuối cùng: chỉ còn một tplt, và T là cây bao trùm nhỏ nhất của đồ thị G. 52
  52. - Xếp các cạnh của E theo thứ tự tăng dần - Nếu một cạnh nối hai tplt, thêm vào T - Nếu không, bỏ đi, xét cạnh tiếp theo 53
  53. Tính đúng đắn Vấn đề: chứng minh tính đúng đắn của thuật toán Kruskal 54
  54. Ví dụ 2 3 1 1 2 6 6 5 4 4 6 3 8 4 5 7 3 4 7 55
  55. Thuật toán Kruskal MST-Kruskal(G,l){ 1. Xếp E theo l tăng; n = # V; T = Ø; 2. Đặt n tplt, mỗi tplt chứa 1 phần tử của V; 3. do{ 4. (u,v) cạnh độ dài min chưa xét đến; 5. if set(u)<> set(v) then{ 6. T = T U (u,v); union(set(u),set(v)); 7. } 8. } while(#T = n-1) 9. return T; 10. } 56
  56. Phân tích 1. Đánh giá độ phức tạp tính toán của thuật toán Kruskal 2. Nếu đồ thị không liên thông, kết quả sẽ thế nào ? 3. Một đồ thị có thể có nhiều cây bao trùm nhỏ nhất. Cây nào được cho bởi thuật toán Kruskal ? 57
  57. Thuật toán Prim (ý tưởng) - Lúc đầu T rỗng và cây B chứa một đỉnh bất kỳ - Tại mỗi thời điểm, T là một cây bao trùm nhỏ nhất của B. Chọn một cạnh (u,v) độ dài min sao cho u Є V\B và v Є B. Thêm u vào B và (u,v) vào T - Cuối cùng: B=V, và T là cây bao trùm nhỏ nhất của đồ thị G. 58
  58. Bài tập 1. Chạy ví dụ t.t. Prim trong hình vẽ đã cho 2. Viết thuật toán Prim 3. Đánh giá độ phức tạp tính toán của t.t. 4. Chứng minh tính đúng đắn của t.t. 5. Một đồ thị có thể có nhiều cây bao trùm nhỏ nhất. Cây nào được cho bởi thuật toán Prim ? 6. Nếu đồ thị không liên thông, kết quả sẽ thế nào ? 59
  59. Đường đi ngắn nhất Bài toán: Cho đồ thị có hướng G=(V,E). Mỗi cạnh e Є E có độ dài l(e). Một đỉnh nguồn s. Tìm đường đi ngắn nhất từ s đến các đỉnh khác của G. 60
  60. Thuật toán Dijkstra (ý tưởng) - Tập S gồm các đỉnh đã xác định đường ngắn nhất từ s - Tập C gồm các đỉnh còn lại - Lúc đầu S = {s} - Tại mỗi thời điểm, chọn trong C đỉnh có khoảng cách từ s min, thêm vào S - Cuối cùng S = V 61
  61. Bổ đề: (đường con của một đường ngắn nhất cũng là đường ngắn nhất) Hệ quả: Ta có thể xây dựng một cây gốc s để đường duy nhất từ s đến mỗi u là đường có khoảng cách min 62
  62. Khai triển ý tưởng - Bảng d: d[u]: khoảng cách min (tạm thời) từ s đến u - Bảng Adj: Adj[u] : các đỉnh liên hệ với u - Bảng l: l[u,v]: độ dài cạnh (u,v) (nếu không có (u,v) thì l[u,v] = ∞ - Bảng p: p[u] là “cha” của u trên đường từ s đến u - Kết quả là một cây gốc s, đường duy nhất từ s đến mỗi u là đường có khoảng cách min 63
  63. Thuật toán Dijkstra Dijkstra(G,l,s){ 1. S= {s}; C = V \ {s}; n= #V; d[s]=0; 2. for u Є C do {d[u] = l[s,u]; p[u] = Null;} 3. while (C≠Ø) do { 4. chọn v Є C để d[v] min; 5. C = C \ {v}; S = S U {v}; 6. for w Є Adj[v] do { 7. if d[w] > d[u]+l[u,v] then { p[w]= v; 8. d[w]= d[v]+l[v,w];}} } 64
  64. Ví dụ 1 50 10 30 2 5 100 5 20 10 4 3 50 65
  65. Tính đúng đắn Chứng minh quy nạp rằng: 1. Nếu u Є S: d[u] là khoảng cách min từ s đến u 2. Nếu u Є C: d[u] là khoảng cách min từ s đến u của các đường chỉ đi qua các đỉnh của S 3. Cuối cùng S = V, d[u] là khoảng cách cần tìm 66
  66. Phân tích thuật toán Độ phức tạp: O(V^2) Nếu đồ thị ít cạnh: O(E lg V) 67
  67. Sắp xếp lịch làm việc Bài toán 1: tối thiểu hóa thời gian chờ đợi: Một máy tính cần phục vụ khách hàng. Thời gian phục vụ khách hàng i la t[i]. Tìm cách xếp khách hàng để tối thiểu hóa tổng thời gian chờ đợi. 68
  68. Thuật toán Ý tưởng: Sắp xếp theo trình tự t[i] tăng. Vấn đề: 1. Chứng minh tính đúng đắn của thuật toán 2. Độ phức tạp của thuật toán 3. Nếu có s máy tính, thuật toán thay đổi thế nào ? 69
  69. Sắp xếp lịch làm việc có lợi nhuận Bài toán: Cho một tập n việc phải làm, mỗi việc trong thời gian đơn vị. Việc i sẽ đem lại lợi nhuận g[i] nếu được thực hiện trước hạn d[i]. Tìm cách thực hiện các công việc để có lợi nhuận cao nhất 70
  70. Ví dụ Dữ kiện i 1 2 3 4 g[i] 50 10 15 30 d[i] 2 1 2 1 Các khả năng Công việc 1,3 2,1 2,3 3,1 4,1 4,3 Lợi nhuận 65 60 25 65 80 45 71
  71. Ý tưởng thuật toán Một tập hợp công việc là tiềm năng nếu có một dãy (tiềm năng) thực hiện mọi công việc của tập này trước thời hạn. Thuật toán: Từng bước một, thêm vào tập công việc một công việc i chưa được xét có g[i] max và tập mới vẫn là tiềm năng. 72
  72. Chạy thuật toán trên ví dụ 1. Chọn việc 1. Tập {1} là tiềm năng 2. Chọn việc 4. Tập {1, 4} là tiềm năng 3. Chọn việc 3. Tập {1, 4, 3} không là tiềm năng. Bỏ việc 3 đi 4. Chọn việc 2. Tập {1, 4, 2} không là tiềm năng. Bỏ việc 2 đi 5. Kết quả tập {1, 4} được chọn. Thực hiện theo thứ tự 4, 1 73
  73. Xác định tập tiềm năng Bổ đề: Cho J là một tập công việc và cho p= {s1,s2, ,sk} là một hoán vị của các việc đó sao cho d[s1]≤d[s2] ≤ ≤d[sk]. Tập J là tiềm năng ≈ dãy p là tiềm năng. 74
  74. Tính đúng đắn của thuật toán Cho I là tập nhận được từ thuật toán Cho J là một tập tối ưu. Chứng minh lợi nhuận của I và của J bằng nhau. 75
  75. Quy ước Ký hiệu: n việc được xếp thứ tự 1,2, ,n để g giảm Tập việc là một bảng j n>0, d[i]>0 Biến chặn 0: d[0]=0; j[0]=0 76
  76. Thuật toán Săp_xếp(d){ d[0]=0; j[0]=0; j[1]=1; k=1; for i=2 to n do{ r=k; while d[j[r]]>max(d[i],r) do r=r-1; if d[j[r]]≤d[i] and d[i]>r then { for (l=k,r+1,-1) do j[l+1]=j[l]; j[r+1]=i; k=k+1;}} return j; } 77
  77. Phân tích thuật toán 1. Kiểm tra thuật toán 2. Tính độ phức tạp của thuật toán 3. Cải tiến cách kiểm tra tập tiềm năng. Viết thuật toán mới với độ phức tạp O(n lg n) 78
  78. Thuật toán định hướng Với một số bài toán tối ưu, thuật toán tìm nghiệm chính xác có độ phức tạp rất lớn. Ta sử dụng các thuật toán đơn giản, tìm nghiệm xấp xỉ. (chú ý rằng trong 1 số trường hợp, t.t.x.x không cho kết quả tối ưu) 79
  79. Tô màu đồ thị Bài toán: Cho một đồ thị vô hướng G=(V,E). Tô màu G là tô màu các đỉnh sao cho hai đỉnh liên thuộc không cùng màu. Tìm cách tô màu sử dụng ít màu nhất. Kết quả đã biết: các thuật oán tối ưu đã biết đều có độ phức tạp là hàm mũ. Mục đích: Tìm thuật toán xấp xỉ. 80
  80. Thuật toán xấp xỉ Thuật toán: 1. chọn 1 màu và 1 đỉnh bất kì, tô màu đỉnh đó. 2. xét các đỉnh còn lại, đỉnh nào tô được màu vừa chọn thì tô 3. nếu còn lại một số đỉnh, quay lại bước 1 81
  81. Đánh giá Cho đồ thị G, p là một hoán vị các đỉnh của G, c(p) là số màu nhận được bởi t.t.x.x, c là số màu tối ưu. Ta có 1. Tồn tại một hoán vị p để c(p)=c 2. Với mọi a>0, tồn tị G, p để c/c(p) < a Như vậy t.t.x.x có thể đạt tối ưu, và cũng có thể “xấu” tùy ý. 82
  82. Người đưa hàng Bài toán: Cho một đồ thị có hướng, các cạnh có độ dài. Tìm một chu trình ngắn nhất bắt đầu và kết thúc tại một đỉnh, và đi qua mỗi đỉnh còn lại đúng một lần. G=(V,E), V={1,2, ,n}, L[i,j]: độ dài cạnh 83
  83. Thuật toán xấp xỉ Ở mỗi bước, chọn một cạnh ngắn nhất chưa được xét thỏa mãn: ◼ Không tạo nên một chu trình với các cạnh đã chọn (trừ trường hợp cạnh cuối cùng) ◼ Không là cạnh thứ 3 liên hệ với cùng một đỉnh. 84
  84. Ví dụ đến j= 2 3 4 5 6 Từ i= 1 3 10 11 7 25 2 6 12 8 26 3 9 4 20 4 5 15 5 18 Các cạnh được chọn là: 12, 35, 45, 23, 46, 16, tạo chu trình (1,2,3,5,4,6,1), độ dài 58. Kết quả này không tối ưu (56 là tối ưu) 85
  85. Chương 4: Phương pháp “chia để trị” I. Giới thiệu chung II. Xác định ngưỡng III. Phương pháp “phân đôi” IV. Sắp xếp “xen kẽ”. Sắp xếp nhanh V. Số học các số nguyên lớn VI. Nhân ma trận VII. Giới thiệu về mật mã 86
  86. Giới thiệu chung (divide and conquer algorithms) Ý tưởng: để giải quyết một bài toán, 1. chia ra làm nhiều phần nhỏ hơn, 2. giải quyết từng phần độc lập, 3. sau đó từ các kết quả này, xây dựng kết quả của bài toán ban đầu. Viêc giải quyết các phần nhỏ hơn này có thể thực hiên một cách đệ qui. 87
  87. Thuật toán sinh Thuật_toán DAC(x){ //t.t. này cho kết quả y ứng với đầu vào x if (x đủ nhỏ) then return base(x); chia x thành x_1, x_2, , x_k; for (i=1 to k) do y_i = DAC(x_i); hợp các y_i lại để tìm ra y; return y; } 88
  88. Bài toán tìm kiếm Bài toán: Cho bảng T[1 n] các số được xếp tăng dần. Cho số x. Tìm phần tử trong T có giá trị x Thuật toán đơn giản: while (T[i]≤x) do if (T[i]=x) then return i; else i=i+1; Độ phức tạp: O(n) 89
  89. Phương pháp “phân đôi” funtion dicto (T[i j],x){ if (i=j) then { if (T[i]=x) then return i; else return “không có”; else { k=(i+j+1)/2; if (x < T[k]) then return dicto(T[i k-1],x); else return dicto(T[k j],x); } } Độ phức tạp : ? 90
  90. Sắp xếp xen kẽ (Merge sort) Ý tưởng: Để xếp bảng T: 1. Chia T thành 2 bảng độ dài bằng nhau 2. Sắp xếp mỗi bảng con này 3. Từ hai bảng con đã sắp, xếp xen kẽ lại để được bảng T sắp xếp Chú ý: bước 2 được thực hiện đệ qui 91
  91. Thuật toán Merge-sort Merge-Sort(A,p,r){ 1. if p < r then { 2. q = [(p+r-1)/2]; 3. Merge-Sort(A,p,q); 4. Merge-Sort(A,q+1,r); 5. Merge(A,p,q,r); } } 92
  92. Phân tích thuật toán Đây là một thuật toán chia để trị. Chia: bước 2: θ(1) Trị: bước 3 và 4: 2T(n/2) Hợp lại: bước 5: θ(n) Tổng kết: T(n) = θ(1) nếu n=1 2T(n/2) + θ(n) nếu n >1 93
  93. Sắp xếp nhanh (quicksort) Chia: Bảng T[p r] được chia thành 2 phần T[p q] và T[q+1 r] sao cho mọi phần tử trong bảng 1 nhỏ hơn mọi phần tử bảng 2 Trị: Mỗi bảng con được sắp xếp đệ qui Hợp: Vì mỗi bảng đã đúng vị trí. Kết thúc. 94
  94. Thuật toán quicksort Quicksort(A,p,r){ 1. if (p<r) then { 2. q=Partition(A,p,r); 3. Quicksort(A,p,q); 4. Quicksort(A,q+1,r); } } 95
  95. Chia đôi bảng (Partition) Ví dụ: 5 3 2 6 4 1 3 7 5 3 2 6 4 1 3 7 3 3 2 6 4 1 5 7 3 3 2 6 4 1 5 7 3 3 2 1 4 6 5 7 96
  96. Partition Partition(A,p,r){ 1. x = A[p]; 2. i = p-1; j = r+1; 3. while (i<j) do { 4. repeat j = j-1 until A[j] ≤ x; 5. repeat i = i+1 until A[i] ≥ x; 6. if (i<j) then exchange (A[i], A[j]); 7. else return j; 8. } } 97
  97. Phân tích thuật toán 1. Partition(A,p,r): O(r-p) 2. Trường hợp xấu nhất: mỗi lần chia bảng ta được 1 bảng 1 phần tử, và một bảng tất cả phần tử còn lại: T(n) = T(n-1) + θ(n). Như vậy: T(n) = θ(n^2) 3. Trường hợp tốt nhất: bảng luôn phân đôi đều: T(n) = 2 T(n/2) + θ(n). Như vậy: T(n) = θ(n lg n) Câu hỏi: Cho ví dụ về trường hợp xấu nhất, tốt nhất. 98
  98. Độ phức tạp trung bình 99
  99. Số học các số nguyên lớn Phép nhân hai số nguyên cực lớn: Bài toán: Cho u và v là hai số nguyên lớn, giả sử mỗi số biểu diễn bởi n chữ số. Tìm thuật toán nhân u và v hiệu quả. 100
  100. Phân tích vấn đề n u a b v c d n u v = 10^{2s} ac + 10 ^s (ad+bc) + bd (s = n/2) 101
  101. Phân tích vấn đề (tiếp) Nhận xét: r = (a+b)(c+d) = ac+(ad+bc)+bd Thay vì tính 4 phép nhân ac, bd, ad, bc, Ta tính ac, bd, và r 102
  102. Thuật toán nhân Mult(u,v){ 1. n= min(size(u), size(v)); 2. if (n bé) then return uv; 3. else { s = n/2; 4. a= u div (10^s), b= u mod 10^s; 5. c= v div (10^s), d= v mod 10^s; 6. r= Mult(a+b,c+d); 7. p=Mult(a,c); q= Mult(b,d); 8. t = r-p-q; 9. return(p*10^{2s} + t*10^s+q); 10. } } 103
  103. Độ phức tạp thuật toán T(n) = 3 T(n/2)+ θ(n) T(n) = θ(n ^{lg 3}) ≈ θ(n^{1,59}) Bài tập: Thay đổi thuật toán để làm việc với các biểu diễn nhị phân và các phép toán trong biểu diễn nhị phân 104
  104. Nhân hai ma trận Bài toán: Cho 2 ma trận A, và B, kích cỡ n*n. Tìm ma trận tích C = A*B. Thuật toán đơn giản: T(n) = θ(n^3) 105
  105. Thuật toán Strassen Ý tưởng: a1 a2 b1 b2 A = B = a3 a4 b3 b4 m2+m3 m1+m2+m5+m6 A*B = m1+m2+m4-m7 m1+m2+m4+m5 106
  106. Tính m_i m1 = (a3+a4-a1)(b4-b2+b1) m2 = a1 *b1 m3 = a2* b3 m4= (a1-a3)(b4-b2) m5= (a3+a4)(b2-b1) m6 = (a2-a3+a1-a4)*b4 m7 = a4*(b1+b4-b2-b3) 107
  107. Độ phức tạp tính toán T(n) = 7 T(n/2) + θ(n^2) ≈ θ(n^{2,81}) 108
  108. Giới thiệu về mật mã Vấn đề: A và B muốn trao đổi thông tin sao cho C đọc được nhưng không hiểu được. Giải quyết: A, B chọn số nguyên tố lớn p và số g, 2 ≤ g ≤ p-1. A chọn số A, B chọn số B ≤ p. A gửi số a, B gửi số b. C biết đươc p,g,a,b. Nhưng không biết x. a A: a= g^A mod p B: g^b mod p b A: x= b^A mod p = B: y = a^B mod p 109
  109. Thuật toán logarithm rời rạc Muốn tìm x, C phải tìm A (hoặc B). Muốn tìm A, biết a, C phải tính logarithm logD(g,a,p){ A=0; x=1; do { A=A+1; x = xg;} while ((a= x mod p) or (A=p)) return A; } 110
  110. Phân tích thuật toán Trung bình: logD có p/2 vòng lặp while. Nếu p rất lớn (vài chục chữ số) thì t.t. chạy rất lâu. Chưa biết t.t. nào cải thiện hàm logD 111
  111. Thuật toán Mũ (exponentiation) A phải tính g^A mod p Thuật toán đơn giản: expD(g,A,p){ a=1; for (i=1 to A) do a = a*g mod p; return a; } 112
  112. Bài tập: Viết thuật toán “chia để trị” để tính hàm mũ theo thời gian O(lg p) 113
  113. Chương 5: Phương pháp qui hoạch động I. Giới thiệu chung II. Nhân một dãy các ma trận III. Các đường đi ngắn nhất IV. Người đưa hàng 114
  114. Giới thiệu chung So sánh với phương pháp “chia để trị”: - Chia thành các phần nhỏ hơn - Thực hiện độc lập từng phần - Hợp các kết quả nhỏ lại. Vấn đề: - nếu có nhiều phần nhỏ giống nhau, liên quan đến nhau - => sử dụng kết quả đã tính: lập bảng lưu trữ dần các kết quả của các phần con 115
  115. Chia để trị: từ trên xuống: nhìn ngay vào vấn đề lớn, chia nhỏ ra, trị phần con Quy hoạch động: từ dưới lên: bắt đầu từ các trường hợp đơn giản, nhỏ, xây dựng dần lên, đến bài toán tổng kết cuối cùng. 116
  116. Ví dụ nhỏ: phép tính tổ hợp Tính C(n,k) = n!/(n-k)!k! Thuật toán đơn giản: function C(n,k){ if (k=0 ou k=n) then return 1; else return C(n-1,k-1)+C(n,k-1); } Câu hỏi: tính độ phức tạp tính toán của thuật toán này 117
  117. Ví dụ nhỏ: phép tính tổ hợp (tiếp) Cải thiện thuật toán: dùng tam giác Pascal 0. 1 1. 1 1 2. 1 2 1 3. 1 3 3 1 4. 1 4 6 4 1 5. 1 5 10 10 5 1 Câu hỏi: Viết thuật toán bằng cách dùng bảng lưu trữ kết quả, tính độ phức tạp tính toán của t.t. đó. 118
  118. Nhân một dãy các ma trận Vấn đề: Ta muốn nhân một dãy các ma trận M= M1xM2x xMn Có nhiều cách đặt các dấu ngoặc để nhân dần 2 ma trận. Chúng ảnh hưởng nhiều đến thời gian tính toán. Ví dụ: M=ABCD, A=(10,2); B=(2,100); C=(100,3); D=(3,20) M=((AB)C)D: 10x2x100+2x100x3+10x3x20=3200 phép x M=(AB)(CD): 10x2x100+100x3x20+10x100x20 = 28000 M=(A(BC))D: 2x100x3 +10x2x3 +10x3x20 = 1260 M=A((BC)D): 2x100x3 +2x3x20 +10x2x20 = 1120 M=A(B(CD)): 100x3x20+2x100x20 +10x2x20 = 10400119
  119. Ý tưởng tìm cách tính Số các cách tính M (số Catalan): C(n) = 1/n x C(2n-2,n-1) = Ω (4^n/n^2) Không thể xét tất cả các trường hợp Ý tưởng: Nếu để tính M, cắt khúc ở i là tối ưu Thì để tính M1x xMi và M(i+1)x xMn, ta cũng tính cách tối ưu. => Lập bảng a[i,j] để lưu trữ số phép x tối ưu khi tính Mix xMj 120
  120. Ý tưởng tìm cách tính (tiếp) Chiều các ma trận: d[0 n], Mi=(d[i-1],d[i]) Xây dựng a[i,j] theo từng đường chéo. Đường chéo s: a[i,j]: j-i=s. s=0: a[i,i]=0, i= 1,2 ,n s=1: a[i,i+1]=d[i-1]d[i]d[i+1], i=1,2, ,n-1 1<s<n: i =1,2, ,n-s a[i,i+s]=min (a[i,k]+a[k+1,i+s]+d[i-1]d[i]d[i+1]) i≤k≤i+s-1 121
  121. Ý tưởng tìm cách tính: ví dụ M=ABCD, A=(10,2); B=(2,100); C=(100,3); D=(3,20). s=1:a[12]=2000,a[23]=600,a[34]=18000 j = 1 2 3 4 i=1 0 2000 ? ? 2 0 600 ? 3 0 18000 4 0 122
  122. Bài tập 1. Viết thuật toán tính bảng a 2. Tính độ phức tạp tính toán 3. Thay đổi thuật toán thế nào để nhận được không chỉ a[1,n] mà còn cả cách tính tích M tối ưu nhất. 123
  123. Các đường đi ngắn nhất Bài toán: Cho đồ thị có hướng G=(V,E). Mỗi cạnh e Є E có độ dài l(e). Tìm đường đi ngắn nhất giữa các cặp đỉnh của G. Ký hiệu: V={1,2, ,n} L[i,i] = 0, L[i,j] = l(e) nếu e=(i,j) L[i,j] = ∞ nếu không có cạnh (i,j) . 124
  124. Ý tưởng thuật toán 1. Nếu k nằm trên 1 đường đi ngắn nhất từ i đến j thì đoạn từ i đến k và từ k đến j cũng là những đường đi ngắn nhất. 2. Xây dựng D[i,j] độ dài min từ i đến j: 1. Lúc đầu: D=L 2. Sau bước thứ k, D[i,j] là độ dài min từ i đến j (mà chỉ đi qua các đỉnh 1,2, ,k) 3. Sau n bước, D[i,j] là độ dài min từ i đến j. 125
  125. Ví dụ 0 5 ∞ ∞ 15 D0=L= 50 0 15 5 1 4 30 ∞ 0 15 15 ∞ 5 0 5 5 50 15 5 0 5 ∞ ∞ D1= 50 0 15 5 30 30 35 0 15 2 3 15 20 5 0 15 0 5 20 10 0 5 20 10 0 5 15 10 D2= 50 0 15 5 D3= 50 0 15 5 D4= 20 0 10 5 30 35 0 15 30 35 0 15 30 35 0 15 15 20 5 0 15 20 5 0 15 20 5 0 126
  126. Thuật toán Floyd Floyd(L){ array D = L; for (k=1 to n) do for (i=1 to n) do for (j=1 to n) do D[i,j]= min(D[i,j],D[i,k]+D[k,j]); return D; } 127
  127. Bài tập 1. Tìm độ phức tạp của thuật toán Floyd 2. Chứng minh tính đúng đắn của thuật toán 3. Nếu muốn biết không chỉ độ dài mà cả đường đi ngắn nhất, phải thêm gì vào thuật toán ? 4. Viết thuật toán xác định xem có đường đi giữa các cặp đỉnh của G. 128
  128. Người đưa hàng Bài toán: Cho một đồ thị có hướng, các cạnh có độ dài. Tìm một chu trình ngắn nhất bắt đầu và kết thúc tại một đỉnh, và đi qua mỗi đỉnh còn lại đúng một lần. G=(V,E), V={1,2, ,n}, L[i,j]: độ dài cạnh. 129
  129. Ý tưởng thuật toán 1. Chu trình bắt đầu từ đỉnh 1. Min chu trình bắt đầu từ 1 = min (L[1,j]+ min đường từ j đến 1) 2. Cho S tập con của V\{1}, i Є V\S: g(i,S)=min (đường từ i đến 1 qua S đúng 1 lần) 3. Min chu trình = g(1, V\{1}) = min(L[1,j]+g(j,V\{1,j})) 2≤j≤n 4. g(i,S)= min (L[i,j] + g(j,S\{j})) jЄS 5. g(i,Ø)=L[i,1], i=2,3, ,n 130
  130. Ví dụ 0 10 15 20 10 5 0 9 10 1 5 2 L = 6 13 0 12 10 8 8 8 9 0 20 8 13 9 6 15 1. Tính g(j,Ø); j= 2,3,4 4 12 3 2. Tính g(j,S) với |S|=1;j=2,3,4 3. Tính g(j,S) với |S|=2;j=2,3,4 9 4. Tính g(1,{2,3,4}) 131
  131. Bài tập 1. Viết thuật toán tính chu trình ngắn nhất theo ý tưởng đã trình bày. 2. Tính toán độ phức tạp và bộ nhớ cần cho t.t. 3. Tính xem thực chất có bao nhiêu giá trị g(i,S) cần phải tính ? 4. Có thể cải thiện t.t. trên để tiết kiệm số lần tính g(i,S) không (mỗi giá trị tính đúng 1 lần) ? 132
  132. Hàm nhớ Thuật toán đơn giản tính g(i,S) function g(i,S){ if (S=Ø) then return L[i,1]; min = ∞; for (jЄS) do { d=L[i,j]+g(j,S\{j}); if (d<min) then min =d;} return min; } Số lần gọi các hàm g là Ω((n-1)!), nhiều giá trị được tính lại nhiều lần 133
  133. Hàm nhớ (tiếp) 1. Lập một bảng gtab[.,.] để nhớ những giá trị g[i,S] đã được tính. 2. Khi gọi hàm g(i,S), sẽ kiểm tra xem g(i,S) đã được tính chưa 3. Lúc đầu gtab[i,S] = -1 với mọi i, S. function g(i,S){ if (S=Ø) then return L[i,1]; if (gtab[i,S]≥0) then return gtab[i,S]; min = ∞; for (jЄS) do { d=L[i,j]+g(j,S\{j}); if (d<min) then min =d;} gtab[i,S]= min; return min; } 134
  134. So sánh 1. Thời gian t.t. đơn giản: n! 2. Thời gian t.t. cải tiến: n^2 2^n 3. Bộ nhớ t.t. cải tiến: n 2^n n n! n^2 2^n n 2^n 5 120 800 160 10 3628800 102400 10240 15 1,3 x 10^12 7372800 491520 20 2,4 x 10^18 419430400 2971520 135
  135. Chương 6: Thuật toán trên đồ thị I. Giới thiệu chung II. Khám phá cây III. Khám phá theo chiều rộng IV. Khám phá theo chiều sâu V. “Branch and bound” 136
  136. Giới thiệu chung 1. Đồ thị biểu diễn nhiều vấn đề: 1. Mạng, trò chơi, sơ đồ, 2. Cấu trúc dữ liệu: đỉnh là một số bit bộ nhớ, cạnh là các con trỏ, 2. Biểu diễn đồ thị, có nhiều cách: 1. Ma trận: a[i,j]=1 nếu có cạnh (i,j), =0 nếu không 2. Dãy liên hệ: Adj[i] là một dãy các cạnh được nối với i, i là các đỉnh của đồ thị. 137
  137. Khám phá cây Xét các cây nhị phân, có 3 cách khám phá: 1. Thứ tự trước (prefix) 2. Thứ tự giữa (infix) 3. Thứ tự sau (suffix) Visit_prefix (r){ //r là gốc của cây print (r.value); if (r.left Null) then visit_prefix(r.right); } Chứng minh độ phức tạp tính toán của t.t. là O(n) 138
  138. Khám phá theo chiều rộng (Breadth-first search) 1. Chọn một đỉnh nguồn s, và thăm các đỉnh khác theo thứ tự từ gần đến xa s 2. Thăm u: thăm tất cả các lân cận của u, sau đó mới thăm lân cận của các đỉnh này 3. Xây dựng cây có gốc s. 4. Tô màu các đỉnh: 1. Lúc đầu tất cả màu trắng 2. Bắt đầu thăm u, tô u màu vàng 3. Nếu đã thăm mọi lân cận của u, tô u màu đỏ 5. Một xâu nhớ (FIFO) Q lưu trữ các đỉnh vàng 139
  139. Ví dụ 140
  140. Thuật toán BFS (G,s){ for (u Є V\{s}) do { color[u]= T ; d[u]=∞; p[u]=Null;} color[s]= V ; d[s]=0; p[s]=Null; Q={s}; while (Q<>Ø) do { u=head(Q); for (v Є Adj[u]) do{ if (color[v]=T) then { color[v]=V; d[v]=d[u]+1; p[v]=u; add(Q,v);}} sup(Q); color[u]=Đ;} } 141
  141. Phân tích 1 Định lý: Nếu đồ thị liên thông. Sau BFS, ta nhận được cây gốc s và đường đi từ s đến u là 1 đường đi ngắn nhất từ s đến u trong G. 2 Tính độ phức tạp và bộ nhớ cho t.t. BFS 142
  142. Khám phá theo chiều sâu (Deep-first search) 1. Thăm u, rồi thăm 1 lân cận v của u, rồi thăm 1 lân cận của v, 2. Hàm thăm này được gọi đệ qui. 3. Sau mỗi lệnh thăm v lân cận của u, nếu u còn lân cận nào, thì lại thăm, 4. Nếu bắt đầu từ s, sau khi thăm s, còn các đỉnh, ta lại chọn một đỉnh mới để thăm. 5. Xây dựng được một rừng. 143
  143. Ký hiệu 1. d[u]: thời điểm bắt đầu thăm u 2. f[u]: t.đ. Kết thúc thăm u 3. p[u]: cha của u 4. color[u] =T trước d[u], = V đang thăm u = Đ sau f[u] 144
  144. Ví dụ 145
  145. Thuật toán DFS(G){ for (u Є V) do { color[u]=T; p[u]=Null;} time=0; for (u Є V) do if (color[u]=T) then DFS-visit(u); } 146
  146. Thuật toán (tiếp) DFS-visit(u){ color[u]=V; d[u]=time=time+1; for (vЄAdj[u]) do { if (color[v]=T) then { p[v]=u; DFS-visit(v);} } color[u]=Đ; f[u]=time=time+1; } 147
  147. Phân tích 1. Tính độ phức tạp và bộ nhớ cần cho DFS 2. Định lý: Các ngoặc (d[u],f[u]) lập thành một bộ ngoặc đơn tốt (hai ngoặc hoặc là trong nhau hoặc là rời nhau) 148
  148. Sắp xếp topology Bài toán: Cho G là đồ thị có hướng, không chu trình. Một sắp xếp topology của G là một cách xếp tuyến tính các đỉnh của G sao cho i trước j nếu (i,j) là cạnh. Ứng dụng: - Sắp xếp các công việc thỏa mãn một số thứ tự. - Biểu diễn tập có thứ tự bộ phận 149
  149. Thuật toán sắp xếp topology Topological-Sort(G){ DFS(G); Xếp vào theo thứ tự f[u] giảm } Vấn đề: chứng minh tính đúng đắn của t.t. và tính độ phức tạp. 150
  150. Ví dụ 151
  151. Thành phần liên thông mạnh Định nghĩa: Đồ thị có hướng là liên thông mạnh nếu giữa hai đỉnh luôn có đường đi. Một đồ thị có hướng bất kỳ được phân thành các t.p.l.t.m., mỗi t.p. là một đồ thị con lớn nhất liên thông mạnh. Bài toán: phân tích G thành các t.p.l.t.m. 152
  152. Thuật toán tính các t.p.l.t.m Tpltm (G){ 1. DFS(G) để tính f[u]; 2. Tính G’ 3. DFG(G’), các đỉnh của G’ được xếp theo f giảm 4. Mỗi cây trong rừng từ bước 3 là một t.p.l.t.m } G’=(V,E’); E’={(u,v): (v,u) Є E} Vấn đề: chứng minh tính đúng đắn của t.t. và tính độ phức tạp của nó. 153
  153. Ví dụ 154
  154. Branch and bound So sánh các cách tìm kiếm trong đồ thị: 1. Theo chiều rộng: thăm hết các lân cận + một FIFO chứa các đỉnh đang thăm 2. Theo chiều sâu: thăm hết các con đường + một FILO chứa các đỉnh đang thăm 3. B.A.B.: thăm các đỉnh hứa hẹn nhất + một dãy chứa các đỉnh đang thăm 155
  155. B.A.B: người đưa hàng Bài toán: Cho một đồ thị có hướng, các cạnh có độ dài. Tìm một chu trình ngắn nhất bắt đầu và kết thúc tại một đỉnh, và đi qua mỗi đỉnh còn lại đúng một lần. G=(V,E), V={1,2, ,n}, L[i,j]: độ dài cạnh. 156
  156. Ví dụ: ý tưởng 0 14 4 10 20 14 0 7 8 7 L= 4 5 0 7 16 11 7 9 0 2 18 7 17 4 0 1. Tìm chu trình đơn ngắn nhất từ đỉnh 1 đến đỉnh 1 2. Xây dựng cây gốc (1). 3. Mỗi nốt là một đường từ 1: (1,3), (1,3,4), 4. Các con của mỗi nốt là các đường thêm vào một đỉnh 5. Với mỗi nốt, tính cận dưới của chu trình đi qua đường tương ứng 157
  157. Ví dụ (tiếp): cách tính cận dưới Tính cận dưới (inf): 1. Khoảng cách L[i,j] chia 2: một nửa đường từ i, một nửa đường đến j 2. inf từ i = min của các đường từ i 3. inf qua i = min (từ i) + min (đến i) 4. inf của nốt = tổng các inf để tạo ra chu trình qua nốt 158
  158. Ví dụ (tiếp): tính cụ thể 1. inf(1)=inf(từ 1) + inf(đến 1) + inf(qua 2)+inf(qua 3)+inf(qua 4)+inf(qua 5) = 2+2+6+4+3+3=20 159
  159. Ví dụ (tiếp): xây dựng cây 1 inf 20 1,2 1,3 1,4 1,5 inf 31 inf 24 inf 29 inf 41 1,3,2 1,3,4 1,3,5 1,4,2 1,4,3 1,4,5 inf 24 inf 30,5 inf 40,5 inf 40 inf 41,5 inf 29 1,4,5,2 1,4,5,3 1,3,2,4 1,3,2,5 =1,4,5,2,3,1 =1,4,5,3,2,1 =1,3,2,4,5,1 =1,3,2,5,4,1 value=30 value=48 value=37 value=31 160
  160. Chương 7: Giới thiệu về phương pháp xác suất I. Giới thiệu chung II. Phân loại các thuật toán xác suất III. Thuật toán xác suất số IV. Thuật toán Sherwood V. Thuật toán Las Vegas VI. Thuật toán Monte Carlo 161
  161. Giới thiệu chung ◼ Khái niệm: Thuật toán xác xuất là thuật toán sử dụng đầu vào là các số ngẫu nhiên. ◼ Nhận xét: - Đầu vào này phải hữu ích - Các số này là “giả ngẫu nhiên” 162
  162. Ví dụ Thuật toán sắp xếp Quicksort: - Phần tử so sánh được chọn ở đầu bảng: - Độ phức tạp xấu nhất là 0(n^2) - Độ phức tạp trung bình là 0(n lg n) Vấn đề: nếu bảng đã gần xếp đúng, không hiệu quả. Giải quyết: Chọn phần tử so sánh một cách ngẫu nhiên trong bảng. 163
  163. Phân loại các thuật toán xác suất Thuật toán xác suất số: - Dùng trong việc tính toán xấp xỉ các bài toán số. - Độ chính xác trung bình tỷ lệ với thời gian chạy - Dùng trong các ví dụ: tính toán thời gian chay TB của một hệ phức tạp, cách tính chính xác là rất phức tạp (hoặc không thể) 164
  164. Phân loại các thuật toán xác suất (tiếp) Thuật toán Monte Carlo: - Có thể dùng trong các bài toán quyết định: đúng/sai, phân tích thừa số ng. tố, - Luôn cho câu trả lời rõ ràng nhưng - Kết quả có thể không đúng - Xác xuất thành công tỷ lệ với thời gian chạy 165
  165. Phân loại các thuật toán xác suất (tiếp) Thuật toán Las Vegas: - Không bao giờ cho câu trả lời sai - Có thể không cho câu trả lời - Xác xuất thành công tỷ lệ với thời gian chạy - Dù vấn đề nào, xác xuất hỏng cũng có thể nhỏ tùy ý * Cho trả lời chính xác với độ phức tạp trung bình có giới hạn 166
  166. Phân loại các thuật toán xác suất (tiếp) Thuật toán Sherwood: - Luôn cho câu trả lời, trả lời luôn đúng - Dùng trong các bài toán đã có thuật toán, với ĐPTTB nhỏ và ĐPT xấu nhất lớn - Biễn ngẫu nhiên là để giảm sự khác nhau giữa hai trường hợp này 167
  167. Thuật toán Monte Carlo Bài toán ví dụ: Thử xem một số có nguyên tố hay không. Ý nghĩa: trong mật mã cần tìm các số nguyên tố lớn. 168
  168. Thuật toán đơn giản Tính nguyên tố (n) { while (i< n) do { if (n chia hết cho i) return sai; i = i+1; } return đúng; } Nhận xét: cho I chạy đến sqrt(n) - Để thử tính chia hết: thời gian nhiều. 169
  169. Phép thử Miller Rabin Nguyên tắc: a) n nguyên tố, a a^{n-1} = 1 (mod n) b) n nguyên tố, a a = 1, -1 (mod n) Câu hỏi: viết thuật toán test (n,a) thử hai điều kiên trên. Độ p.t.t.t = ? 170
  170. Thuật toán Miller-Rabin M-R(n) { i=1; chọn a ngẫu nhiên < n; while (i<k and test (n,a)=false) do { chọn a ngẫu nhiên < n; i = i+1;} return test(n,a); } - Số lần chọn các số ngẫu nhiên a là k lần. - Tính độ p.t.t.t 171
  171. Xác xuất của thuật toán Tính chất: Nếu n lẻ, thì có ít nhất ¾ số a < n sẽ cho kết quả test(n,a)= true nếu n không nguyên tố. Như vậy sau k lần thì xác xuất không tìm thấy a cho test(n,a)=true là (1/4)^k. Và ta có thể cho xac suất này nhỏ tùy ý. 172
  172. Thuật toán Las-Vegas Bài toán: Bầu một người chủ. Có n người, cần chọn ra một người. Đòi hỏi: các lần chạy t.t. khác nhau, chọn ra những người khác nhau. Ý nghĩa: Trong bài toán mạng, tránh tình trạng tắc nghẽn khi các máy cùng đến một lúc. 173
  173. Thuật toán 1. Mỗi người chọn một số ngẫu nhiên từ 1 đến m (số người chọn) 2. Nếu không có ai chọn số 1, quay về bước 2. 3. Nếu có ít nhất 2 người chọn số 1, thì những người này tiếp tục, quay về bước 1. 4. Nếu chỉ có 1 người chọn số 1 thì người này là chủ. 174
  174. Tính chất của thuật toán - Thuật toán không chắc chắn là sẽ dừng - Nhưng nếu dừng nó luôn cho kết quả đúng. 175
  175. Phân tích thuật toán Xác xuất để có k người vào vòng 2 là: p(n,k) = C^k_n (1/n)^k (1-1/n)^(n-k) P(n,0) = (1-1/n)^n. Xác xuất để vòng 1 lặp l lần là (1-1/n)^{nl} Xác xuất để t.t. không dừng là = 0 176
  176. Chương 8: Về độ phức tạp tính toán I. Cây quyết định II. Qui dẫn III. Giới thiệu về NP- đầy đủ 1) Lớp P và NP 2) Một số bài toán NP- đầy đủ 3) Định lý Cook 4) Một số qui dẫn 177
  177. Cây quyết định Vấn đề: Có một bảng n phần tử cần được sắp xếp tăng dần. Cần tối thiểu bao nhiêu phép so sánh để thực hiện thuật toán ? Chú ý: chỉ tính so sánh các phần tử, không tính so sánh các chỉ số. 178
  178. Định nghĩa cây quyết định Định nghĩa: một cây quyết định là một cây nhị phân có hướng và được dán nhãn, - mỗi đỉnh trong chứa một phép so sánh 2 phần tử cần được xếp - Mỗi lá chứa một hoán vị các phần tử Cho một thứ tự, một đường đi trong cây bắt đầu từ gốc, và đặt các câu hỏi mà nó gặp: nếu trả lới “đúng” thì rẽ trái, nếu “không” thì rẽ phải. Đường kết thúc ở một lá. Lá này chứa kết quả ứng với thứ tự vào. 179
  179. Tính chất - Một cây quyết định là đúng để sắp xếp n phần tử nếu với mọi thứ tự vào đều cho ra kết quả đúng cới thứ tự đó. - Một cây quyết định là gọn nếu không có đường nào mâu thuẫn, tức là mọi lá đều nhận được từ gốc qua một dãy các quyết định đúng. 180
  180. Ví dụ cây quyết định sắp 3 số A<B B<C B<C A < B < C A<C A<C C ≤ B ≤ A A < C ≤ B C ≤ A< B B ≤ A <C B < C < A 181
  181. Thuật toán Mọi cây quyết định đúng để sắp xếp n số sẽ cho một thuật toán tương ứng để sắp xếp n số đó. Bài tập: 1. Viết thuật toán tương ứng với cây quyết định đã cho. 2. Vẽ cây quyết định gọn tương ứng cho các t.t. sắp xếp chèn vào, lựa chọn, xen kẽ với 3 số. 182
  182. Nhận xét - Vẽ cây quyết định cho thuật toán sắp xếp vun đống cho 3 số. - Nhận xét gì về cây này: có bao nhiêu lá ? Có các phép so sánh thừa hay không ? Cây có gọn không ? 183
  183. - Nhận xét gì về độ cao của các cây quyết định ? - Độ dài lớn nhất từ đỉnh tới một lá nói lên điều gì ? 184
  184. Thời gian tối đa Bổ đề 1: Mọi cây nhị phân k lá có độ cao ít nhất là bằng [lg k] Bổ đề 2: Mọi cây quyết định đúng để xếp n số có ít nhất k! lá Định lý: Mọi thuật toán để xếp n số bằng các phép so sánh sẽ mất thời gian là Ω(n lg n) trong trường hợp xấu nhất 185
  185. Thời gian trung bình Định nghĩa: độ cao trung bình của cây nhị phân A là tổng độ sâu của các lá chia cho số lá Bổ đề 3: Mọi cây nhị phân k lá có độ cao trung bình ít nhất là bằng [lg k] Định lý: Mọi thuật toán để xếp n số bằng các phép so sánh sẽ mất thời gian trung bình là Ω(n lg n). 186
  186. Bài tập 1. Tìm công thức chính xác cho số các phép so sánh trong trường hợp xấu nhất của t.t. xếp chèn vào và lựa chọn. 2. Tìm công thức chính xác cho số các phép so sánh tính trung bình của t.t. xếp chèn vào và lựa chọn. 3. So sánh hai kết quả này. 187
  187. Một ví dụ nhỏ function sort(T[1 n]){ i = min (T); j = max(T); table C[i j]=0; for (k=1 to n) do C[T[k]]=C[T[k]]+1; k=1; for (p=i to j) do for (q=1 to C[p]) do {T[k]=p; k=k+1;} } 188
  188. Câu hỏi 1. Chạy t.t. trên cho bảng T[1 10] = {3,1,4,1,5,9,2,6,5,3} 2. Tính xem để xếp n số, t.t. này thực hiện bao nhiêu phép so sánh giữa các số 189
  189. Thời gian đa thức: Vấn đề trừu tượng Vấn đề trừu tượng Q: là một quan hệ hai ngôi trên tập các trạng thái I và tập các lời giải S. Bài toán quyết định: là có một lời giải Co’/Không Bài toán tối ưu: có một đại lượng cần cực tiểu (đại) hóa có thể đưa về bài toán quyết định: đặt một giá trị biên. 190
  190. Mã hóa - Một mã hóa của một tập S các đối tượng trừu tượng là một ánh xạ e từ S vào các dãy nhị phân. - Một t.t. máy tính giải một vấn đề trừu tượng sẽ nhận một mã hóa của một trạng thái như là đầu vào. - Vấn đề cụ thể: là vấn đề mà các trạng thái là các dãy nhị phân. 191
  191. Thuật toán thời gian đa thức Thuật toán giải một vấn đề cụ thể trong thời gian O(T(n)) nếu: mỗi đầu vào i có độ dài n, t.t. cho kết quả trong thời gian = O(T(n)). Một vấn đề cụ thể giải được trong thời gian đa thức nếu tồn tại t.t. giải nó trong t.g. O(n^k), k hằng số. Lớp P = {vấn đề cụ thể giải được trong t.g.đ.t.} 192
  192. Mã hóa chuẩn - Một vấn đề trừu tượng có thể có nhiều cách mã hóa thành vấn đề cụ thể. - Mã hóa chuẩn: các số tự nhiên theo biểu diễn (tương đương đa thức với) nhị phân. - Một tập phần tử được mã theo dãy các mã của các phần tử. - Đồ thị, công thức, được mã tương tự * Ta có thể xét vấn đề trừu tượng như vấn đề cụ thể 193
  193. Ngôn ngữ Bảng chữ cái A: tập hữu hạn các ký tự. Từ: 1 dãy các chữ cái của A. Một ngôn ngữ L trên A: 1 tập các từ trên A. Từ rỗng: ε Ngôn ngữ rỗng: Ø Ngôn ngữ gồm tất cả các từ trên A: A* 194
  194. Các phép toán trên các ngôn ngữ - Hợp, giao, - phần bù Ḹ = A* \ L - dán (concatenation): L=L1.L2 = {xy: x Є L1, y Є L2} - Bao đóng Kleene: L*={ε} U L U L^2 U L^3 U 195
  195. Bài toán - ngôn ngữ Σ = {0,1}. Bài toán quyết đinh Q  Ngôn ngữ L = {x Є Σ*: Q(x) = 1} Thuật toán A chấp nhận một từ x Є Σ*: nếu với đầu vào x, A cho kết quả A(x) = 1. A loại bỏ x nếu A(x) = 0 Ngôn ngữ L được chấp nhận bởi A:L={x Є Σ*:A(x)=1} L được chấp nhận bởi A trong t.g.đ.t. nếu có hằng k: mọi từ x độ dài n được A chấp nhận trong t.g O(n^k) - Chú ý: nếu x |Є L, A có thể không loai bỏ x, mà chạy không dừng. 196
  196. Ngôn ngữ được quyết định Một ngôn ngữ L được quyết định bởi t.t. A: nếu x thuộc L  A chấp nhận x và x không thuộc L  A loại bỏ x. L được quyết định bởi A trong t.g.đ.t. nếu có hằng k: mọi từ x độ dài n được A quyết định trong t.g O(n^k) 197
  197. Lớp P P = {L ngôn ngữ trên Σ: có t.t. A quyết đinh L trong t.g.đ.t.} Định lý: P = {L ngôn ngữ trên Σ: có t.t. A ch L chấp nhận L trong t.g.đ.t.} 198
  198. Thuật toán kiểm chứng ◼ Thuật toán kiểm chứng: là một t.t. A hai biến, một biến bình thướng là một xâu nhị phân đàu vào x, và một biến là xâu nhị phân y (được gọi là xâu kiểm chứng). ◼ T.t A kiểm chứng x nếu tồn tại xâu kiểm chứng y để A(x,y) =1. ◼ Ngôn ngữ L được kiểm chứng bởi A là: L = {x Є Σ*: tồn tại y Є Σ*: A(x,y)=1 } 199
  199. Lớp NP ◼ Lớp độ phức tạp tính toán NP là lớp các ngôn ngữ được kiểm chứng trong thời gian đa thức. ◼ L Є NP  tồn tại t.t. 2 biến t.g.đ.t. A và hằng số c sao cho: L= {x Є Σ*: tồn tại y Є Σ*, |y|=O(|x|^c): A(x,y)=1 } Ta nói: A kiểm chứng L trong t.g.đ.t. 200
  200. Ví dụ Bài toán: chu trình Hamilton: HAM-CYCLE Є NP 201
  201. Lớp co-NP - L Є co-NP  Σ*\L Є NP - 4 trường hợp có thể xảy ra: 202
  202. Phép qui dẫn ◼ Ngôn ngữ L1 qui dẫn được về ngôn ngữ L2 trong t.g.đ.t. (L1 ≤_P L2) nếu tồn tại một hàm tính được trong t.g.đ.t. f: Σ* -> Σ* sao cho x Є L1  f(x) Є L2 f: hàm qui dẫn T.t. F t.g.đ.t. tính f: t.t. qui dẫn 203
  203. Bài tập 1. Chứng minh rằng quan hệ qui dẫn là một quan hệ thứ tự. 2. Chứng minh bổ đề: Bổ đề: Cho 2 ngôn ngữ L1, L2, nếu L1 ≤ L2 thì L2 Є P kéo theo L1 Є P. 204
  204. Lớp NP- đầy đủ Ngôn ngữ L là NP-đầy đủ (NPC) nếu: 1. L Є NP, và 2. Với mọi L’ Є NP thì L’ ≤_P L. Ngôn ngữ L là NP-khó nếu L thỏa mãn đk 2 (nhưng không nhất thiết đk 1). 205
  205. P versus NP ◼ Định lý: Nếu có một bài toán NP-đầy đủ nào giải được trong t.g.đ.t. thì P = NP. Nếu có một bài toán trong NP nào mà không giải được trong t.g.đ.t. thì tất cả các bài toán NP-đầy đủ đều không giải được trong t.g.đ.t. 206
  206. Chứng minh tính NP-đầy đủ 1. Bổ đề: Nếu L là một ngôn ngữ sao cho L’ ≤_P L với L’ Є NPC, thì L là NP-khó. Hơn nữa, nếu L Є NP thì L Є NPC. 2. Để chứng minh L Є NPC: - chứng minh L Є NP - chọn một ngôn ngữ L’ Є NPC - tìm một t.t. F tính hàm f chuyển mối trạng thái của L’ về một trạng thái của L - chứng minh f thỏa mãn: x Є L’  f(x) Є L với mọi x Є Σ* - chứng minh t.t. F chạy trong t.g.đ.t. 207
  207. Circuit satisfiability Combinational element: một dãy các phần tử có môt số cố định các phần tử vào và ra và hoàn thành tính toán một hàm. Boolean combinational element: đầu vào và ra là thuộc {0,1} (0: sai, 1: đúng) Một boolean combinational element dùng để tính 1 hàm boolean đơn được gọi là một logic gate. 208
  208. Boolean combinational circuit xây dựng từ các boolean combinational elements (được nối với nhau bằng các dây(wire)) 209
  209. 1. Circuit input (đầu vào): các dây không nối với một phần tử vào nào Circuit output (đàu ra): các dây không nối với một phần tử ra nào Ta xét các circuit chỉ có một đầu ra. 2. Một phép gán giá trị của một circuit là một tập các giá trị đầu vào. 3. Môt circuit là satisfiable (thỏa mãn) nếu có một phép gán giá trị đầu vào sao cho đàu ra của circuit là 1. 210
  210. Ví dụ 211
  211. Bài toán Circuit satisfiability “Cho một boolean combinational circuit gồm các cổng AND, OR, NOT; nó có thỏa mãn hay không ?” Độ dài của circuit: số các boolean combinational elements + số các wires Ngôn ngữ: CIRCUIT-SAT={ : C là một satisfiable boolean combinational circuit} 212
  212. CIRCUIT-SAT Є NP-đầy đủ Bổ đề: CIRCUIT-SAT Є NP Bổ đề: CIRCUIT-SAT là NP-khó Định lý: CIRCUIT-SAT Є NP-đầy đủ 213
  213. SAT Một trạng thái của bài toán SAT là một công thức boolean Φ gồm: 1. Các biến boolean: x1, x2, 2. Các liên kết boolean: các hàm boolean một hoặc hai biến: AND, OR, NOT, ->,  3. Các dấu ngoặc Một công thức Φ là satisfiable (thỏa mãn được )nếu có một phép gán giá trị để giá trị ra của Φ là 1. SAT = { : Φ là một công thức thỏa mãn được} 214
  214. SAT Є NP-đầy đủ ◼ Đinh lý: SAT Є NP-đầy đủ ◼ Chứng minh: - SAT Є NP - Qui dẫn CIRCUIT-SAT về SAT. 215
  215. 3-CNF SAT ◼ 1 literal trong một công thức boolean là một biến x hoặc ¬x. ◼ 1 công thức boolean là có dạng hợp chuẩn (conjunctive normal form, CNF), nếu nó được biểu diễn như là một phép AND của các clause, mỗi clause là một phép OR của các literal. ◼ 1 công thức boolean là một dạng 3-CNF nếu mỗi clause của nó có đúng 3 literal khác nhau. ◼ 3-CNF-SAT={Ф Є 3-CNF và là công thức thoả mãn được} 216
  216. 3-CNF-SAT Є NP-đầy đủ Định lý: 3-CNF-SAT Є NP-đầy đủ Chứng minh: - 3-CNF-SAT Є NP - Qui dẫn SAT về 3-CNF-SAT 217
  217. 3-CNF-SAT là NP-khó Ý tưởng: chứng minh SAT ≤P 3-CNF-SAT: ◼ Với mỗi công thức boolean Φ, ta tìm tương ứng một công thức f(Φ) Є 3-CNF. ◼ Xây dựng f(Φ) theo 3 bước: 1. Φ’: là công thức gồm phép AND của các clause 2. Φ’’: có dạng chuẩn CNF 3. Φ’’’: có dạng chuẩn 3-CNF. f(Φ)= Φ’’’ ◼ Chứng minh: Φ thỏa mãn được  f(Φ) thỏa mãn được ◼ Chứng minh f(Φ) có độ dài đa thức và f có tgđt 218
  218. Bước 1: Φ -> Φ’ 219
  219. ◼ Xây dựng cây nhị phân: ◼ Các lá là các literal của Φ ◼ Các nốt trong là các toán tử của Φ ◼ Thêm một biến yi cho mỗi nốt trong ◼ Φ’: là phép AND của gốc và các clause tương ứng với các nốt trong (mỗi clause có ≤ 3 literal) 220
  220. Φ’ -> Φ’’ ◼ Với mỗi clause C của Φ’: ◼ Viết bảng giá trị của C theo các biến ◼ Hợp các giá trị 0 lại, được dạng chuẩn DNF của ¬C ◼ Theo luật De Morgan, AND -> OR, OR ->AND: được dạng chuẩn CNF của C (C là AND của các clause, mỗi clause là gồm các phép OR) ◼ Φ’’: là AND của các tất cả clause nhận được (mỗi clause có ≤ 3 literal) 221
  221. Φ’’ -> Φ’’’ Ck ٨ ٨ C2 ٨ Φ’’ = C1 ◼ ◼ Nếu Ci có: ◼ 3 literal: để nguyên (p¬ ٧ y ٧ x) ٨ (p ٧ y ٧ y = (x ٧ literal Ci = x 2 ◼ ٨ (q¬ ٧ p ٧ x) ٨ (q ٧ p ٧ literal Ci = x = (x 1 ◼ (q¬ ٧ p¬ ٧ x) ٨ (q ٧ p¬ ٧ x) ◼ Φ’’’: nhận được Є 3-CNF 222
  222. Chứng minh tính đúng đắn ◼ Φ thỏa mẫn được  Φ’’’ thỏa mãn được ◼ Φ’’’: độ dài đa thức ◼ Tính Φ’’’: trong thời gian đa thức 223
  223. Bài toán chu trình Hamilton ◼ Cho đồ thị G=(V,E) vô hướng ◼ Một chu trình Hamilton trong G là một chu trình đơn và đi qua tất cả các đỉnh của G (qua mỗi đỉnh đúng một lần, trừ đỉnh đầu trùng đỉnh cuối). ◼ Đồ thị G được gọi là đồ thị Hamilton nếu nó có chu trình Hamilton, nếu không nó được gọi là đồ thi không phải Hamilton. ◼ Bài toán chu trình Hamilton: đồ thị G có chu trình Hamilton hay không ? ◼ HAM-CYCLE = { : G là đồ thị Hamilton} 224
  224. HAM-CYLCE Є NP-đầy đủ ◼ HAM-CYCLE Є NP ◼ 3-CNF-SAT ≤P HAM-CYCLE: Xây dựng hàm f: Φ Є 3-CNF -> đồ thị G=(V,E) Sao cho Φ thỏa mãn được  G là đồ thị Hamilton. 225
  225. Ý tưởng Φ: các biến x1, , xn; các clause: C1, ,Ck Đồ thị G gồm hai phần: trái, phải: 1. Trái: mỗi Ci: xây dựng một widget dạng B. Nối bi4 với bi+1,1, i=1,2, ,k-1 2. Phải: mỗi xm: x’m và x’’m nối bằng em và ¬em: em Є h  xm = 1 3. Nối (b11 , x1’) và (bk4, xn’’) 4. Nối các clause với các biến có liên quan bằng các widget dạng A. 226
  226. Chứng minh tính đúng đắn G Є HAM-CYCLE => Φ Є 3-CNF-SAT: Chu trình h trong G: 1. (b11 , x1’) và (bk4, xn’’) Є h 2. Bên trái: đi qua các widget B 3. Bên phải: qua hoặc em hoặc ¬em Gán giá trị cho Φ như sau: Nếu em Є h: xm= 1, nếu ¬em Є h: xm = 0 227
  227. Φ Є 3-CNF-SAT => G Є HAM-CYCLE Xây dựng h như sau: 1. Nếu xm= 1: em Є h, nếu xm = 0: ¬em Є h 2. (bij, bịj+1) Є h  literal thứ j của Ci = 0 228
  228. Thời gian đa thức ◼ Dễ thấy: 1. G độ dài đa thức 2. Tính G trong thời gian đa thức 229
  229. Bài toán Người đưa hàng Bài toán: Cho đồ thị G đầy đủ và có trong số c(i,j) cho mỗi cạnh (i,j). Tìm chu trình Hamilton có trọng số nhỏ nhất. Đưa về bài toán quyết định: TSP={ : G=(V,E) đồ thị đầy đủ, c hàm số V*V -> Z, k Є Z và G có chu trình người đưa hàng có trọng số ≤ k} 230
  230. TSP Є NP-đầy đủ 1. TSP Є NP: dễ chứng minh 2. Qui dẫn HAM-CYCLE về TSP: - Cho G=(V,E) Є HAM-CYCLE, xây dựng một trạng thái của TSP như sau: G’=(V,E’): E’=V*V; và c là: c(i,j) = 1 nếu (i,j) Є E, =0 nếu (i,j) ¬Є E Є TSP  Є HAM-CYCLE. - có độ dài đa thức và được tính trong tgđt. 231