›
›

Bài giảng Toán rời rạc - Bài 5: Bài toán liệt kê - Nguyễn Văn Hiệu

pdf 61 trang cucquyet12 19360
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Toán rời rạc - Bài 5: Bài toán liệt kê - Nguyễn Văn Hiệu", để 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:

  • pdfbai_giang_toan_roi_rac_bai_5_bai_toan_liet_ke_nguyen_van_hie.pdf

Nội dung text: Bài giảng Toán rời rạc - Bài 5: Bài toán liệt kê - Nguyễn Văn Hiệu

  1. BÀI 5 BÀI TOÁN LIỆT KÊ Giáo viên: TS. Nguyễn Văn Hiệu Email: nvhieuqt@dut.udn.vn Nguyễn Văn Hiệu, 2012, Discrete Mathematics 1
  2. 5.1. Giới thiệu Nội dung  5.1. Giới thiệu  5.2. Phương pháp sinh  5.3. Phương pháp quay lui Nguyễn Văn Hiệu, 2012, Discrete Mathematics 2
  3. 5.1. Giới thiệu Mục đích . Đưa ra danh sách tất cả các cấu hình có thể có Bản chất . Xác định một thuật toán để theo đó có thể lần lượt xây dựng được tất cả các cấu hình đang quan tâm. Nguyễn Văn Hiệu, 2012, Discrete Mathematics 3
  4. 5.1. Giới thiệu Nguyên tắc . Không được lặp lại một cấu hình . Không được bỏ sót một cấu hình Lưu ý . Chỉ giải với bài toán chưa có phương pháp giải  Phương pháp Sinh  Phương pháp quay lui Nguyễn Văn Hiệu, 2012, Discrete Mathematics 4
  5. 5.2. Phương pháp sinh Thường sử dụng . Giải bài toán liệt kê tổ hợp Điều kiện . Xác định được một thứ tự. . Có cấu hình đầu tiên . Có cấu hình cuối cùng . Xác định được thuật toán để xây dựng cấu hình kế tiếp Nguyễn Văn Hiệu, 2012, Discrete Mathematics 5
  6. 5.2. Phương pháp sinh Bản chất Chú thích Generating_method( ) {  Stop = =1, là cấu hình ; cuối cùng stop = islastconfigure( );  Stop == 0, chưa phải while (stop==0) { là cấu hình cuối cùng ; }  là } thuật toán sinh cấu hình tiếp theo trên thứ tự đã xác định trước Nguyễn Văn Hiệu, 2012, Discrete Mathematics 6
  7. 5.2. Phương pháp sinh Ví dụ  Liệt kê dãy nhị phân có độ dài n.  Liệt kê các tập con k phần tử của tập n phần tử.  Liệt kê các hoán vị của tập n phần tử Nguyễn Văn Hiệu, 2012, Discrete Mathematics 7
  8. 5.2. Phương pháp sinh Ví dụ 1: Liệt kê các dãy nhị phân có độ dài n Bước 1: Xác định thứ tự Dãy nhị phân được biểu diễn: b = (b1 b2 bn ) thỏa mản bi €{0,1}  Định nghĩa thứ tự từ điển: b = (b1 b2 bn) và *b = (*b1 *b2 *bn) thứ tự b < *b, nếu q(b) < q(*b) Nguyễn Văn Hiệu, 2012, Discrete Mathematics 8
  9. 5.2. Phương pháp sinh Ví dụ 1: Liệt kê các dãy nhị phân có độ dài n Bước 2: Cấu hình đầu và cuối  Khi n = 4 phần tử, có 24 dãy nhị phân được liệt kê Nguyễn Văn Hiệu, 2012, Discrete Mathematics 9
  10. 5.2. Phương pháp sinh Ví dụ 1: Liệt kê các dãy nhị phân có độ dài n Bước 2: b q(b) b q(b) 0000 0 1000 8 0001 1 1001 9 0010 2 1010 10 0011 3 1011 11 0100 4 1100 12 0101 5 1101 13 0110 6 1110 14 0111 7 1111 15 Nguyễn Văn Hiệu, 2012, Discrete Mathematics 10
  11. 5.2. Phương pháp sinh Bước 3: xác định thuật Thuật toán toán  Tìm i từ bên phải: 0000 0001 bi = 0.  Gán lại bi = 1 và 0001 0010 bj = 0 với mọi j> i. 0011 0100 i= n; 0111 1000 while (i>=1 && b[i]==‘1’) b[i ] = ‘0’; b[i] = ‘1’; Nguyễn Văn Hiệu, 2012, Discrete Mathematics 11
  12. 5.2. Phương pháp sinh Nguyễn Văn Hiệu, 2012, Discrete Mathematics 12
  13. 5.2. Phương pháp sinh Nguyễn Văn Hiệu, 2012, Discrete Mathematics 13
  14. 5.2. Phương pháp sinh Ví dụ 1: Liệt kê các dãy nhị phân có độ dài n Kết quả Chương trình Result Source Code Nguyễn Văn Hiệu, 2012, Discrete Mathematics 14
  15. 5.2. Phương pháp sinh Ví dụ 2 Liệt kê các tập con k phần tử của tập n phần tử Chuẩn bị  Ánh xạ tập n phần tử vào tập X = {1,2, ,n}  Mỗi tập con k phần tử của X được biểu diễn bởi bộ có thứ tự gồm k thành phần: a = (a1 a2 a3 ak ) thỏa mản 1≤ a1< a2 < a3 < < ak ≤ n Nguyễn Văn Hiệu, 2012, Discrete Mathematics 15
  16. 5.2. Phương pháp sinh Ví dụ 2 Liệt kê các tập con k phần tử của tập n phần tử Bước 1: Xác định thứ tự  Định nghĩa thứ tự từ điển: a = (a1 a2 a3 ak) và b = (b1 b2 b3 bk) thứ tự a < b, nếu tồn tại j (1≤ j≤ k): a1 = b1, ,aj-1= bj-1, aj < bj Nguyễn Văn Hiệu, 2012, Discrete Mathematics 16
  17. 5.2. Phương pháp sinh Ví dụ 2: Liệt kê các tập con k phần tử của tập n phần tử Bước 2: { 1,2,3 } Cấu hình đầu { 1,2,4 } { 1,2,5 }  Các tập con 3 phần tử { 1,3,4 } Cách sinh của tập 5 phần tử { 1,3,5 } {1,2,3,4,5} { 1,4,5 }  푪 5 = 10 { 2,3,4 } { 2,3,5 } { 2,4,5 } { 3,4,5 } Cấu hình cuối Nguyễn Văn Hiệu, 2012, Discrete Mathematics 17
  18. 5.2. Phương pháp sinh Bước 3: xác định Thuật toán thuật toán . Giả sử a = (a a ) không là n=5, k=3 1 k cuối cùng. i = 1 2 3  B1: Tìm vị trí i đầu tiên từ a = {1, 4, 5 } n-k+i = 3 4 5 bên phải của dãy: ai ≠ n-k+i.  B2: Thay ai bởi ai + 1.  B3: Thay a bởi a - i +j, { 2, , } j i { 2, 3, 4} với j = i+1, ,k Nguyễn Văn Hiệu, 2012, Discrete Mathematics 18
  19. 5.2. Phương pháp sinh Thuật toán Code . Giả sử a = (a1 ak ) không là cuối cùng. B1:  B1: Tìm vị trí i đầu tiên từ i=k; bên phải của dãy: while (a[i]==n-k+i) i ; B2: ai ≠ n-k+i. a[i]= a[i] + 1;  B2: Thay ai bởi ai + 1. B3:  B3: Thay aj bởi ai - i +j, với j = i+1, ,k for (j=i+1;j<=k;j++) a[j]= a[i]+ j –i; Nguyễn Văn Hiệu, 2012, Discrete Mathematics 19
  20. 5.2. Phương pháp sinh Nguyễn Văn Hiệu, 2012, Discrete Mathematics 20
  21. 5.2. Phương pháp sinh Nguyễn Văn Hiệu, 2012, Discrete Mathematics 21
  22. 5.2. Phương pháp sinh Ví dụ 2 Liệt kê các tập con k phần tử từ tập n phần tử Kết quả Chương trình Result Source Code Nguyễn Văn Hiệu, 2012, Discrete Mathematics 22
  23. 5.2. Phương pháp sinh Ví dụ 3 Liệt kê hoán vị của tập n phần tử Nguyễn Văn Hiệu, 2012, Discrete Mathematics 23
  24. 5.2. Phương pháp sinh Minh họa {1,2,3,4} {3,1,2,4} {1,2,4,3} {3,1,4,2}  {1,2,3,4} ? {1,3,2,4} {3,2,1,4} {3,2,4,1} {1,3,4,2}  {4,3,2,1}? {1,4,2,3} {3,4,1,2} {3,4,2,1} {1,4,3,2} {4,1,2,3}  {3,4,2,1} {4,1,2,3}? {2,1,3,4} {4,1,3,2} {2,1,4,3} {4,2,1,3}  Xây dựng thuật toán {2,3,1,4} {4,2,3,1} sinh {2,3,4,1} {4,3,1,2} {2,4,1,3} {4,3,2,1} {2,4,3,1} Nguyễn Văn Hiệu, 2012, Discrete Mathematics 24
  25. 5.2. Phương pháp sinh Định nghĩa Định nghĩa  Ánh xa tập n phần tử bất kỳ  Thứ tự từ điển: vào tập a = (a1 a2 a3 an) X = {1,2, ,n} b = (b1 b2 b3 bn)  Mỗi hoán vị của X được thứ tự a < b, biểu diễn bởi bộ có thứ tự nếu tồn tại j (1≤ j≤ n): gồm n thành phần: a = b , ,a = b , a < b a = (a a a ) 1 1 j-1 j-1 j j 1 2 n thỏa mản ai € X, i=1, ,n , ap ≠ aq , p ≠ q. Nguyễn Văn Hiệu, 2012, Discrete Mathematics 25
  26. 5.2. Phương pháp sinh Bước 3: Thuật toán n= 4 . a = (a1 a2 an ) chưa phải là cuối i = 1 2 3 4 cùng. a = {1 3 4 2}  B1: Tìm Right -> Left, j đầu tiên: k = 1 2 3 4 aj ≤ aj+1 a = { 1 3 4 2}  B2: Tìm Right -> Left, k đầu tiên: a = { , 4 , 3, } ak > aj.  B3: hoán vị aj và ak a = { , , 2, 3 }  B4: Lật ngược đoạn aj+1 đến an Nguyễn Văn Hiệu, 2012, Discrete Mathematics 26
  27. 5.2. Phương pháp sinh Bước 3:  int j = n-1;  B1: Tìm Right -> Left, j while(j>=1&&a[j]>a[j+1])j ; đầu tiên: a ≤ a  int k = n; j j+1 while(a[j]>a[k])k ;  B2: Tìm Right -> Left, k  int temp = a[j]; đầu tiên: a[j] = a[k]; a[k] = temp; ak > aj.  int l = j+1;int r = n;  B3: hoán vị aj và ak while(l<r) { int temp = a[l]; a[l]= a[r]; [r]= temp;  B4: Lật ngược đoạn aj+1 l++; r ; đến an } Nguyễn Văn Hiệu, 2012, Discrete Mathematics 27
  28. 5.2. Phương pháp sinh Nguyễn Văn Hiệu, 2012, Discrete Mathematics 28
  29. 5.2. Phương pháp sinh Nguyễn Văn Hiệu, 2012, Discrete Mathematics 29
  30. 5.2. Phương pháp sinh Nguyễn Văn Hiệu, 2012, Discrete Mathematics 30
  31. 5.2. Phương pháp sinh Ví dụ 2 Liệt kê các tập hoán vị của tập n phần tử Kết quả Chương trình Result Source Code Nguyễn Văn Hiệu, 2012, Discrete Mathematics 31
  32. Bài toán liệt kê Nội dung  5.1. Giới thiệu  5.2. Phương pháp sinh  5.3. Phương pháp quay lui Nguyễn Văn Hiệu, 2012, Discrete Mathematics 32
  33. Phương pháp quay lui Nội dung  Mục đích  Khái niệm  Phương pháp  Mã giả  Minh họa Nguyễn Văn Hiệu, 2012, Discrete Mathematics 33
  34. 5.3. Phương pháp quay lui Mục đích Khái niệm  Để giải bài toán liệt kê  Backtracking hoặc tối ưu tổ hợp  Поиск с возвратом  Quay lui  Đã giải:  Bài toán mã đi tuần  Backtracking  1950,  Bài toán xếp hậu  D.H.Lehmer  Bài toán mê cung  Bài toán người giao hàng Nguyễn Văn Hiệu, 2012, Discrete Mathematics 34
  35. 5.3. Phương pháp quay lui Khái niệm Khái niệm  Một cấu hình hay một nghiệp:  Backtracking– đi tìm lời s 1 s 2 s n giải cho bài toán mà s i ∈ D nghiệm của nó là một cấu hình hoặc một tập cấu  Bài toán: Liệt kê tất cả các cấu hình của S hình: S = s 1 s 2 s n  Tính chất P: xác định cấu hình  Bài toán con:  Tính chất Q: xác định Giả sử đã tìm được s 1 s i , i < 푛 tính dừng của bài toán Hãy tìm cấu hình S Nguyễn Văn Hiệu, 2012, Discrete Mathematics 35
  36. 5.3. Phương pháp quay lui Phương pháp Bản chất  Một quy trình tìm kiếm theo chiều . Giả sử có: s1 s i-1 sâu Tìm giá trị cho s i:  Ví dụ tìm số có 3 chữ số đầu tiên  Duyệt ∀ j ∈ đề cử cho s i  Mỗ푖 j ∈ kiểm tra:  D = {1,2, 3}  Nếu j chấp nhận (∈ P ), si = j  P:  Nếu i = n (∈ Q ) , được 1  (2,1,3) – chấp nhận cấu hình,  (2,2,3) – không chấp nhận  Nếu i< 푛, tìm s i +1. 1 2 3  Nếu ∀ j không được cấp nhận 1 3 2 (∉ P ) (ngõ cụt) thì quay lại 2 1 3 2 3 1 bước xác định si-1 3 1 2 3 2 1 Nguyễn Văn Hiệu, 2012, Discrete Mathematics 36
  37. 5.3. Phương pháp quay lui Phương pháp Mã giả . Giả sử có: s1 s i-1 void try (i, n){ ∀j ∈ D { Tìm giá trị cho s i: i  Duyệt ∀ j ∈ đề cử cho si if ( ){  Mỗ푖 j ∈ kiểm tra: si = j;  Nếu j chấp nhận (∈ P ), s = j i if (i==n)  Nếu i = n (∈ Q ) , được 1 cấu hình,  Nếu i< 푛, tìm s i +1. else try (i+1, n);  Nếu ∀ j không được cấp nhận } (∉ P ) (ngõ cụt) thì quay lại } bước xác định si-1 } Nguyễn Văn Hiệu, 2012, Discrete Mathematics 38
  38. 5.3. phương pháp quay lui Bắt đầu S1 D1 ( 2pt) s2 D2 (2pt) D3 (2pt) s3 D4 ( 3pt) s4 Một cấu hình Nguyễn Văn Hiệu, 2012, Discrete Mathematics 39
  39. 5.2. Phương pháp quay lui Ví dụ  Liệt kê dãy nhị phân có độ dài n.  Liệt kê hoán vị tập n phần tử.  Bài toán Xếp Hậu. Nguyễn Văn Hiệu, 2012, Discrete Mathematics 40
  40. 5.3. Phương pháp quay lui Ví dụ 1 Mã giả  Liệt kê xâu nhị phân độ dài n void Try(int i, char b[]){ char j;  Biểu diễn dãy nhị phân: for(j='0'; j<='1';j++){ b = ( b b b ) 1 2 n , //P – bỏ qua kiêm tra bi ∈ {0,1}  Try(i, ) - xác định bi b[i]=j;  D = {0,1} if(i==n) Out(b);  P else Try(i+1,b);  i = n - được 1 cấu hình ∈ 푄 } } Nguyễn Văn Hiệu, 2012, Discrete Mathematics 41
  41. 5.3. Phương pháp quay lui Bit 1 2 3 4 0 0 0 0 0000 Mã giả 1 0001 1 0 0010 void Try(int i, char b[]){ 1 0011 char j; 1 0 0 0100 Try(1,b) for(j='0'; j<='1';j++){ 1 0101 //P – bỏ qua kiêm tra 1 0 0110 1 0111 b[i]=j; 1 0 0 0 1000 if(i==n) Out(b); 1 1001 else Try(i+1,b); 1 0 1010 } 1 1011 } 1 0 0 1100 1 1101 1 0 1110 1 1111 Nguyễn Văn Hiệu, 2012, Discrete Mathematics 42
  42. 5.3. Phương pháp quay lui Nguyễn Văn Hiệu, 2012, Discrete Mathematics 43
  43. 5.2. Phương pháp quay lui Ví dụ 1 Liệt kê xâu nhị phân độ dài n Kết quả Chương trình Result Source Code Nguyễn Văn Hiệu, 2012, Discrete Mathematics 44
  44. 5.3. Phương pháp quay lui Ví dụ 2 Ví dụ 2 . Liệt kê các hoán vị của tập  Sử dụng mảng b X = {1,2, ,n}. b = { b[1], b[2], , b[n]} 1 , 푗 ℎư ℎọ푛  Biểu diễn hoán vị dạng b[j] = 0 , 푗 đã đượ ℎọ푛 s1 s2 sn si ∈ X , sp ≠ sq , p ≠ q.  Try(i, ) - xác định si  Khởi tạo b[j] = 1, ∀푗 ∈  D = {0,1, ,n}  Chấp nhận j ∈ nếu j chưa  i = n - được 1 cấu hình ∈ 푄 được chọn. Nguyễn Văn Hiệu, 2012, Discrete Mathematics 45
  45. 5.3. Phương pháp quay lui Ví dụ 2 Mã giả . Liệt kê các hoán vị của tập void Try(int i,int b[],int s[]){ X = {1,2, ,n}. int j; for(j=1;j<=n;j++){  Biểu diễn hoán vị dạng if(b[j]==1){ s1 s2 sn s[i]=j; si ∈ X , sp ≠ sq , p ≠ q. b[j]=0;  Try(i, ) - xác định si if(i==n) Out(s); else Try(i+1,b,s); b[j]=1; } } } Nguyễn Văn Hiệu, 2012, Discrete Mathematics 46
  46. 5.3. Phương pháp quay lui Nguyễn Văn Hiệu, 2012, Discrete Mathematics 47
  47. 5.3. Phương pháp quay lui Nguyễn Văn Hiệu, 2012, Discrete Mathematics 48
  48. 5.2. Phương pháp sinh Ví dụ 2 Liệt kê hoán vị của tập n phần tử Kết quả Chương trình Result Source Code Nguyễn Văn Hiệu, 2012, Discrete Mathematics 49
  49. 5.3. Phương pháp quay lui Ví dụ 3 Ví dụ 3 . Liệt kê tất cả các cách xếp 8  Đánh số cột từ 1 8 quân Hậu trên bàn cờ 8x8 sao  Đánh số hàng từ 1 8 cho chúng không ăn được  Biểu diễn cách xếp: nhau. x1 x2 x8   xi được xếp ở hàng i  D = {1, ,8}  xi= j : Hậu thứ i được xếp vào cột j  j được chấp nhận nếu ô (i,j) được tự do Nguyễn Văn Hiệu, 2012, Discrete Mathematics 50
  50. 5.3. Phương pháp quay lui Ví dụ 3 Ví dụ 3  ô (i,j) được tự do  Mảng a – quản lý cột  Quản lý cột a = { a[1], , a[8]}  Quản lý đường chéo thuận 1 , ộ푡 푗 푡ự 표  Quản lý đường chéo a[j] = nghịch 0 , ộ푡 푗 đã ℎ푖ế Nguyễn Văn Hiệu, 2012, Discrete Mathematics 51
  51. 5.3. Phương pháp quay lui Ví dụ 3: Ví dụ 3  Quản lý đường chéo thuận  Mảng b – quản lý đường chéo thuận b = { b[2], ,b[16]}  b[k]= 1 , đ ℎ ậ푛 푡ự 표 0 , đ 푡ℎ ậ푛 đã ℎ푖ế Nguyễn Văn Hiệu, 2012, Discrete Mathematics 52
  52. 5.3. Phương pháp quay lui Ví dụ 3: Ví dụ 3  Quản lý đường chéo nghịch  Mảng c – quản lý đường chéo nghịch c = { c[-7], ,b[7]}  c[k]= 1 , đ 푛𝑔ℎị ℎ 푡ự 표 0 , đ 푛𝑔ℎị ℎ đã ℎ푖ế Nguyễn Văn Hiệu, 2012, Discrete Mathematics 53
  53. 5.3. Phương pháp quay lui Ví dụ 3: Ví dụ 3  Khởi tạo: 1 2 3 4 5 6 7 8 ∀ 푖, X1 aj =1&& bk=1&& ck =1 X 2 X3  j được chấp nhận khi X4 aj ==1&& bi+j==1 && c ==1 X5 i-j X 6  Try (i, ) – tìm cột đặt con X7 hậu ở hang i X8 Nguyễn Văn Hiệu, 2012, Discrete Mathematics 54
  54. 5.3. Phương pháp quay lui Nguyễn Văn Hiệu, 2012, Discrete Mathematics 55
  55. 5.3. Phương pháp quay lui Nguyễn Văn Hiệu, 2012, Discrete Mathematics 56
  56. 5.3. Phương pháp quay lui Nguyễn Văn Hiệu, 2012, Discrete Mathematics 57
  57. 5.2. Phương pháp quay lui Ví dụ 3 Liệt kê cách xếp hậu Kết quả Chương trình Result Source Code x = (3 6 4 2 8 5 7 1) Nguyễn Văn Hiệu, 2012, Discrete Mathematics 58
  58. Tóm lại  Kỹ thuật sinh: (1) Xác định trạng thái đầu của bài toán. (2) Xác định trạng thái kết thúc. (3) Xác định một thứ tự cho các trạng thái. (4) Tìm giải thuật đi từ trạng thái này sang trạng thái khác.  Kỹ thuật quay lui: (1) Tại 1 thời điểm, chỉ xét thành phần thứ i của cấu hình (2) Với mọi trị j trong miền trị của thành phần này 2.1- Nếu chọn được 1 trị hợp lệ thì Gán xi = j Xử lý cấu hình ở thành phần thứ i+1 Nếu i=0 thì bài toán không có lời giải. Nguyễn Văn Hiệu, 2012, Discrete Mathematics 59
  59. Bài Tập 1. Liệt kê nghiệm nguyên của pt x1 + x2 + x3 = 15 với x1 ≥ 0 , x2 ≥ 0 , x3 ≥ 0. 2. Liệt kê số chuổi có độ dài 3 ký tự xyz với x ∈ { a,b,c}, y ∈ { d,e}, z ∈ { m,n,t} 3. Viết lại các bài mẫu về giải thuật quay lui nhưng ghi kết qủa lên file. Nguyễn Văn Hiệu, 2012, Discrete Mathematics 60
  60. Bài Tập x y z a d m a d n a d t Cấu hình ban đầu: trị đầu tiên a e m của mỗi miền trị a e n a e t b d m Dùng thứ tự b d n từ điển để so b d t Cách sinh:Lấy trị kế tiếp của mỗi b e m sánh: miền trị theo cơ chế vòng tròn b e n b e t adm < adn c d m c d n c d t Cấu hình cuối: trị cuối cùng của c e m mỗi miền trị c e n c e t Nguyễn Văn Hiệu, 2012, Discrete Mathematics 61
  61. THAT’S ALL; THANK YOU • WHAT NEXT? LÝ THUYẾT ĐỒ THỊ