Tiểu luận học phần Phân tích Thi ết kế thuật toán-Thuật toán tham lam (greedy algorithm)

à hắn ta có thể mang thêm nữa, hắn ta lấy càng nhiều càng tốt như món hàng với đơn giá cao nhất tiếp theo, tiếp tục cho đến khi hắn ta không thể mang được nữa. Vì vậy, việc sắp xếp các món hàng theo đơn giá, thuật toán tham lam chạy với độ phức tạp O(nlogn) thời gian. Sự chứng minh rằng bài toán chiếc ba lô phân số có chiến lược lựa chọn tham lam được để lại cho bài tập 16.2-1. Hình 16.2: Chiến lược tham lam không thực hiện trong bài toán chiếc ba lô 0-1. (a) tên trộm phải chọn một tập con của ba món hàng mà khối lượng của chúng không vượt quá 50 pound. (b) Tập con tối ưu bao gồm món hàng 2 và 3. Giải pháp bất kỳ có món hàng 1 là không tối ưu, mặc dù món hàng 1 có đơn giá lớn nhất. (c) trong bài toán chiếc ba lô phân số, lấy các món hàng theo thứ tự sắp xếp đơn giá lớn nhất của mỗi pound của các món hàng đưa lại một giải pháp tối ưu. Để thấy rằng chiến lược tham lam này không thực hiện cho bài toán chiếc ba lô 0-1, xem trường hợp của bài toán được minh hoạ trong hình 16.2(a). Có 3 món hàng, và cái ba Thuật toán tham lam Trang 18 lô có thể chứa 50 pound. Món hàng 1 nặng 10 pound có giá tri 60 dollar. Món hàng 2 nặng 20 pound và có giá trị 100 dollar. Món hàng 3 nặng 30 pound và có giá trị 120 dollar. Vì vậy, đơn giá của món hàng 1 là 6 dollar mỗi pound, nó lớn hơn đơn giá của món hàng 2 (5 dollar mỗi pound) hay cả món hàng 3 (4 dollar mỗi pound). Chiến lược tham lam, bởi vậy, sẽ lấy món hàng 1 trước tiên. Như có thể thấy từ sự phân tích ở hình 16.2(b). Tuy nhiên, giải thuật tối ưu lấy món hàng 2 và 3, để lại 1. Hai giải thuật có khả năng mà bao gồm món hàng 1 là đều không tối ưu. Tuy nhiên, trong bài toán phân số tương ứng, chiến lược tham lam, lấy món hàng 1 trước tiên, mang lại một giải thuật tối ưu, như biểu diễn ở hình 16.2(c). Việc lấy món hàng 1 không thực hiện trong bài toán 0-1 bởi vì tên trộm không thể làm đầy ba lô của hắn đối với sức chứa, và khoảng trống hạ thấp giá trị hiệu qủa của mỗi pound của tải trọng của hắn. Trong bài toán 0-1, khi ta xem một món hàng cho vào chiếc ba lô, ta phải so sánh giải thuật đối với bài toán con trong đó món hàng được tính đến với giải thuật đối với bài toán con trong đó món hàng được tính đến trước khi ta có thể thực hiện lựa chọn. Bài toán được thành lập theo cách này làm tăng lên đối với nhiều bài toán con phủ chồng - một dấu chất lượng của quy hoạch động,và thực vậy, quy hoạch động có thể được sử dụng để giải quyết bài toán 0-1.(Xem bài tập 16.2-2) Thuật toán tham lam Trang 19 PHẦN 3: MÃ HUFFMAN Các mã Hufman là phương pháp hiệu quả và được sử dụng một cách rộng rãi trong việc nén dữ liệu, thường tiết kiệm từ 20% đến 90%, phụ thuộc vào đặc tính của tập tin được nén. Ta xem như dữ liệu đó là một chuỗi các ký tự. Giải pháp tham lam của Huffman sử dụng một bảng gồm các tần số xuất hiện của các ký tự để xây dựng nên một cách biểu diễn tối ưu mỗi ký tự dưới dạng một chuỗi nhị phân. Giả sử ta có tập tin dữ liệu gồm 100,000 ký tự mà ta muốn lưu trữ ở dạng nén. Ta nhận thấy rằng những ký tự trong tập tin đó xuất hiện với tần số được cho bởi minh hoạ 16.3. Tức là, chỉ có 6 ký tự khác nhau xuất hiện, và ký tự a xuất hiện 45,000 lần. Có rất nhiều cách để biểu diễn thông tin của một tập tin nào đó. Ta xét bài toán thiết kế mã ký tự nhị phân (hoặc gọi tắt là mã) ở khía cạnh nào đó mỗi ký tự được biểu diễn bởi một chuỗi nhị phân duy nhất. Nếu ta sử dụng mã có chiều dài cố định, ta cần 3 bit để biểu diễn 6 ký tự: a = 000, b = 001,..., f = 101. Phương pháp này yêu cầu có 300,000 bit để mã hoá toàn bộ tập tin đó. Ta có thể làm điều này tốt hơn không? Mã có chiều dài bất định có thể thực hiện tốt hơn đáng kể so với mã có chiều dài cố định, bằng cách cho những từ mã ký tự ngắn thường xuyên và những từ mã ký tự dài không thường xuyên. Minh hoạ 16.3 chỉ ra một cách mã hoá như thế; ở đây chuỗi 1 bit 0 biểu diễn a, và chuỗi 4 bit 1100 biểu diễn f. Cách mã hoá này cần: (45.1 + 13.3 + 12.3 + 16.3 + 9.4 + 5.4).1,000 = 224,000 bit để biểu diễn tập tin đó, tiết kiệm khoảng chừng 25%. Thật vậy, đây là cách mã hoá tối ưu cho tập tin này, như ta thấy. 3.1. Mã tiền tố Ở đây ta chỉ xét những mã trong đó không có từ mã nào là tiền tố của vài từ mã khác. Những mã này được gọi là mã tiền tố. Điều này có thể chỉ ra rằng việc nén dữ liệu tối ưu có thể thực hiện được bằng việc mã hoá ký tự có thể luôn luôn được hoàn thành với một mã tiền tố, vì vậy không mất tính tổng quát trong việc giới hạn sự chú ý đến mã tiền tố. Việc giải mã luôn luôn đơn giản đối với bất cứ mã ký tự nhị phận nào; ta chỉ việc ghép nối các từ mã biểu diễn mỗi ký tự của tập tin đó với nhau. Ví dụ, với mã tiền tố có Thuật toán tham lam Trang 20 độ dài bất định của minh hoạ 16.3, ta mã hoá tập tin gồm 3 ký tự abc là 0.101.100 = 0101100, những chỗ mà ta sử dụng dấu “.” biểu diễn phép ghép nối. A b c d e f Tần số (ngàn) 45 13 12 16 9 5 Từ mã có chiều dài cố định 000 001 010 011 100 101 Từ mã có chiều dài bất định 0 101 100 111 1101 1100 Minh hoạ 16.3 Bài toán mã hoá ký tự. Một tập tin dữ liệu gồm 100,000 ký tự chỉ chứa các ký tự a-f, với tần số được cho trước. Nếu mỗi ký tự được chỉ định một từ mã 3 bit, tập tin đó có thể được mã hoá với 300,000 bit. Sử dụng mã có chiều dài bất định cho thấy tập tin đó có thể được mã hoá với 224,000 bit. Mã tiền tố cần thiết bởi vì chúng làm đơn giản hoá việc giải mã. Vì rằng không có từ mã nào là tiền tố của bất kỳ từ mã khác, nên từ mã bắt đầu một tập tin được mã hoá là rất rõ ràng. Ta có thể nhận biết một cách đơn giản từ mã lúc đầu, dịch nó trở lại ký tự gốc ban đầu, và lặp lại quy trình giải mã đối với phần còn lại của tập tin đã mã hoá. Ta có ví dụ, chuỗi 001011101 phân ra một cách duy nhất là 0.0.101.1101, đây là dạng giải mã đối với aabe. Quá trình giải mã cần có sự biểu diễn thích hợp cho mã tiền tố sao cho có thể dễ dàng chọn ra từ mã ban đầu. Một cây nhị phân mà các lá của nó là các ký tự cho trước quy định một cách biểu diễn như vậy. Ta diễn dịch từ mã nhị phân của một ký tự chính là đường đi từ gốc đến ký tự đó, ở đó 0 có nghĩa là “đi đến con trái” và 1 có nghĩa là “đi đến con phải”. Minh hoạ 16.4 chỉ ra các cây có 2 mã của ví dụ. Lưu ý rằng những cây này không là cây nhị phân tìm kiếm, những lá không cần xuất hiện trong thứ tự sắp xếp và những nút trong không chứa khoá ký tự. Thuật toán tham lam Trang 21 Minh hoạ 16.4: Cây tương ứng với biểu đồ mã hoá ở minh hoạ 16.3. Mỗi lá được gán nhãn là một ký tự và tần số xuất hiện của nó. Mỗi nút trong được gán nhãn là tổng của tần số các lá trên cây con của nó. (a) Cây tương ứng với mã có chiều dài cố định a = 000,..., f = 101. (b) Cây tương ứng với mã tiền tố tối ưu a = 0, b = 101,..., f= 1100. Một mã tối ưu cho một tập tin luôn luôn được biểu diễn bằng một cây nhị phân đầy đủ, trong đó mọi nút không là lá đều có 2 con (xem bài tập 16.3-1). Mã có chiều dài cố định trong ví dụ của ta là không tối ưu vì rằng cây của nó thể hiện ở minh hoạ 16.4(a) không phải là cây nhị phân đầy đủ: có những từ mã bắt đầu 10… nhưng không bắt đầu 11…Vì rằng bây giờ ta có thể hạn chế chú ý vào các cây nhị phân đầy đủ, nên có thể nói rằng nếu C là bảng chữ cái từ những ký tự được cho trước và tất cả tần số ký tự là xác định, thì cây cho một mã tiền tố tối ưu có chính xác là C lá, mỗi lá cho một ký tự của bảng chữ cái, và có đúng 1C − nút trong (xem Bài tập B.5-3). Cho một cây T tương ứng với một mã tiền tố, dễ dàng để tính được số bit yêu cầu để mã hoá một tập tin. Với mỗi ký tự c trong bảng chữ cái C, đặt f(c) là tần số của c trong tập tin đó và đặt dT(c) là độ sâu của lá chứa ký tự c trên cây. Lưu ý rằng dT(c) cũng là chiều dài của từ mã của ký tự c. Số bit cần có để mã hoá một tập tin là như sau: B(T)= ( ) ( )T c C f c d c ∈ ∑ (16.5) điều này ta định nghĩa là mức phí của cây T. Thuật toán tham lam Trang 22 3.2. Xây dựng mã Huffman Huffman phát minh ra giải thuật tham lam nhằm xây dựng mã tiền tố tối ưu gọi là giải thuật mã hoá Huffman. Đúng với nhận xét của ta ở phần 16.2, sự kiểm chứng về độ tin cậy đúng đắn trên thuộc tính lựa chọn tham lam và cấu trúc con tối ưu. Hơn nữa chứng minh rằng hiểu được những thuộc tính này và rồi phát triển dạng giả mã, đầu tiên ta biểu diễn dưới dạng giả mã. Làm như thế sẽ giúp làm rõ giải thuật chọn những chọn lựa tham lam như thế nào. Trong dạng giả mã sau đây, ta giả sử rằng C là một tập hợp gồm n ký tự và mỗi ký tự c∈C là phần tử với tần số xác định f[c]. Giải thuật xây dựng cây T tương ứng với mã tối ưu theo cách từ trên xuống. Nó bắt đầu với một tập gồm C lá và thực hiện một chuỗi gồm 1C − phép “kết hợp” để tạo ra cây cuối cùng. Một hàng đợi ưu tiên nhỏ nhất Q, được lập trên khoá f, được sử dụng để nhận biết 2 đối tượng có tần số nhỏ nhất để kết hợp với nhau. Kết quả của sự kết hợp 2 phần tử đó là một phần tử mới mà tần số của nó là tổng của các tần số của 2 phần tử được kết hợp. Chẳng hạn, giải thuật Huffman được chỉ ra như ở minh hoạ 16.5. Vì rằng có 6 mẫu tự trong bảng chữ cái, kích thước chuỗi ban đầu là 6, và 5 bước kết nối được yêu cầu để xây dựng cây. Cây cuối cùng biểu diễn mã tiền tố tối ưu. Từ mã đối với mẫu tự là một chuỗi các nhãn dọc theo đường đi từ gốc đến mẫu tự đó. HUFFMAN(C) 1 n← |C| 2 Q←C 3 fori 1 ton - 1 4 do allocate a new node z 5 left[z] ←x← EXTRACT-MIN (Q) 6 right[z] ←y← EXTRACT-MIN (Q) 7 f [z] ←f [x] + f [y] 8 INSERT(Q, z) 9 return EXTRACT-MIN(Q) ▹Return the root of the tree. Thuật toán tham lam Trang 23 Minh hoạ 16.5: Các bước của giải thuật Huffman với tần số được cho trong minh hoạ 16.3 mỗi đường đi chỉ ra nội dung của chuỗi được sắp xếp theo thứ tự tăng dần của tần số. Ở mỗi bước, 2 cây với tần số thấp nhất được kết hợp với nhau. Các lá được thể hiện bởi các hình chữ nhật chứa một ký tự và tần số của nó. Những nút trong được thể hiện bởi các vòng tròn chứa tổng các tần số của các nút con của nó. Nút ngoài cùng kết nối với nút trong bởi các con của nó có nhãn là 0 nếu đó là cạnh đi đến nút con trái và 1 nếu đó là cạnh đi đến nút con phải. Từ mã cho một mẫu tự là một dãy các nhãn trên những cạnh kết nối gốc với lá biểu diễn cho mẫu tự đó. (a) Tập hợp ban đầu của n=6 nút, mỗi nút là một mẫu tự. (b)-(e) các giai đoạn trung gian. (f) Cây cuối cùng Dòng 2 khởi tạo hàng đợi ưu tiên nhỏ nhất Q với các ký tự trong C. Vòng For ở dòng 3-8 lặp lại nhiều lần động tác trích ra 2 nút x và y có tần số thấp nhất trong hàng đợi, và thay thế chúng trong hàng đợi với một nút mới z thực hiện kết hợp chúng với nhau. Tần số của z được tính là tổng của các tần số của x và y ở dòng 7. Nút z có x là nút con trái và y là nút con phải. (Thứ tự này là tuỳ ý; đổi vị trí cây con trái và phải đều mang lại một mã khác có mức hao phí tương đương). Sau n-1 phép kết hợp, nút thứ nhất trái được để lại trong hàng đợi - gốc của cây mã hoá - được trả về giá trị ở dòng 9. Thuật toán tham lam Trang 24 Phân tích thời gian chạy giải thuật Huffman cho thấy rằng Q được thực hiện như một đống nhị phân (xem Chương 6). Cho một tập hợp C gồm n ký tự, giá trị ban đầu của Q ở dòng 2 có thể được thực hiện trong O(n) thời gian dùng cho thủ tục BUILD_MIN_HEAP trong phần 6.3. Vòng For ở dòng 3-8 được thực hiện chính xác là n-1 lần, và bởi vì mỗi phép toán đống yêu cầu thời gian là O(lgn), nên vòng lặp đóng góp O(nlgn) vào thời gian chạy thuật toán. Vì vậy, tổng thời gian chạy của giải thuật Huffman trên tập hợp gồm n ký tự là O(nlgn). 3.3. Tính đúng đắn của giải thuật Huffman Để chứng minh thuật toán tham lam Huffman là đúng, ta chỉ ra rằng bài toán xác định mã tiền tố tối ưu thể hiện lựa chọn tham lam và những tính chất cấu trúc con. Bổ đề tiếp theo chỉ ra thuộc tính lựa chọn tham lam có. a. Bổ đề 16.2 Cho C là một bảng chữ cái mà mỗi ký tự c C∈ có tần số là f[c]. Cho x và y là 2 ký tự trong C có tần số thấp nhất. Thì tồn tại mã tiền tố tối ưu đối với C mà trong đó những từ mã của x và y có cùng chiều dài và chỉ khác duy nhất ở bit cuối cùng. Chứng minh: Ý tưởng của phần chứng minh đó là chọn một cây T biểu diễn mã tiền tố tối ưu tuỳ ý và sửa đổi nó để tạo thành một cây biểu diễn mã tiền tố tối ưu khác sao cho các ký tự x và y xuất hiện như những lá anh em ruột có chiều sâu cực đại trên một cây mới. Nếu ta có thể thực hiện điều này, thì các từ mã của chúng sẽ có cùng chiều dài và chỉ khác nhau ở bit cuối cùng. Cho a và b là hai ký tự là các lá anh em ruột có chiều sâu cực đại trong T. Không mất tính tổng quát, ta mặc nhận rằng [a] f[b]f ≤ và [x] f[y]f ≤ . Vì rằng f[x] và f[y] là hai tần số của lá thấp nhất, theo thứ tự và f[a] và f[b] là các tần số tuỳ ý, theo thứ thự, nên ta có [x] f[a]f ≤ và [y] f[b]f ≤ . Như đã có ở minh hoạ 16.6, ta tráo đổi các vị trí trong T của a và x để tạo ra một cây mới T’, và sau đó ta tráo đổi các vị trí trên câu T’ của b và y để tạo ra cây mới T”. Qua phương trình (16.5), sự khác biệt đáng kể về mức hao phí giữa T và T’ là: Thuật toán tham lam Trang 25 Minh hoạ 16.6: Hình ảnh minh hoạ bước mấu chốt trong chứng minh của Bổ đề 16.2. Trong cây tối ưu T, các lá a và b là hai lá sâu nhất và là anh em ruột với nhau. Các lá x và y là hai lá mà giải thuật Huffman kết hợp với nhau đầu tiên; chúng xuất hiện ở các vị trí tuỳ ý trên T. Các lá a và x được trao đổi để thu được cây T’. Sau đó, các lá b và y được trao đổi để thu được cây T”. Bởi vì mỗi lần trao đổi không làm tăng mức phí, kết quả cây T” cũng như cây tối ưu. bởi vì cả f[a]-f[x] và dT(a)-dT(x) là không âm. Đặc biệt hơn, f[a]-f[x] là không âm bởi vì x là lá có tần số cực tiểu và dT(a)-dT(x) là không âm bởi vì a là lá có chiều sâu cực đại trên T. Tương tự, tráo đổi a và b mà không là tăng mức hao phí, và B(T’)-B(T”) là không âm. Bởi vậy, ( ") ( )B T B T≤ , và vì rằng T là tối ưu, ( ) ( ")B T B T≤ , suy ra B(T)=B(T”). Vì vậy, T” là cây tối ưu trong đó x và y xuất hiện như những lá anh em ruột có chiều sâu cực đại, mà bổ đề theo. Bổ đề 16.2 hàm ý rằng quá trình xây dựng một cây tối ưu bởi các phép kết hợp có thể, không mất tính tổng quát, bắt đầu với một lựa chọn tham lam của tiến kết hợp hai ký tự có tần số thấp nhất với nhau . Tại sao điều này là một lựa chọn tham lam? Ta có thể xem mức hao phí của phép kết hợp đơn lẻ dưới dạng tổng của các tần số của hai phần tử được kết hợp. Bài tập 16.3-3 chỉ ra rằng tổng mức hao phí các phép hợp của nó. Đối với tất cả phép kết hợp có thể ở mỗi bước, Huffman chọn ra một phép kết hợp mang giá trị nhỏ nhất. Bổ đề tiếp theo sau đây chỉ ra rằng bài toán xây dựng mã tiền tố tối ưu có tính chất cấu trúc con - tối ưu. Thuật toán tham lam Trang 26 b. Bổ đề 16.3 Cho C là một bảng chữ cái cho trước với tần số f[c] xác định với mỗi ký tự c C∈ . Cho x và y là hai ký tự trong C với tần số nhỏ nhất. Cho C’ là bảng chữ cái C với x và y bị xoá và có thêm ký tự mới z, vì vậy C’=C-{x,y}∪ {z}; xác định f của C’ cũng là của C, với f[z]=f[x]+f[y]. Cho T’ là cây bất kỳ biểu diễn mã tiền tố tối ưu của bảng chữ cái C’ thì cây T, thu được từ T’ bằng việc thay thế nút lá z với một nút trong có x và y là con, biểu diễn mã tiền tố tối ưu cho bảng chữ cái C. Chứng minh: Đầu tiên ta chỉ ra rằng giá trị B(T) của cây T có thể được thể hiện dưới dạng mức hao phí B(T’) của cây T’ bằng cách xét các mức hao phí thành phần trong phương trình (16.5). Với mỗi {x,y}c C∈ − , ta có dT(c)=dT’(c), và do đó: f[c]dT(c)=f[c]dT’(c) Vì rằng dT(x)=dT(y)=dT’(z)+1, ta có: f[x]dT(x) + f[y]dT(y) = (f[x] + f[y])(dT’(z) + 1) = f[z]dT’(z) + (f[x] + f[y]) từ đó ta kết luận rằng: B(T) = B(T’) + f[x] + f[y] Hoặc, ta có tương đương: B(T’) = B(T) - f[x] - f[y] Bây giờ, ta chứng minh bổ đề bằng phản chứng. Giả sử rằng T biểu diễn mã tiền tố không tối ưu cho C. Thì tồn tại một cây T“ sao cho B(T“)<B(T). Không mất tính tổng quát (bởi Bổ đề 16.2), T“ có x và y là anh em ruột. Cho T’“ là cây T“ với cha mẹ chung của x và y được thay thế bởi một lá z có tần số f[z]= f[x] + f[y]. Thì: B(T’’’)=B(T’’)-f[x]-f[y] <B(T)-f[x]-f[y] = B(T’) Dẫn đến mâu thuẫn đối với giả thiết cho rằngT’ biểu diễn mã tiền tố tối ưu cho C’. Vì vậy, T phải biểu diễn mã tiền tố tối ưu cho bảng chữ cái C. c. Bổ đề 16.4 Thủ tục Huffman hình thành nên mã tiền tố tối ưu. Chứng minh từ Bổ đề 16.2 và 16.3 3.4 Cài đặt thuật toán (xem phần phụ lục) Thuật toán tham lam Trang 27 PHẦN 4: CƠ SỞ LÝ THUYẾT CỦA PHƯƠNG PHÁP THAM LAM Có một lý thuyết rất hay về giải thuật tham lam mà ta sẽ tóm tắt trong phần này. Lý thuyết này rất hữu ích trong việc xác định khi phương pháp tham lam dẫn đến những giải pháp tối ưu. Nó liên quan đến cấu trúc tổ hợp đã biết như “matroids”. Mặc dù lý thuyết này không áp dụng cho tất cả các trường hợp mà phương pháp tham lam đã áp dụng (ví dụ, không áp dụng cho bài toán lựa chọn hoạt động ở phần 16.1 hoặc bài toán mã Huffman ở phần 16.3), nó áp dụng cho nhiều trường hợp quan trọng thiết thực. Hơn nữa, lý thuyết này đang được phát triển nhanh chóng và mở rộng để áp dụng cho nhiều ứng dụng hơn nữa; hãy đọc mục lục ở cuối chương để tham khảo. 4.1. Matroid Một matroid là một cặp có thứ thự M=(S, l ) thoả mãn những điều kiện sau đây: 1. S là một tập không rỗng hữu hạn 2. l là một họ các tập con khác rỗng của S, được gọi là các tập con độc lập của S, sao cho nếu B∈l và A⊆B thì A∈l . Ta nói rằng l là di truyền nếu nó thoả mãn tính chất này. Lưu ý rằng tập rỗng nhất thiết là một phần tử của l 3. Nếu A∈l , B∈l và A B< thì có một phần tử x A B∈ − sao cho {x}A∪ ∈l . Ta nói rằng M thoả mãn tính chất trao đổi. Từ “matroid” là do Hassler Whitney đặt. Ông nghiên cứu về matroid ma trận, trong đó các phần tử của S là các dòng của ma trận cho trước và một tập hợp các dòng độc lập nếu chúng phụ thuộc tuyến tính theo nghĩa thông thường. Dễ dàng thấy rằng cấu trúc này định nghĩa một matroid (xem Bài tập 16.4-2). Với ví dụ khác của matroid, cho rằng matroid đồ thị MG=(SG,G) xác định dưới dạng đồ thị vô hướng G=(V,E) như sau. • Tập SG được định nghĩa là tập E, là tập các cạnh của G. • Nếu A là một tập con của E thì A G∈l nếu và chỉ nếu A là không có chu trình. Tức là, một tập gồm các cạnh A là độc lập nếu và chỉ nếu đồ thị con GA=(V,E) hình thành nên rừng. Thuật toán tham lam Trang 28 Matroid đồ thị MG có liên quan mật thiết với bài toán tìm cây khung nhỏ nhất, sẽ được trình bày ở Chương 23. a. Định lý 16.5: Nếu G=(V,E) là đồ thị vô hướng thì MG=(SG,G) là một matroid. Chứng minh: Rõ ràng, SG =E là một tập hợp hữu hạn. Ngoài ra, Gl là di truyền, vì rằng một tập con của rừng là một rừng. Nói cách khác, xoá các cạnh từ chu trình ra khỏi tập các cạnh thì không thể tạo chu trình. Do đó, ta chỉ cần chứng tỏ rằng MG thoả mãn tính chất trao đổi. Giả sử rằng GA=(V,A) và GB=(V,B) là những rừng của G và B A> . Tức là, A và B tập hợp các cạnh không tạo chu trình, và B chứa nhiều cạnh hơn A. Từ định lý B.2 suy ra rằng một rừng có k cạnh có chính xác là V k− cây. (Để chứng minh điều này bằng cách khác, bắt đầu từ V cây, mỗi cây bao gồm nhiều đỉnh và không có cạnh nào. Sau đó, mỗi cạnh được thêm vào rừng sẽ làm giảm số lượng cây là một). Do đó, rừng GA chứa V A− cây, và rừng GB chứa V B− cây. Vì rằng rừng GB có một số cây nhiều hơn rừng GA, rừng GB có chứa một cây T mà đỉnh của nó là ở hai cây khác nhau trong rừng GA. Ngoài ra, bởi vì T liên thông nên nó phải chứa cạnh (u,v) sao cho đỉnh u và v nằm ở những cây khác nhau của rừng GA. Vì rằng cạnh (u,v) có thể được thêm vào rừng GA mà không tạo chu trình. Vì vậy, MG thoả mãn tính chất trao đổi, hoàn tất việc chứng minh rằng MG là matroid. Cho một matroid M=(S, l ), ta gọi một phần tử x∉A là phần tử mở rộng của A∈l nếu x có thể được thêm vào A trong khi vẫn đảm bảo tính độc lập; Do đó, x là phần tử mở rộng của A nếu A {x}∪ ∈l . Ví dụ, cho một matroid đồ thị MG. Nếu A là tập hợp các cạnh độc lập thì cạnh e là phần tử mở rộng của A nếu và chỉ nếu e không thuộc A và khi thêm e vào A thì không tạo chu trình. Nếu A là một tập con độc lập trong matroid M, ta nói rằng A là lớn nhất nếu không có phần tử mở rộng. Tức là, A là lớn nhất nếu nó không được chứa trong bất kỳ tập con độc lập lớn hơn của M. Tính chất sau thường hữu ích. b. Định lý 16.6: Mọi tập con độc lập lớn nhất trong matroid đều có cùng lực lượng. Thuật toán tham lam Trang 29 Chứng minh: Giả sử điều mâu thuẫn rằng A là tập con độc lập lớn nhất của M và tồn tại một tập con độc lập lớn nhất B của M. Thì tính chất trao đổi chỉ ra rằng A được mở rộng thành một tập độc lập lớn hơn A {x}∪ với x B A∈ − , điều này mâu thuẫn với giả thiết A là lớn nhất. Để minh hoạ định lý này, cho một matroid đồ thị MG của đồ thị liên thông, vô hướng G. Mỗi tập con độc lập lớn nhất của MG phải là một cây với 1V − cạnh nối đến tất cả các đỉnh của G. Cây như thế được gọi là cây khung của G. Ta nói rằng một matroid M=(S, l ) là có trọng số nếu có một hàm liên quan đến trọng lượng ω nhận một trọng số hoàn toàn dương ( )xω đối với mỗi phần tử x S∈ . Hàm trọng số ω mở rộng với những tập con của S bằng công thức: ( ) ( ) x A A xω ω ∈ =∑ với bất kỳ tập A S⊆ . Ví dụ, nếu ta đặt ( )eω là độ dài của cạnh e trong matroid đồ thị MG, thì ( )Aω là tổng độ dài của các cạnh trong tập cạnh A. 4.2. Giải thuật tham lam trên một matroid trọng số Nhiều bài toán mà cách tiếp cận tham lam đưa ra những giải pháp tối ưu có thể được trình bày rõ ràng bởi việc tìm ra tập con độc lập có trọng số lớn nhất trong matroid trọng số. Tức là, ta được cho một matroid trọng số M=(S,l ) và ta muốn tìm ra một tập A∈l độc lập sao cho ( )Aω được cực đại hoá. Ta gọi tập con độc lập và có trọng số lớn nhất là tập con tối ưu của matroid. Bởi vì trọng số ( )xω của bất kỳ phần tử x S∈ là số dương, một tập con tối ưu luôn là tập con độc lập lớn nhất. Ví dụ, trong bài toán tìm cây khung nhỏ nhất, ta có một đồ thị vô hướng, liên thông G=(V,E) và hàm tính độ dài ω sao cho ( )eω là độ dài của cạnh e. (Ta sử dụng đại lượng “độ dài” để chỉ trọng số của cạnh ban đầu trong đồ thị, “trọng lượng” để chỉ trọng số trong matroid). Ta cần tìm ra tập con của các cạnh mà kết nối tất cả các đỉnh với nhau và có tổng độ dài nhỏ nhất. Để xem ví dụ này như là một bài toán tìm một tập con tối ưu của matroid, cho một matroid trọng số MG với hàm trọng số 'ω , trong đó '( )eω = (0) ( )eω ω− và 0ω thì lớn hơn độ dài tối đa của một cạnh bất kỳ. Trong matroid trọng số này, tất cả trọng số là số dương và một tập con tối ưu là một cây khung có tổng độ dài nhỏ nhất Thuật toán tham lam Trang 30 trong đồ thị ban đầu. Cụ thể hơn, mỗi tập con độc lập lớn nhất A tương ứng với một cây khung và bởi vì: 0'( ) ( 1) ( )A V Aω ω ω= − − Trong một tập con độc lập lớn nhất bất kỳ, một tập con độc lập đạt cực đại về '( )Aω thì phải cực tiểu ( )Aω . Vì vậy, một thuật toán bất kỳ có thể tìm ra một tập con tối ưu A trong matroid tuỳ ý có thể giải quyết bài toán cây khung nhỏ nhất Chương 23 đưa ra thuật toán cho bài toán cây khung nhỏ nhất, nhưng ở đây ta có một thuật toán tham lam thực hiện trên matroid trọng số bất kỳ. Giải thuật trên nhận dữ liệu vào là một matroid trọng số M=(S, l ) với một hàm trọng số dương và nó trả về một tập con tối ưu A. Trong phần giả mã, ta biểu diễn những thành phần của M bởi S[M] và [M]l và hàm trọng số bởi ω . Thuật toán là tham lam bởi vì nó xem mỗi phần tử x S∈ lần lượt được sắp xếp theo trọng số giảm dần đều và trực tiếp cộng nó vào tập A đang được tích luỹ nếu {x}A∪ là độc lập. GREEDY(M,w) 1. A←∅ 2. Sắp xếp S[M] theo thứ tự giảm dần bởi trọng lượng w 3. for mỗi x∈S[M] lấy ra từ tập được sắp xếp giảm dần theo trọng lượng w(x) 4. do if A∪{x}∈l[M] 5. then A←A∪{x} 6. return A Những phần tử thuộc S được sắp xếp giảm dần theo trọng lượng. Nếu phần tử x được xem có thể thêm vào A trong khi vẫn duy trì sự độc lập của A, thì đúng là nó. Bằng không, x bị loại bỏ. Bởi vì tập rỗng là độc lập bởi định nghĩa về matroid và x được thêm vào A với điều kiện A ∪ {x} là độc lập, nên tập con A luôn luôn độc lập bằng phương pháp qui nạp. Vì vậy, GREEDY luôn trả về một tập con độc lập A. Như sẽ thấy dưới dây A là tập con trọng số khả dĩ lớn nhất, vì vậy A một tập con tối ưu. Thuật toán tham lam Trang 31 Thật dễ dàng để phân tích thời gian thực hiện của thuật toán tham lam. Cho n biểu diễn cho S . Giai đoạn sắp xếp mất thời gian là O(nlogn). Dòng 4 thực hiện chính xác là n lần, mỗi lần là một phần tử của S. Mỗi lần thực hiện dòng 4 yêu cầu là tập A {x}∪ có độc lập không. Nếu mỗi lần kiểm tra như thế chiếm O(f(n)), thì một giải thuật hoàn chỉnh chạy trong thời gian O(nlgn + nf(n)) Ta chứng minh rằng GREEDY trả về một tập con tối ưu. a. Bổ đề 16.7: (Matroid có tính chất lựa chọn tham lam) Giả sử rằng M=(S,l ) là một matroid trọng số với hàm trọng số là ω và S được sắp xếp theo thứ tự giảm dần theo trọng lượng. Cho x là phần tử đầu tiên của S sao ch