Khoa học máy tính - Thuật toán tham lam

THUẬT TOÁN (Algorithms)Nguyễn Thanh CẩmNội DungTHUẬT TOÁN VÀ ĐỘ PHỨC TẠP C1CHIA ĐỂ TRỊ C2QUY HOẠCH ĐỘNG C3THUẬT TOÁN THAM LAM C4THUẬT TOÁN QUAY LUIC54.14.2Thuật toán tham lam Một số bài toán minh họa THUẬT TOÁN THAM LAM4.14.1.14.1.2Thuật toán tham lam Đặc điểm chung của thuật toán tham lam Thuật toán tham lam THUẬT TOÁN THAM LAMSự khác nhau giữa thuật toán tham lam và thuật toán quy hoạch động 4.1.34.1.1 Đặc điểm chung của thuật toán tham lam Một bài toán thực hiện cấu trúc con tối ưu (optimal substructure) nếu cách giải quyết tối ưu của bài toán chứa đựng cách giải quyết tối ưu những bài toán con của nó.Đối với nhiều bài toán, thuật toán tham lam hầu như không cho ra lời giải tối ưu toàn cục, vì chúng thường không chạy trên tất cả các trường hợp. Tuy nhiên, các thuật toán này vẫn hữu ích vì chúng dễ thiết kế và cho ra các ước lượng tốt về lời giải tối ưu.Nếu một thuật toán tham lam cho ra kết quả tối ưu toàn cục cho một lớp bài toán nào đó, thì thuật toán thường sẽ được chọn lựa, vì nó chạy nhanh hơn các phương pháp tối ưu hóa khác như quy hoạch động 4.1.2 Thuật toán tham lam Thuật tham lam có 05 thành phần:Một tập hợp các ứng viên C (candidate), để từ đó tạo ra lời giải. Một hàm lựa chọn Select(C), để theo đó lựa chọn ứng viên tốt nhất để bổ sung vào lời giải. Một hàm khả thi Feasible(S  x), dùng để quyết định nếu một ứng viên có thể được dùng để xây dựng lời giải. Một hàm mục tiêu Solution(S), ấn định giá trị của lời giải hoặc một lời giải chưa hoàn chỉnh. Một hàm đánh giá, chỉ ra khi nào ta tìm ra một lời giải hoàn chỉnh.4.1.2 Thuật toán tham lam Thuật tham lam:void      Greedy;           //Giả sử C là tập các ứng cử viên        {                S = ;       // S là lời giải xây dựng theo thuật toán               While ( (C  0) and not Solution(S))              {                         x  Select(C);                        C = C\x;                        If (Feasible(S  x))        S = S  x                }             If (Solution(S) )   Return S     }4.1.2 Thuật toán tham lam Chúng minh tính đúng đắn:Để chỉ ra thuật toán không cho lời giải đúng chỉ cần đư­a ra một phản ví dụViệc chứng minh thuật toán đúng khó hơn nhiều và ta sẽ nghiên cứu cụ thể trong phần sau đây :Lập luận biến đổi (Exchange Argument)Giả sử cần chứng minh thuật toán A cho lời giải đúng. A(I) là lời giải tìm được bởi thuật toán A đối với bộ dữ liệu I. Còn O là lời giải tối ưu của bài toán với bộ dữ liệu này.Ta cần tìm cách xây dựng phép biến đổi  để biến đổi O thành O’ sao cho:O’ cũng tốt không kém gì O (Nghĩa là O’ vẫn tối ưu). O’ giống với A(I) nhiều hơn O.Giả sử đã xây dựng được phép biến đổi vừa nêu. Để chứng minh tính đúng đắn dựa vào hai sơ đồ chứng minh sau 1)  Chứng minh bằng phản chứng: Giả sử A không đúng đắn, hãy tìm bộ dữ liệu I sao cho A(I) khác với lời giải tối ưu của bài toán. Gọi O là lời giải tối ưu giống với A(I) nhất => A(I) khác O. Dùng phép biến đổi  chúng ta có thể biến đổi O  O’ sao cho O’  vẫn tối ưu và O’ giống với A(I) hơn => mâu thuẫn giả thiết O là lời giải tối ưu giống với A(I) nhất.2)  Chứng minh trực tiếp: O là lời giải tối ưu. Biến đổi O  O’ giống với A(I) hơn là O. Nếu O’ = A(I) thì A(I) chính là phương án tối ưu ngược lại biến đổi O’   O’’  giống với A(I) hơn. Cứ thế ta thu được dãy O’, O’’ ,O’’’ ..ngày càng giống hơn, và chỉ có một số hữu hạn điều kiện để so sánh nên chỉ sau một số hữu hạn lần phép biến đổi sẽ kết thúc và đó là tại A(I).4.1.3 Sự khác nhau giữa thuật toán tham lam và thuật toán quy hoạch động Toàn bộ phương pháp tối ưu có thể đạt được, từ việc chọn tối ưu trong từng bước chọn. Về khía cạnh này, thuật toán tham lam khác với thuật toán quy hoạch động ở chỗ: Trong quy hoạch động chúng ta thực hiện chọn cho từng bước, nhưng việc lựa chọn này phụ thuộc vào cách giải quyết các bài toán con. Với thuật toán tham lam, tại mỗi bước chúng ta chọn bất cứ cái gì là tốt nhất vào thời điểm hiện tại, và sau đó giải quyết các vấn đề phát sinh từ việc chọn này. Vấn đề chọn thực hiện bởi thuật toán tham lam không phụ thuộc vào việc lựa chọn trong tương lai hay cách giải quyết các bài toán con. Vì vậy khác với quy hoạch động, giải quyết các bài toán con theo kiểu bottom-up (từ dưới lên), thuật toán tham lam thường sử dụng giải pháp top-down (từ trên xuống).4.24.2.14.2.2Một số bài toán minh họa Bài toán đường đi của người giao hàng Bài toán các đoạn thẳng không giao nhau THUẬT TOÁN THAM LAMBài toán cái ba lô 4.2.3Bài toán cây khung nhỏ nhất 4.2.44.2.1 Bài toán đường đi của người giao hàng Bài toán: Có một người đi giao hàng, cần đi giao hàng tai n thành phố. Xuất phát tại một thành phố nào đó đi qua các thành phố khác để giao hàng và trở về thành phố ban đầu. Mỗi thành phố chỉ đến 1 lần khoảng cách từ một thành phố đến các thành phố khác là xác định. Giả thiết rằng, mỗi thành phố đều có đường đi đến các thành phố còn lại. Khoảng cách giữa hai thành phố có thể là khoảng cách địa lý, có thể là cước phí di chuyển hoặc thời gian di chuyển. Ta gọi chung là độ dài. Hãy tìm một chu trình (một đường đi khép kín thỏa mãn điều kiện trên) sao cho tổng độ dài các cạnh là nhỏ nhất, hay nói cách khác là tìm một phương án có giá trị nhỏ nhất. Bài toán này cũng được gọi là bài toán người du lịch.Một cách tổng quát, có thể không tồn tại một đường đi giữa hai thành phố a và b nào đó. Trong trường hợp đó ta cho đường đi ảo giữa a và b với độ dài bằng ∞4.2.1 Bài toán đường đi của người giao hàng Bài toán này có nhiều ứng dụng rất quan trọng. Thí dụ một máy hàn các điểm được điều khiển bởi máy tính. Nhiệm vụ của nó là hàn một số điểm dự định ở trên một tấm kim loại. Người thợ hàn bắt đầu từ một điểm ở bên ngoài tấm kim loại và kết thúc tại chính điểm này, do đó tấm kim loại phải được di chuyển đến điểm cần hàn được đưa vào vị trí hàn ( tương tự như ta đưa tấm vải vào đầu mũi kim của máy khâu). Cần tìm một phương án di chuyến tấm kim loại sao cho việc di chuyến ít nhất.Hình ảnh sau minh họa bài toán trên:           4.2.1 Bài toán đường đi của người giao hàng Với phương pháp véc cạn ta xét tất cả các chu trình, mỗi chu trình tính tổng độ dài các cạnh của nó rồi chọn một chu trình có tổng độ dài nhỏ nhất. Tuy nhiên chúng ta cần xét tất cả (n-1)! chu trình. Thật vậy do mỗi chu trình đi qua tất cả các đỉnh (thành phố) nên ta cố định một đỉnh. Từ đỉnh này ta có n-1 cạnh tới n-1 đỉnh khác nên ta có n-1 cách chọn cạnh đầu tiên của chu trình. Sau khi đã chọn được cạnh đầu tiên chúng ta có n-2 cách chọn cạnh thứ hai, do đó ta có (n-1)(n-2) cách chọn hai cạnh. Cứ lý luận như vậy ta sẽ có (n-1)! cách chọn chu trình khác nhau. Và đó là một thuật toán với thời gian lớn hơn hàm mũ.4.2.1 Bài toán đường đi của người giao hàng Áp dụng kỹ thuật tham lam ta có:B1: Sắp xếp các cạnh theo thứ tự tăng của độ dàiB2: Xét các cạnh có độ dài từ nhỏ đến lớn để đưa vào chu trìnhB3: Một cạnh sẽ được đưa vào chu trình sẽ thỏa mãn: Không tạo thành một chu trình con Không tạo thành một đỉnh có cấp >= 3Lặp lại bước ba cho đến khi được một chu trình.4.2.1 Bài toán đường đi của người giao hàng Thí dụ: cho bài toán TSP với 6 đỉnh được cho bởi các tọa độ sau: c(1,7) d(15,7) b(4,3) e(15,4) a(0,0) f(18,0) 6 thành phố có tất cả 15 cạnh. Đó là các cạnh ab, ac, ad, ae, af, bc, bd, be, bf, cd, ce, cf, de, df, ef. Độ dài các cạnh ở đây là khoảng cách Euclide trong đó cạnh de = 3 là nhỏ nhất nên de được chọn vào chu trình. Kế đến là 3 cạnh ab,bc ef đều có độ dài 5 cả 3 cạnh đều thỏa mãn hai điều kiện nói trên nên đều được chọn vào chu trình, cạnh có độ dài nhỏ nhất kế tiếp là ac = 7.08 nhưng không thể đưa cạnh này vào chu trình vì nó sẽ tạo ra chu trình con (abca) cạnh df cũng bị lý do tương tự. Cạnh be cũng được xem xét rồi cũng bị loại do tạo ra đỉnh b và đỉnh e có cấp 3, tương tự chúng ta cũng loại bd. cd là cạnh tiếp theo được xét và được chọn cuối cùng ta có chu trình abcdefa với tổng độ dài là 50. Đây chỉ là một phương án tốt. Phương án tối ưu là chu trình acdefba với tổng độ dài là 48.39 4.2.1 Bài toán đường đi của người giao hàng c(1,7) d(15,7) c(1,7) d(15,7) b(4,3) e(15,4) b(4,3) e(15,4) a(0,0) f(18,0) a(0,0) f(18,0)4.2.1 Bài toán đường đi của người giao hàng Thuật toán:void Tsp { chutrinh = 0 // sắp xếp các cạnh trong E theo thứ tự tăng của độ dài Gia = 0 while E0 do { if(cạnh có thể chọn) //không tạo thành chu trình Chutrinh = chutrinh + [e] Gia = gia + đồdàicủa e } E = E – [e] }Độ phức tạp của thuật toán:Với đồ thị n đỉnh đầy đủ ta có n(n-1)/2 cạnh. Hơn nữa thuật toán chỉ phụ thuộc vào việc sắp xếp theo sự không giảm theo độ dài của các cạnh. Nên độ phức tạp của thuật toán cỡ O(n) nếu chọn phương pháp sắp xếp QuickSort.4.24.2.14.2.2Một số bài toán minh họa Bài toán đường đi của người giao hàng Bài toán các đoạn thẳng không giao nhau THUẬT TOÁN THAM LAMBài toán cái ba lô 4.2.3Bài toán cây khung nhỏ nhất 4.2.44.2.2 Bài toán các đoạn thẳng không giao nhau Bài toán Đầu vào: Cho họ các đoạn thẳng mở  Đầu ra: Tập các đoạn thẳng không giao nhau có lực lượng lớn nhất. Ứng dụng thực tế: Bài toán xếp thời gian biểu cho các hội thảo, bài toán phục vụ khách hành trên một máy, bài toán lựa chọn hành động (Ví dụ có n lời mời dự tiệc bắt đầu bởi ai kết thúc bởi bj, hãy lựa chọn sao cho đi đ­ược nhiều tiệc nhất).4.2.2 Bài toán các đoạn thẳng không giao nhau Đề xuất các thuật toán:Greedy 1: Sắp xếp các đoạn thẳng theo thứ tự tăng dần của đầu mút trái, bắt đầu từ tập S là tập rỗng, ta lần lượt xếp các đoạn thẳng trong danh sách đã sắp xếp và bổ sung đoạn thẳng đang xét vào S nếu nó không có điểm chung với bất cứ đoạn nào trong S. Thuật toán:void          Greedy1;      {         S = ;           //S là tập các đoạn thẳng cần tìm            While   (C  0)           {        (ai, bi)  đoạn đầu tiên trong C;                     C = C\(ai, bi);                    If  ()                    S = S  (ai, bi)           }                     }4.2.2 Bài toán các đoạn thẳng không giao nhau Độ phức tạp của thuật toán chủ yếu là nằm ở thủ tục sắp xếp. Nếu có n đoạn thẳng thì ta cần cỡ O(nlogn) để sắp xếp bằng phương pháp sắp xếp MergeSort.Tuy nhiên Greedy1 không cho lời giải tối ưu. Ví dụTa thấy rằng thuật toán sẽ lựa chọn dạ tiệc 1, trong khi phương án tối ưu của bài toán là (Dạ tiệc 2, Dạ tiệc 3) 4.2.2 Bài toán các đoạn thẳng không giao nhau Greedy2: Ta chọn đoạn có độ dài ngắn nhất bổ xung vào S. Tuy nhiên thuật toán tham lam này cũng không cho kết quả tối ưu. Sau đây là ví dụ Khi đó thuật toán sẽ lựa chọn (dạ tiệc 1) trong khi lời giải tối ưu của thuật toán là (dạ tiệc 2, dạ tiệc 3).4.2.2 Bài toán các đoạn thẳng không giao nhau Greedy3: Xắp xếp các đoạn thẳng theo thứ tự không giảm của mút phải. Bắt đầu từ tập S là tập rỗng, ta lần lượt xét các đoạn trong danh sách theo thứ tự đã sắp xếp và bổ xung đoạn thẳng đang xét vào S nếu nó không có điểm chung với bất cứ đoạn nào trong S. (Dạ tiệc nào kết thúc sớm sẽ được xét trước).4.2.2 Bài toán các đoạn thẳng không giao nhau Mệnh đề 1: Thuật toán Greedy3 cho lời giải tối ưu của bài toán về các đoạn thẳng không giao nhau.Chứng Minh: Giả sử Greedy3 không cho lời giải đúng. Phải tìm bộ dữ liệu C sao cho thuật toán không cho lời giải tối ưu. Giả sử G3(C) là lời giải tìm được bởi Greedy3. Gọi O là lời giải tối ưu có số đoạn thẳng chung với G3(C) là lớn nhất. Gọi X là đoạn thẳng đầu tiên có trong G3(C) nhưng không có trong O. Đoạn này là tồn tại, vì nếu trái lại thì G3(C)  O ( mâu thuẫn vì đã giả thiết G3(C)  O ) hay G3(C)  O ( Cũng mâu thuẫn vì khi đó thuật toán phải chọn đoạn thẳng X) (O cũng được sắp xếp giống G3(C)).Gọi Y là đoạn đầu tiên kể từ bên trái của O không có mắt trong G3(C). Đoạn Y cũng phải tồn tại (Chứng minh tương tự như trên).Khi đó mút phải của đoạn X phải ở bên trái (nhỏ hơn) mút phải của đoạn Y, vì nếu trái lại thuật toán sẽ chọn Y thay vì X. Xét             Rõ ràng O’ gồm các đoạn thẳng không giao với nhau, bởi vì X không giao với bất kì đoạn nào ở bên trái nó trong O’ (do G3(C) là chấp nhận được) cũng như không giao với bất cứ đoạn nào ở bên phải nó trong O’ (Do mút phải của X nhỏ hơn mút phải của Y và Y không giao với bất cứ đoạn nào ở bên phải Y trong O’). Do O’ có cùng lực lượng với O nên O’ cũng là tối ưu Tuy nhiên ta thấy rằng O’ giống với G3(C) hơn là O => mâu thuẫn với giả thiết.Độ phức tạp tính toán:Độ phức tạp của thuật toán chủ yếu phụ thuộc vào thủ tục sắp xếp. 4.24.2.14.2.2Một số bài toán minh họa Bài toán đường đi của người giao hàng Bài toán các đoạn thẳng không giao nhau THUẬT TOÁN THAM LAMBài toán cái ba lô 4.2.3Bài toán cây khung nhỏ nhất 4.2.44.2.3 Bài toán cái ba lô Bài toán: Một nhà thám hiểm cần sắp n vật vào ba lô của mình để thực hiện một cuộc thám hiểm ở bắc cực, vật thứ i có khối lượng là wi, có giá trị là ci (wi, ci N),   ba lô chỉ có thể mang được khối lượng tối đa là b (b  N). Vậy nhà thám hiểm cần chọn mang những vật nào? Ta có thể tóm tắt bài toán như sau:C = {1,2,3,..n}: tập chỉ số của đồ vật. Tìm I  C. Sao cho            ;           4.2.3 Bài toán cái ba lô Đề xuất thuật toán tham lam Greedy1: Sắp xếp theo thứ tự không tăng của giá trị. Xét các đồ vật theo thứ tự đã xếp, lần lượt chất các đồ vật đang xét vào ba lô nếu dung lượng còn lại trong ba lô đủ chứa nó.Tham số của bài toán là n = 3; b = 19.Đồ vật             1          2          3Giá trị             20        16         8Trọng lượng   14        10        6Thuật toán sẽ lựa chọn đồ vật 1 với tổng giá trị là 20, trong khi lời giải tối ưu của bài toán là lựa chọn (đồ vật 2, đồ vật 3 ) với tổng giá trị là 24. 4.2.3 Bài toán cái ba lô Greedy2: Sắp xếp đồ vật không giảm của trọng lượng. Lần lượt chất các đồ vật vào ba lô theo thứ tự đã sắp xếp.Tham số của bài toán là n = 3; b = 11Đồ vật             1          2          3Giá trị             10        16        28 Trọng lượng   5          6          10Thuật toán sẽ lựa chọn (đồ vật 1, đồ vật 2) với tổng giá trị là 26, trong khi lời giải tối ưu của bài toán là (đồ vật 3) với tổng giá trị là 28 4.2.3 Bài toán cái ba lô  Greedy3: Sắp xếp các đồ vật theo thứ tự không tăng của giá trị một đơn vị trọng lượng (ci /wi). Lần lượt xét: Tham số của bài toán: n = 2; b  2.Khi đó thuật toán chỉ lựa chọn được đồ vật 1 với tổng giá trị là 10, trong khi lời giải tối ưu của bài toán lựa chọn đồ vật 2 với tổng giá trị là 10b-1 ( 10.2-1 = 19 > 10).4.2.3 Bài toán cái ba lô Greedy4: Gọi Ij là lời giải thu được theo thuật toán Greedyj (j = 1, 2, 3). Gọi                                                                 Định lý: Lời giải I4 thoả mãn bất đẳng thứcTrong đó f* là giá trị tối ưu của bài toán.4.24.2.14.2.2Một số bài toán minh họa Bài toán đường đi của người giao hàng Bài toán các đoạn thẳng không giao nhau THUẬT TOÁN THAM LAMBài toán cái ba lô 4.2.3Bài toán cây khung nhỏ nhất 4.2.44.2.4 Bài toán cây khung nhỏ nhất Bài toánCho G = (V, E) là đồ thị vô hướng liên thông với tập đỉnh V = {1, 2,, n} và tập cạnh E gồm m cạnh. Mỗi cạnh e của đồ thị G được gán với một số thực c(e) gọi là độ dài của nó. Giả sử H = (V, T) là cây khung của đồ thị G. Ta gọi độ dài c(H) của cây khung H là tổng độ dài của các cạnh của nó.Bài toán đặt ra là, trong số tất cả các cây khung của đồ thị G, hãy tìm cây khung có độ dài nhỏ nhất4.2.4 Bài toán cây khung nhỏ nhất Thí dụ: 4.2.4 Bài toán cây khung nhỏ nhất Giải bài toán cây khung nhỏ nhất:liệt kê tất cả các cây khung của đồ thị và chọn trong số chúng cây khung nhỏ nhất. Phương pháp như vậy trong trường hợp đồ thị đầy đủ sẽ đòi hỏi thời gian cỡ nn-2 ->không thể thực hiện được.Thuật toán Kruskal và thuật toán Prim. Cả hai thuật toán Kruskal và Prim đều dựa trên tư tưởng của các giải thuật tham lam Ở mỗi bước của thuật toán ta chọn và bổ sung vào cây khung cạnh có trọng số nhỏ nhất có thể.4.2.4 Bài toán cây khung nhỏ nhất Thuật toán Kruskal:Thuật toán sẽ xây dựng tập cạnh T của cây khung nhỏ nhất H = (V, T) theo các bước: B1: Sắp xếp các cạnh của đồ thị G theo thứ tự không giảm của độ dài. B2: T = Ø, B3: Trong khi |T|0 Chọn cạnh có trọng số nhỏ nhất bổ sung vào T sao cho T không tạo thành chu trình. Thuật toán sẽ kết thúc khi ta thu được tập T gồm n-1 cạnh.4.2.4 Bài toán cây khung nhỏ nhất void Kruskal;{ T = Ø; while ((|T| Ø)) { chọn e là cạnh nhỏ nhất trong E; E = E\[e]; if (T U [e] không chứa chu trình) T = T U [e]; } if (|T| c[u, v] ) { d[v] = c[u,v]; Near[v] = u; } }}camcntt@yahoo.comThank You !