Bài giảng Cấu trúc dữ liệu và giải thuật - Phương pháp tham lam - Nguyễn Văn Linh

Phương pháp tham lam (greedy)Bài toánPhương phápLược đồ tổng quátVí dụ minh hoạBài toán Cái ba lôBài toán tô màu bản đồ1Bài toánPhương pháp tham lam thường được sử dụng để giải quyết các bài toán tối ưu.2Bài toán (tiếp)	Nhiều vấn đề cần giải quyết qui về bài toán:Cho trước tập A các đối tượng nào đó, cần phải chọn ra một tập con S các đối tượng thoả mãn một số điều kiện nào đó. Bất kỳ tập con S nào thoả mãn điều kiện gọi là nghiệm chấp nhận được của bài toán.Một hàm mục tiêu gắn mỗi nghiệm chấp nhận được với một giá trị nào đó.Một nghiệm chấp nhận được mà hàm mục tiêu có giá trị lớn nhất (hoặc nhỏ nhất) gọi là nghiệm tối ưu3Phương phápTa xây dựng tập S dần từng bước, bắt đầu từ tập S =Tại mỗi bước, ta sẽ chọn một phần tử “tốt nhất” trong các phần tử còn lại của A để đưa vào tập S.Việc chọn lựa một phần tử như thế ở mỗi bước sẽ được hướng dẫn bởi hàm chọn.4Phương pháp (tiếp)Phần tử được chọn bị loại khỏi tập ANếu khi thêm phần tử được chọn vào tập S mà S vẫn thoả mãn các điều kiện của bài toán, ta tiếp tục mở rộng S bằng cách thêm vào phần tử được chọn5Lược đồ tổng quátThamlam(A,S) { A là tập các ứng cử viên, S là tập nghiệm}Bước 1: S=;Bước 2: Khi A  thực hiện các bước sau:Bươc 2.1: X = Select(A);Bước 2.2: A = A - {x};Bước 2.3: Nếu S  {x} Chấp nhận được thì S=S  {x}6Bài toán cái ba lôInput:Cho n đồ vật Đồ vật i khối lượng Wi và trị giá Vi Kích thước ba lô ZOutput:Chọn k đồ vật cho vào ba lô sao cho tổng khối lượng W  Z và tổng giá trị V lớn nhất7Bài toán cái ba lô (tiếp) Ví dụ: Cho 4 loại đồ vật có khối lượng và trị giá:Kích thước ba lô 37WV1530102522688Bài toán cái ba lô (tiếp)15,302,210,256,83715,3015,3015,30Ối!!! Túi không vừa9Bài toán cái ba lô (tiếp)15,302,210,256,83715,3015,3010,25Ối!!! Túi không vừa10Bài toán cái ba lô (tiếp)15,302,210,256,83715,3015,302,22,22,2Kích thước =36Trị giá =66Á, ít quá !!!Ta phải làm cách khác ???11Bài toán cái ba lô (tiếp)15,302,210,256,83715,3015,302,22,26,8Ối!!! Túi không vừa12Bài toán cái ba lô (tiếp)15,302,210,256,83715,3015,302,26,8Ối!!! Túi không vừa13Bài toán cái ba lô (tiếp)15,302,210,256,83715,3015,306,8Kích thước =36Trị giá =68Á, Vẫn ít, !!!Ta phải làm cách khác ???14Bài toán cái ba lô (tiếp)15,302,210,256,83715,3010,2510,252,2Kích thước =37Trị giá =82Á, khá hơn hẳn !!!Ta phải làm cách khác ???15Bài toán cái ba lô (tiếp)15,302,210,256,83710,2510,2510,256,8Kích thước =36Trị giá =83Very good!!!16Bài toán ba lô (tiếp) – Ý tưởngSử dụng phương pháp tham lamTa xây dựng nghiệm dần từng bướcTa căn cứ vào tỉ lệ giữa giá trị và khối lượng V/W sắp xếp các đồ vật sẽ chọn lựa theo thứ tự ưu tiên giảm17Bài toán ba lô (tiếp) – Giải thuậtBALOS=Với mỗi đồ vật i  n thực hiện:Nếu tất cả các đồ vật trong S {i} có chấp nhận được S= S  {i}18Bài toán cái ba lô (tiếp) – Chú ýTrong nhiều trường hợp ta chỉ chọn được nghiệm gần đúng với nghiệm tối ưuVí dụ với Z=15Ta chọn đồ vật W=15, V=30 “Tối ưu hơn” 2 đồ vật (W= 10,V=25) và (W =2,V=2)19Bài toán tô màu bản đồBài toán:Tô màu các nước trên bản đồ sao cho các nước có chung đường biên giới thì được tô khác màu nhau.Cần chọn cách tô tối ưu sao cho số màu dùng để tô là ít nhất20Bài toán tô màu bản đồ (tiếp)Input:Cho đồ thị G=(V,E) là đồ thị không có hướngCần sơn các đỉnh đồ thị sao cho hai đỉnh kề nhau được sơn bởi hai màu khác nhau Output:Số màu k tối thiểu phải sử dụng21Bài toán tô màu bản đồ (tiếp)ABCDE22Bài toán tô màu bản đồ (tiếp) – Ý tưởngÝ tưởng:Sử dụng phương pháp tham lamDùng một màu để tô (ví dụ màu đỏ).Chọn một đỉnh chưa được tô, và tô đỉnh đó. Sau đó với mỗi đỉnh chưa được sơn, nếu nó không kề với các đỉnh đã tô bởi màu đang dùng, ta tiến hành tô nó bởi màu đang sử dụng.Khi không còn đỉnh nào có thể tô bởi màu đó thì ta sử dụng một màu mớiQuá trình này cứ tiếp tục cho đến khi các đỉnh trên đồ thị đã được tô23Bài toán tô màu bản đồ (tiếp)ABCDEAKhông sử dụng màu đỏ được !!!CKhông sử dụng màu đỏ được !!!EBDTa sử dụng 2 màu để tô, Very good !!!24Bài toán tô màu bản đồ (tiếp)ABCDEACEBDTa sử dụng 3 màu để tô, good !!!25Bài toán tô màu bản đồ (tiếp) - Giải thuậtGọi V là tập đỉnh của đồ thịV0 là tập đỉnh chưa được tôV1 là tập các đỉnh đã được tôTa kí hiệu các màu là k =1, 2, 3, 26Bài toán tô màu bản đồ (tiếp) - Giải thuậtToMauBước 1: k=0; V0 = V;Bước 2: Khi k 0 thực hiện các bước sau:Bước 2.1: k=k+1;Bước 2.2: Chọn x V0 và tô x bởi màu k;Bước 2.3: V1 = V1 {x};Bước 2.4:Với mỗi v  V0 thực hiện:27Bài toán tô màu bản đồ (tiếp) - Giải thuậtBước a: Nếu v không kề với mọi w V1Bước a.1: Tô v bởi màu k;Bước a.2: V1 = V1  {v};Bước b: V0 = V0 –V128Phương pháp quay luiBài toánPhương phápLược đồ tổng quátVí dụ minh hoạBài toán 8 hậuBài toán mã đi tuầnBài toán tìm các hoán vị của dãy số 1..nBài toán tìm các tập con có tổng cho trước29Bài toánDùng để thiết kế thuật toán tìm ra một nghiệm hoặc tất cả các nghiệm của bài toánTrong nhiều trường hợp, việc tìm nghiệm quy về việc tìm một véctơ hữu hạn V(x1,x2,,xn, ) nhưng độ dài véctơ có thể không được xác định trước.30Bài toán (tiếp)Véctơ này cần thoả mãn một số điều kiện nào đó tuỳ thuộc bài toán.Các thành phần xi của vectơ được chọn từ một tập hữu hạn Ai(i=1,2..n,).31Phương phápTa xây dựng vectơ nghiệm dần từng bước, bắt đầu từ vectơ không ().Thành phần đầu tiên x1 được chọn ra từ tập S1 = A1.Khi đã chọn được các thành phần x1, x2,..,xi-1 từ các điều kiện của bài toán ta xác định tập Si các ứng viên để chọn làm thành phần xiTập Si là tập con của Ai và phụ thuộc vào các thành phần x1,x2,,xi-1 đã chọn.32Phương pháp (tiếp)Chọn một phần tử xi trong tập Si ta mở rộng vectơ nghiệm (x1,x2,,xi-1) thành vectơ nghiệm (x1,x2,,xi).Lặp lại quá trình trên để tiếp tục mở rộng vectơ nghiệm (x1,x2,,xi).Nếu không thể chọn được thành phần xi+1 (khi Si+1=) ta quay lại chọn phần tử khác của Si làm xi. Nếu không còn một phần tử nào khác của Si ta quay lại chọn một phần tử khác của Si-1 làm xi-1 và cứ thế tiếp tục33Phương pháp (tiếp)Trong quá trình mở rộng vectơ nghiệm ta phải kiểm tra vectơ nghiệm có là nghiệm của bài toán hay không.Nếu chỉ tìm 1 vectơ nghiệm, khi tìm được vectơ nghiệm ta dừng lạiNếu cần tìm tất cả các vectơ nghiệm, quá trình trên chỉ dừng khi tất cả các khả năng chọn các xi của vectơ nghiệm đã được duyệt hết.34Lược đồ tổng quát Quaylui(vectơ,i) {Xác định thành xi của vectơ nghiệm}Bước 1: Xác định SiBước 2: Với mọi xi  Si thực hiện các bước sau:Bước 2.1: vectơ = vectơ +(xi);Bươc 2.2: Nếu vectơ là nghiệm thì Viết nghiệmBước 2.3: Quaylui(vectơ,i+1);Bước 2.4: vectơ = vectơ – (xi);35Bài toán 8 quân hậuInput: Bàn cờ 8 x 88 quân hậuOutput:Đặt 8 quân hậu vào 8 ô khác nhau sao cho trên mỗi hàng, mỗi cột, mỗi đường chéo chỉ có một quân36Bài toán 8 hậu (tiếp )XXXXXXXX37Bài toán 8 hậu (tiếp )Ý tưởngSử dụng phương pháp quay luiVét cạn mọi trường hợp có thể xảy ra	38Bài toán 8 hậu (tiếp )X39Bài toán 8 hậu (tiếp )XXỐi! Tôi bị ănXX40Bài toán 8 hậu (tiếp )XX41Bài toán 8 hậu (tiếp )Bài toán 8 hậu (tiếp )XXX42Bài toán 8 hậu (tiếp )Bài toán 8 hậu (tiếp )XXX43Bài toán 8 hậu (tiếp)XXXX44Bài toán 8 hậu (tiếp)XXXX45Bài toán 8 hậu (tiếp)XXXXX46Bài toán 8 hậu (tiếp)XXXXX47Bài toán 8 hậu (tiếp)XXXXXX48Bài toán 8 hậu (tiếp)XXXXXXX49Bài toán 8 hậu (tiếp)XXXXXXXHết chỗ đặt tướng !!!50Bài toán 8 hậu (tiếp)XXXXXXXCất tướng ở vị trí này51Bài toán 8 hậu (tiếp)XXXXXCất tướng khỏi ô này52Bài toán 8 hậu (tiếp)XXXXCất tướng khỏi ô nàyX53Bài toán 8 hậu (tiếp)XXXXX54Bài toán 8 hậu (tiếp)XXXXXKhông đặt tướng được!!!55Bài toán 8 hậu (tiếp)XXXXKhông đặt được tướng ở vị trí nàyX56Bài toán 8 hậu (tiếp)XXXXX57Bài toán 8 hậu (tiếp)XXXXXX58Bài toán 8 hậu (tiếp)XXXXXXX59Bài toán 8 hậu (tiếp)XXXXXXX60Bài toán 8 hậu (tiếp)XXXKhông đặt được tướng ở vị trí nàyX61Bài toán 8 hậu (tiếp )DATHAU(i); {Đặt bà thứ i trên bàn cờ }Bước 1: Khởi động chọn vị trí cho bà thứ i;Bước 2: Thực hiện các bước sau cho đến khi (Thành công) hoặc (Hết chỗ đặt tướng bà) : Bước 2.1: Thực hiện phép chọn vị trí cho bà thứ i;Bước 2.2: Nếu Antoàn thực hiện các bước sau:62Bài toán 8 hậu (tiếp )Bước 2.1.a Đặt tướngBước 2.1.b Nếu (in) InKêtQua ngược lại thực hiện bước 2.Bước 2: Với mọi j  1..n thực hiện:Bước 2.1: Nếu (B[j] =1) thực hiện:Bước 2.1.a: A[i]=j;B[j] =0;Bước 2.1.a: TRY(i+1);B[j]=1; A[i] =0; 89Bài toán tìm các tập Con có tổng cho trướcInput:A tập n số nguyên dươngM là số nguyên dương cho trướcOutput:Tìm A’  A, sao cho  A’ = M90A = { 3, 5, 20, 15, 35, 69, 72}M = 38 Bài toán tìm các tập Con có tổng cho trước (tiếp)91Bài toán tìm các tập Con có tổng cho trước (tiếp) 352015356972 M = 3835201543 > MQuay lui!!!92 M = 3833Bài toán tìm các tập Con có tổng cho trước (tiếp)352015356972 M = 3835153533558 > MQuay lui!!!93Bài toán tìm các tập Con có tổng cho trước (tiếp) - Giải thuậtTa dùng mảng A[1..n] để lưu các số nguyên thuộc tập A đã choMảng I[1..n] lưu chỉ số các thành phần thuộc A’ cần tìmS lưu tổng các số của A’ trong quá trình hình thành94Bài toán tìm các tập Con có tổng cho trước (tiếp) - Giải thuậtTAPCONBước 1: k=1; I[1 ]=0; S =0;Bước 2: Khi k 0 thực hiện các bước:Bước 2.1: I[k] =I[k]+1;Bước 2.2: Nếu I[k]<=n thực hiện các bước sau, ngược lại thực hiện bước 2.395Bài toán tìm các tập Con có tổng cho trước (tiếp) - Giải thuậtTAPCONBước 2.2.a: Nếu S+A[I[k]] = M viết kết quả l[1..k], ngược lại thực hiện:Bước 2.2.b: S =S+A[I[k]];l[k+1]=I[k];k=k+1Bước 2.3:k=k-1;S = S- A[i[k]];9697