Tài liệu Thiết kế thuật toán dựa trên ý tưởng của phương pháp tham lam

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG CÀ THỊ THÙY LINH THIẾT KẾ THUẬT TOÁN DỰA TRÊN Ý TƯỞNG CỦA PHƯƠNG PHÁP THAM LAM LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Thái Nguyên- 2012 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG CÀ THỊ THÙY LINH THIẾT KẾ THUẬT TOÁN DỰA TRÊN Ý TƯỞNG CỦA PHƯƠNG PHÁP THAM LAM Chuyên ngành: Khoa học máy tính Mã số: 60 48 01 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH NGƯỜI HƯỚNG DẪN KHOA HỌC PGS. TSKH. NGUYỄN XUÂN HUY Thái Nguyên – 2012 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn MỤC LỤC Trang Trang phụ bìa ………………………………………………………………………... Lời cảm ơn…………………………………………………………………………...i Lời cam đoan ………………………………………………………………………ii Mục lục …………………………………………………………………………….iii MỞ ĐẦU ………………………………………………………………………….1 Chƣơng 1 TỔNG QUAN VỀ PHƢƠNG PHÁP THAM LAM 1.1. Phƣơng pháp tham lam……………………………………………………….4 1.1.1. Ý tưởng phương pháp tham lam………………………………………………4 1.1.2. Đặc trưng của phương pháp tham lam……………………………………….6 1.1.3. Thiết kế thuật toán dựa trên ý tưởng phương pháp tham lam….……………7 1.1.3.1. Các thành phần quyết định tham lam………………………………………7 1.1.3.2. Sơ đồ chung để giải các bài toán bằng giải thuật tham lam….….…………9 1.1.3.3. Lược đồ giải thuật tham lam ……………………………………………….9 1.1.3.4. Thiết kế một thuật toán dựa trên ý tưởng tham lam….….………………...11 1.1.3.5 Tiến trình thực hiện phương pháp tham lam…………………………...…..11 1.2. Ví dụ…………………………………………………………………………..14 1.2.1. Bài toán lựa chọn công việc.………………………………………………...14 1.2.2. Xác định bài toán……………………………………………………………14 1.2.3. Tính chất của lời giải ……………………………………………………….14 1.2.4. Các bước của thuật giải tham lam…………………………………………..15 Chƣơng 2 THIẾT KẾ THUẬT TOÁN DỰA TRÊN Ý TƢỞNG CỦA PHƢƠNG PHÁP THAM LAM 2.1. Bài toán ngƣời du lịch ……………………………………………………….18 2.1.1. Phát biểu bài toán …………………………………………………………..18 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 2.1.2. Phân tích thiết kế thuật toán ……………………………………………….18 2.1.3. Xác định độ phức tạp của thuật toán ………………………………………20 2.2. Bài toán cây bao trùm ngắn nhất …………………………………………..21 2.2.1. Phát biểu bài toán …………………………………………………………..21 2.2.2. Phân tích thiết kế thuật toán ………………………………………………..21 2.2.3. Xác định độ phức tạp của thuật toán ……………………………………….27 2.3. Thuật toán Dijkstra -Tìm đƣờng đi ngắn nhất trong đồ thị có trọng số…28 2.3.1. Phát biểu bài toán …………………………………………………………..28 2.3.2. Phân tích thiết kế thuật toán ………………………………………………..28 2.3.3. Xác định độ phức tạp của thuật toán ……………………………………….33 2.4. Bài toán cái ba lô …………………………………………………………….33 2.4.1. Phát biểu bài toán …………………………………………………………..33 2.4.2. Phân tích thiết kế thuật toán ………………………………………………..33 2.4.3. Xác định độ phức tạp của thuật toán ……………………………………….35 2.5. Bài toán băng nhạc ………………………………………..…………………35 2.5.1. Phát biểu bài toán …………………………………………………………..35 2.5.2. Phân tích thiết kế thuật toán ………………………………………………..36 2.5.3. Xác định độ phức tạp của thuật toán ……………………………………….38 2.6. Bài toán lập lịch ……………………………………………………………...38 2.6.1. Phát biểu bài toán ………………………………………………………….38 2.6.2. Phân tích thiết kế thuật toán ………………………………………………..38 2.6.3. Xác định độ phức tạp của thuật toán ……………………………………….42 2.7. Bài toán mã hóa Huffman …………………………………………………..43 2.7.1. Phát biểu bài toán …………………………………………………………..49 2.7.2. Phân tích thiết kế thuật toán ………………………………………………..49 2.8. Phƣơng pháp tham lam trong tƣơng quan với phƣơng pháp khác ……...50 - Phƣơng pháp quy hoạch động 2.8.1. Phương pháp quy hoạch động ……………………………………………...50 2.8.2. Phương pháp tham lam trong tương quan vớiv PP quy hoạch động ……...51 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Chƣơng 3 CÀI ĐẶT CHƢƠNG TRÌNH CHO MỘT SỐ BÀI TOÁN 3.1. Bài toán ngƣời du lịch ………………………………………………………53 3.2. Bài toán cây bao trùm ngắn nhất Kruskal…………………………………56 3.3. Thuật toán Dijkstra -Tìm đƣờng đi ngắn nhất trong đồ thị có trọng số……………………………………………………………………..……………62 3.4. Bài toán mã hóa huffman……………………………………………………65 KẾT LUẬN ……………………………………………………………………..69 TÀI LIỆU THAM KHẢO ……………………………………………………..70 PHỤ LỤC………………………………………………………………………….. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 1 MỞ ĐẦU 1. Đặt vấn đề Có nhiều phƣơng pháp đƣợc dùng để thiết kế thuật toán nhƣ: chia để trị, vét cạn, quy hoạch động... trong đó, mỗi phƣơng pháp chỉ áp dụng cho những lớp bài toán phù hợp. Phƣơng pháp tham lam cũng là một trong số các phƣơng pháp phổ biến thƣờng đƣợc vận dụng trong thiết kế thuật toán. Phƣơng pháp tham lam gợi ý chúng ta tìm một trật tự hợp lí để duyệt dữ liệu nhằm đạt đƣợc mục tiêu một cách chắc chắn và nhanh chóng. Thông thƣờng dữ liệu đƣợc duyệt theo một trong hai trật tự tăng hay giảm theo một tiêu chí nào đấy. Phƣơng pháp tham lam xây dựng các thuật toán để giải các bài toán tối ƣu dựa trên tƣ tƣởng tối ƣu cục bộ theo một chiến lƣợc tƣ duy kiểu con ngƣời, nhằm nhanh chóng đạt đến một lời giải "tốt". Nếu có thể chứng minh rằng một thuật toán dựa trên phƣơng pháp tham lam cho ra kết quả tối ƣu toàn cục của một lớp bài toán nào đó, thì khi ấy thuật toán ấy thƣờng sẽ đƣợc lựa chọn, 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. Một số thuật toán dựa trên tƣ tƣởng phƣơng pháp tham lam đã thực sự tìm ra đƣợc phƣơng án tối ƣu nhƣ: thuật toán Kruscal tìm cây khung cực tiểu, thuật toán Prim dành cho bài toán cây bao trùm nhỏ nhất, thuật toán Dijkstra dành cho bài toán đƣờng đi ngắn nhất và thuật toán tìm cây Huffman tối ƣu. Là một giáo viên giảng dạy bộ môn Tin học ở trƣờng PT, tôi nhận thấy việc ứng dụng phƣơng pháp tham lam trong thiết kế thuật toán là một mảng kiến thức rất cần thiết đối với học sinh, đặc biệt là học sinh nhóm chuyên Tin và đội tuyển. Vì vậy, tôi mong muốn tìm hiểu về phƣơng pháp tham lam và ứng dụng phƣơng pháp tham lam trong thiết kế thuật toán cho một nhóm các bài toán, nhằm tạo ra một nguồn tƣ liệu quan trọng cho các giáo viên, học sinh và những ngƣời quan tâm đến phƣơng pháp này. Từ những lí do trên, tôi quyết định lựa chọn đề tài luận văn tốt nghiệp là “Thiết kế thuật toán dựa trên ý tƣởng của phƣơng pháp tham lam ”. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 2 2. Đối tƣợng và phạm vi nghiên cứu - Phƣơng pháp tham lam trong thiết kế thuật toán. - Một số bài toán đặc trƣng, cơ bản. 3. Hƣớng nghiên cứu của đề tài - Tổng quan về phƣơng pháp tham lam. - Thiết kế thuật toán cho một số bài toán dựa trên ý tƣởng tham lam từ đó tìm ra: + Các kĩ thuật sử dụng trong phƣơng pháp tham lam + Đối sánh phƣơng pháp tham lam với Phƣơng pháp khác + Hạn chế của phƣơng pháp tham lam. - Cài đặt chƣơng trình cho một số bài toán kinh điển. 4. Những nội dung nghiên cứu chính Chƣơng 1. TỔNG QUAN VỀ PHƢƠNG PHÁP THAM LAM (Trong chương này, học viên sẽ tìm hiểu và trình bày phương pháp tham lam: Ý tưởng, phát biểu phương pháp, nêu ví dụ và phân tích làm rõ về phương pháp này). Chƣơng 2. THIẾT KẾ THUẬT TOÁN DỰA TRÊN Ý TƢỞNG CỦA PHƢƠNG PHÁP THAM LAM (Dựa vào cơ sở lí thuyết trình bày ở chương I, trong chương này, học viên sẽ phân tích thiết kế thuật toán bằng phương pháp tham lam cho 7 bài toán cụ thể (mục 2.1 đến 2.7); Thông qua các bài tập học viên sẽ rút ra kỹ thuật sử dụng phương pháp tham lam; Đối sánh phương pháp tham lam với phương pháp khác ; Chỉ ra hạn chế của phương pháp tham lam). Các bài toán cụ thể: - Bài toán ngƣời du lịch - Bài toán tìm cây khung cực tiểu - Bài toán cây bao trùm ngắn nhất - Bài toán cái ba lô - Bài toán băng nhạc - Bài toán xếp lịch - Bài toán mã hóa Huffman Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 3 Chƣơng 3. CÀI ĐẶT CHƢƠNG TRÌNH CHO MỘT SỐ BÀI TOÁN (Trong chương này, dựa vào chương II, học viên sẽ xây dựng chương trình và cài đặt chương trình cho một số bài toán bằng ngôn ngữ C++, Free Pascal). 5. Phƣơng pháp nghiên cứu: phân tích, liệt kê, so sánh, đối chiếu, trực quan, thực nghiệm,… 6. Ý nghĩa khoa học của đề tài - Đƣa ra nội dung phƣơng pháp tham lam - Ứng dụng phƣơng pháp tham lam trong thiết kế thuật toán cho một nhóm các bài toán, nhằm tạo ra một nguồn tƣ liệu quan trọng cho các giáo viên, học sinh và những ngƣời quan tâm đến phƣơng pháp này. 7. Kết cấu của đề tài Ngoài phần mở đầu, kết luận, tài liệu tham khảo đề tài gồm 3 chƣơng: Chƣơng 1. TỔNG QUAN VỀ PHƢƠNG PHÁP THAM LAM Chƣơng 2. THIẾT KẾ THUẬT TOÁN DỰA TRÊN Ý TƢỞNG CỦA PHƢƠNG PHÁP THAM LAM Chƣơng 3. CÀI ĐẶT CHƢƠNG TRÌNH CHO MỘT SỐ BÀI TOÁN Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 4 Chƣơng 1 TỔNG QUAN VỀ PHƢƠNG PHÁP THAM LAM Các bài toán trên thực thế có muôn hình muôn vẻ, không thể đƣa ra một cách thức chung để tìm giải thuật cho mọi bài toán. Các phƣơng pháp vét cạn (exhaustivesearch), chia để trị (divide and conquer), quy hoạch động (dynamic programming) và tham lam (greedy) là những “chiến lƣợc” kinh điển để tìm giải thuật cho các bài toán. Tham lam (greedy) là một phƣơng pháp giải các bài toán tối ƣu. Các thuật toán tham lam dựa vào sự đánh giá tối ƣu cục bộ địa phƣơng để đƣa ra quyết định tức thì tại mỗi bƣớc lựa chọn, với hy vọng cuối cùng sẽ tìm ra đƣợc phƣơng án tối ƣu tổng thể. Chƣơng I trình bày về phƣơng pháp tham lam: Ý tưởng phương pháp tham lam, nêu ví dụ và phân tích làm rõ về phương pháp này. 1.1. Phƣơng pháp tham lam 1.1.1. Ý tưởng phương pháp tham lam Các bài toán tối ƣu thƣờng là có một số rất lớn nghiệm, việc tìm ra nghiệm tối ƣu (nghiệm có giá thấp nhất) đòi hỏi rất nhiều thời gian. Một cách tiếp cận để giải quyết các bài toán tối ƣu là chiến lƣợc tham lam. Trong hầu hết các bài toán tối ƣu, để nhận đƣợc nghiệm tối ƣu chúng ta có thể đƣa về sự thực hiện một dãy quyết định. Ý tƣởng của chiến lƣợc tham lam là, tại mỗi bƣớc ta sẽ lựa chọn quyết định để thực hiện quyết định đƣợc xem là tốt nhất trong ngữ cảnh nào đó đƣợc xác định bởi bài toán. Tức là, quyết định đƣợc lựa chọn ở mỗi bƣớc là quyết định tối ƣu địa phƣơng. Tùy theo từng bài toán mà ta đƣa ra tiêu chuẩn lựa chọn quyết định cho thích hợp. Các thuật toán tham lam nói chung là đơn giản và hiệu quả (vì các tính toán để tìm ra quyết định tối ƣu địa phƣơng thƣờng là đơn giản). Tuy nhiên, các thuật toán tham lam có thể không tìm đƣợc nghiệm tối ƣu, nói chung nó chỉ cho ra Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 5 nghiệm gần tối ƣu, nghiệm tƣơng đối tốt. Nhƣng cũng có nhiều thuật toán đƣợc thiết kế theo kỹ thuật tham lam cho ta nghiệm tối ƣu, chẳng hạn thuật toán Dijkstra tìm đƣờng đi ngắn nhất từ một đỉnh tới các đỉnh còn lại trong đồ thị định hƣớng, các thuật toán Prim và Kruskal tìm cây bao chùm ngắn nhất trong đồ thị vô hƣớng. Ví dụ - Bài toán trả tiền của máy rút tiền tự động ATM: Trong máy ATM, có sẵn các loại tiền có mệnh giá 100.000 đồng, 50.000 đồng, 20.000 đồng và 10.000 đồng. Giả sử mỗi loại tiền đều có số lƣợng không hạn chế. Khi có một khách hàng cần rút một số tiền n đồng (tính chẵn đến 10.000 đồng, tức là n chia hết cho 10.000). Hãy tìm một phƣơng án trả tiền sao cho trả đủ n đồng và số tờ giấy bạc phải trả là ít nhất. Ý tưởng phương pháp tham lam để giải quyết bài toán trả tiền của máy rút tiền tự động ATM: Gọi X = (X1, X2, X3, X4) là một phƣơng án trả tiền. X1 là số tờ giấy bạc 100.000 đồng, X2 là số tờ giấy bạc 50.000 đồng, X3 là số tờ giấy bạc 20.000 đồng, X4 là số tờ giấy bạc 10.000 đồng. Theo yêu cầu ta phải có X1 + X2 + X3 + X4 nhỏ nhất X1*100.000+X2*50.000+X3*20.000+X4*10.000 = n. Để có số lƣợng tờ tiền nhỏ nhất thì các tờ giấy bạc mệnh giá lớn phải đƣợc chọn nhiều nhất. Trƣớc hết ta chọn tối đa các tờ giấy bạc 100.000 đồng, nghĩa là X1 là số nguyên lớn nhất sao cho X1 * 100.000  n. Tức là X1 = n DIV 100.000. Xác định số tiền cần rút còn lại là hiệu n – X1 * 100000 Chuyển sang chọn loại giấy bạc 50.000 đồng, và cứ tiếp tục nhƣ thế cho các loại mệnh giá khác. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 6 Giả sử n = 1290000, phƣơng án trả tiền nhƣ sau: X1 = 1290000 DIV 100000 = 12 Số tiền còn lại là 1290000 – 12 * 100000 = 90000 X2 = 90000 DIV 50000 = 1 Số tiền còn lại là 90000 – 1 * 50000 = 40000 X3 = 40000 DIV 20000 = 2 Số tiền còn lại là 40000 – 2 * 20000 = 0 X4 = 0 DIV 10000 = 0 Ta có X = (X1, X2, X3, X4) = (12, 1, 2, 0) Đây là một phƣơng án tối ƣu. Tuy nhiên giả sử trong máy ATM có các loại tiền mệnh giá 50.000đ, 80.000 đồng, 10.000đ thì khi đó để rút 100.000đ theo ý tƣởng tham lam sẽ có phƣơng án rút một tờ mệnh giá 80.000đ và hai tờ mệnh giá 10.000đ. Đây chƣa phải là phƣơng án tối ƣu vì phƣơng án tối ƣu nhất là rút hai tờ mệnh giá 50.000đ. Song, cách lựa chọn theo ý tƣởng tham lam cũng là một phƣơng án tốt, có thể chấp nhận đƣợc trong thực tế. 1.1.2. Đặc trưng của phương pháp tham lam Phƣơng pháp tham lam gợi ý chúng ta tìm một trật tự hợp lí để duyệt dữ liệu nhằm đạt đƣợc mục tiêu một cách chắc chắn và nhanh chóng. Thông thƣờng, dữ liệu đƣợc duyệt theo một trong hai trật tự là tăng hoặc giảm dần theo một chỉ tiêu nào đó. Một số bài toán đòi hỏi những dạng thức cải biên của hai dạng nói trên. Thuật toán tham lam có trƣờng hợp luôn tìm ra đúng phƣơng án tối ƣu, có trƣờng hợp không. Nhƣng trong trƣờng hợp thuật toán tham lam không tìm ra đúng phƣơng án tối ƣu, chúng ta thƣờng thu đƣợc một phƣơng án khả dĩ chấp nhận đƣợc. Với một bài toán có nhiều thuật toán để giải quyết, thông thƣờng thuật toán tham lam có tốc độ tốt hơn hẳn so với các thuật toán tối ƣu tổng thể. Đặc trƣng của thuật toán tham lam thƣờng thể hiện bởi: trong mỗi bƣớc, việc xử lí sẽ tuân theo một sự lựa chọn trƣớc, không kể đến tình trạng không tốt có thể xảy ra khi thực hiện lựa chọn lúc đầu. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 7 1.1.3. Thiết kế thuật toán dựa trên ý tưởng phương pháp tham lam Khác với các kỹ thuật thiết kế thuật toán nhƣ chia để trị, liệt kê, quy hoạch động mà chúng ta đã biết, rất khó để đƣa ra một quy trình chung để tiếp cận bài toán, tìm thuật toán cũng nhƣ cài đặt thuật toán tham lam. Giải thuật tham lam (Greedy algorithm) là một thuật toán giải quyết một bài toán theo kiểu metaheuristic để tìm kiếm lựa chọn tối ƣu địa phƣơng ở mỗi bƣớc đi với hi vọng tìm đƣợc tối ƣu toàn cục. Chẳng hạn áp dụng giải thuật tham lam với bài toán hành trình của ngƣời bán hàng ta có giải thuật sau: “Ở mỗi bước hãy tìm đến thành phố gần thành phố hiện tại nhất”. Nói chung, giải thuật tham lam thƣờng có 5 thành phần: 1. Một tập các ứng viên để từ đó tạo ra lời giải 2. Một hàm lựa chọn để theo đó chọn ứng viên tốt nhất để bổ sung vào lời giải. 3. Một hàm khả thi 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. 4. Một hàm mục tiêu ấn định giá trị của lời giải hoặc một lời giải chƣa hoàn chỉnh. 5. 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. 1.1.3.1. Các thành phần quyết định tham lam Tính chất lựa chọn tham lam Thành phần then chốt trƣớc tiên là tính lựa chọn tham lam: một giải pháp tối ƣu toàn cục có thể đạt đƣợc bằng cách lựa chọn tối ƣu cục bộ (tham lam). Nói một cách khác, khi có nhiều sự lựa chọn thì ta lựa chọn phƣơng án nào tốt nhất ở hiện tại trong bài toán hiện tại, mà không cần quan tâm đến kết quả các bài toán con của nó. Thuộc tính lựa chọn tham lam thƣờng đạt đƣợc hiệu lực trong việc thực hiện lựa chọn của ta trong bài toán con. Ví dụ, trong bài toán chọn hoạt động, giả sử rằng ta có các hoạt động đƣợc sắp xếp sẵn theo thứ tự tăng dần của thời điểm kết thúc, ta cần kiểm tra mỗi một hoạt động. Nó thƣờng là trƣờng hợp mà đƣợc xử lý trƣớc khi đƣa vào hay sử dụng một cấu trúc dữ liệu thích hợp (thƣờng một hàng đợi ƣu thế), Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 8 ta có thể thực hiện các lựa chọn tham lam nhanh chóng, vì vậy đƣa ra một thuật toán hiệu quả. Chúng ta có thể lựa chọn giải pháp nào đƣợc cho là tốt nhất ở thời điểm hiện tại và sau đó giải bài toán con nảy sinh từ việc lựa chọn vừa rồi. Lựa chọn của thuật toán tham lam có thể phụ thuộc vào các lựa chọn trƣớc đó. Nhƣng nó không thể phụ thuộc vào một lựa chọn nào trong tƣơng lai hay phụ thuộc vào lời giải của các bài toán con. Thuật toán tiến triển theo kiểu thực hiện các lựa chọn theo một vòng lặp, cùng lúc đó thu nhỏ bài toán đã cho về một bài toán con nhỏ hơn. Giải thuật tham lam quyết định sớm và thay đổi đƣờng đi của thuật toán theo quyết định đó, và không bao giờ xét lại các quyết định cũ. Đối với một số bài toán, đây có thể là một thuật toán không chính xác. Cấu trúc con tối ưu Một bài toán có cấu trúc con tối ƣu nếu giải pháp tối ƣu cho bài toán này chứa trong nó các giải pháp tối ƣu cho các bài toán con. Thuộc tính này là điểm để quyết định ta có thể giải quyết bài toán bằng phƣơng pháp quy hoạch động cũng nhƣ tham lam đƣợc hay không. Nhƣ một ví dụ của cấu trúc con tối ƣu, quay về cách ta chứng minh rằng nếu một giải pháp tối ƣu đối với bài toán con Sij có chứa một hoạt động ak, sau đó nó cũng phải chứa các giải pháp tối ƣu đối với các bài toán Sik và Skj. Cấu trúc con tối ƣu này đƣợc đƣa ra, ta nói rằng nếu biết hoạt động nào sử dụng nhƣ ak, ta có thể xây dựng một giải pháp tối ƣu đối với Sij bằng việc lựa chọn cùng với tất cả hoạt động của các giải pháp tối ƣu đối với các bài toán con Sik và Skj. Dựa trên sự quan sát này của cấu trúc con tối ƣu, ta có thể đƣa ra công thức đệ quy mà nó định rõ giá trị của một giải pháp tối ƣu. Ta thƣờng sử dụng thêm cấu trúc con tối ƣu gần nhƣ trực tiếp, khi áp dụng nó đối với các giải thuật tham lam. Ta không cần thiết cho rằng đi đến một bài toán con bằng cách thực hiện lựa chọn tham lam trong bài toán tối ƣu. Ta cần làm là cho rằng một giải pháp tối ƣu đối với bài toán con, kết hợp với lựa chọn tham lam vừa đƣợc thực hiện, mang lại một giải pháp tối ƣu đối với bài toán ban đầu. Sự phối hợp hoàn toàn sử dụng phƣơng pháp quy nạp đối với các bài toán con để chứng minh Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 9 rằng việc sử dụng lựa chọn tham lam tại mỗi bƣớc tạo ra một giải pháp tối ƣu Một bài toán đƣợc gọi là có cấu trúc tối ƣu nếu một lời giải tối ƣu của bài toán con chứa lời giải tối ƣu của bài toán lớn hơn. 1.1.3.2. Sơ đồ chung để giải các bài toán bằng giải thuật tham lam Dạng các bài toán giải bằng phương pháp tham lam Giả sử phải chọn một tập con R của các phần tử của một tập S =(s1,s2,…,sn) sao cho tập R thỏa mãn một điều kiện ràng buộc W(R) nào đó, và một hàm mục tiêu Z(R) đạt giá trị tối ƣu. Ví dụ bài toán tối ƣu tổ hợp: Cho hàm f(X) xác định trên một tập hữu hạn các phần tử D. Hàm f(X) đƣợc gọi là hàm mục tiêu. Mỗi phần tử X  D có dạng X = (x1, x2, .. ,xn) đƣợc gọi là một phƣơng án. Cần tìm một phƣơng án X* D sao cho f(X*) đạt min(max). Phƣơng án X* nhƣ thế đƣợc gọi là phƣơng án tối ƣu. Sơ đồ chung để giải các bài toán bằng giải thuật tham lam Bƣớc 1: Chọn một phần tử s có lợi nhất cho lời giải trong bƣớc đó sao cho phần tử này cùng với lời giải tối ƣu của bài toán con với tập con S – {s} với ràng buộc W(R-{s}) là lời giải tối ƣu cho bài toán. Bƣớc 2: Tiếp tục tìm phần tử tiếp theo có lợi nhất với tập con S=S-{s} với ràng buộc W(R-{s}) và hàm mục tiêu Z = Z (R-{s}). Cho đến khi không tìm đƣợc phần tử nhƣ vậy hoặc tập S = . 1.1.3.3. Lƣợc đồ giải thuật tham lam Tư tưởng của phương pháp tham lam Ta xây dựng tập S dần từng bƣớc, bắt đầu từ tập rỗng. 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 S. Việc lựa chọn một phần tử nhƣ thế ở mỗi bƣớc đƣợc hƣớng dẫn bởi hàm chọn. Phần tử đƣợc chọn sẽ đƣợc loại khỏi tập A. Nếu khi thêm phần tử đƣợc chọn vào tập S mà S vẫn còn thỏa mãn các điều kiện của bài toán thì ta mở rộng S bằng cách thêm vào phần tử đƣợc chọn. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 10 Mô hình: Chọn S từ tập A; Tính chất tham lam của thuật toán đƣợc định hƣớng bởi hàm Chọn - Khởi động S =  - Trong khi A ≠ : + Chọn phần tử tốt nhất của A gán vào x: x= Chọn(A) + Cập nhật các đối tƣợng để chọn A: A = A –{x} + Nếu S  {x} thỏa mãn yêu cầu bài toán thì: Cập nhật lời giải S = S  {x} Lược đồ tổng quát như sau: Greedy(A, S) // A là một tập các ứng cử viên, S là tập quyết định – Procedure nghiệm Begin S  ∅; While A <> ∅ do Begin x  select(A); AA-{x}; if S  {x} đƣợc thừa nhận then SS {x}; end; end; Trong lƣợc đồ tổng quát trên, Select là hàm chọn, nó cho phép ta chọn từ tập A một phần tử đƣợc xem là tốt nhất, nhiều hứa hẹn nhất là thành viên của tập nghiệm. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 11 1.1.3.4. Thiết kế một thuật toán dựa trên ý tƣởng tham lam Khi tiếp cận bài toán và tìm thuật toán tham lam thì cần khảo sát kĩ bài toán để tìm ra các tính chất đặc biệt mà ở đó ta có thể đƣa ra quyết định tức thời tại từng bƣớc dựa vào sự đánh giá tối ƣu cục bộ địa phƣơng. Ý tƣởng của phƣơng pháp tham lam trong thiết kế thuật toán đƣợc tiến hành là: Xác định trật tự xử lí để có lợi nhất, sắp xếp dữ liệu theo trật tự đó, xử lí dữ liệu theo trật tự đã nêu. 1.1.3.5 Tiến trình thực hiện phƣơng pháp tham lam Thuật toán tham lam có đƣợc một giải pháp tối ƣu cho một bài toán bằng cách thực hiện một chuỗi các lựa chọn. Đối với mỗi quyết định chỉ ra trong thuật toán, sự lựa chọn này dƣờng nhƣ tốt nhất tại thời điểm đƣợc chọn. Chiến lƣợc phỏng đoán này không luôn tạo ra giải pháp tối ƣu, nhƣng thỉnh thoảng nó giải quyết đƣợc. Quy trình thực hiện để phát triển thuật toán tham lam đi qua từng bƣớc nhƣ sau: 1. Xác định cấu trúc con tối ƣu 2. Xây dựng giải pháp đệ quy 3. Chứng minh: tại mỗi bƣớc đệ qui, lựa chọn tham lam là một trong những lựa chọn cho kết quả tối ƣu 4. Chỉ ra: sau mỗi lựa chọn tham lam, một trong những bài toán con sẽ rỗng 5. Xây dựng giải pháp đệ quy cho chiến lƣợc tham lam 6. Khử đệ quy Qua các bƣớc này, ta đã thấy chi tiết cơ bản nguồn gốc quy hoạch động của thuật toán tham lam. Trong thực tế, ta thƣờng tổ chức hiệu quả các bƣớc trên khi thiết kế giải thuật tham lam. Ta phát triển cấu trúc con với một cái nhìn hƣớng đến thực hiện lựa chọn tham lam mà để lại một bài toán con đƣợc giải quyết một cách tối ƣu. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 12 Ví dụ - bài toán chọn hoạt động: Bài toán sắp xếp lịch cho nhiều hoạt động với ý nghĩa để có thể sử dụng chung một tài nguyên (mỗi thời điểm chỉ có một hoạt động sử dụng tài nguyên chung), với mục tiêu là sắp xếp sao càng có nhiều hoạt động tƣơng thích sử dụng tài nguyên càng tốt. Giả sử ta có một tập hợp S = {a1, a2, .., an } là tập các hoạt động muốn sử dụng tài nguyên, ví dụ một hội trƣờng, chỉ mỗi một hoạt động tại mỗi thời điểm. Mỗi hoạt động ai sẽ có thời điểm bắt đầu là si và thời điểm kết thúc là fi, với điều kiện 0 ≤ si < fi < ∞. Nếu hoạt động ai đƣợc chọn, thì nó sẽ độc chiếm tài nguyên trong khoảng thời gian [si, fi). Hoạt động ai và aj đƣợc gọi là tƣơng thích lẫn nhau nếu nhƣ khoảng thời gian [si, fi) và [aj, fj) là không giao nhau (Ví dụ ai và aj là tƣơng thích nếu si ≥ fj hoặc sj ≥ fi ). Trong bài toán chọn hoạt động ta phải chọn tập con lớn nhất của các hoạt động tƣơng thích lẫn nhau. Chẳng hạn, xem tập S của các hoạt động sau, mà ta có thể sắp xếp tăng dần theo thời điểm kết thúc. i 1 2 3 4 5 6 7 8 9 10 11 Si 1 3 0 5 3 5 6 8 8 2 12 Fi 4 5 6 7 8 9 10 11 12 13 14 Ta sẽ thấy một cách ngắn gọn là tại sao nó thuận lợi để xem xét các hoạt động trong trình tự sắp xếp. Chẳng hạn nhƣ, một tập con {a3, a9, a11 } bao gồm những hoạt động tƣơng thích lẫn nhau. Nó không phải là tập con lớn nhất, vì một tập con {a1, a4, a8, a11} là lớn hơn. Thật ra {a1, a4, a8, a11} là tập con lớn nhất của các hoạt động tƣơng thích lẫn nhau; một tập con lớn nhất khác là {a2, a4, a9, a11}. Ta sẽ giải quyết bài toán này trong một vài bƣớc. Bắt đầu bởi việc đƣa ra công thức của giải pháp quy hoạch động đối với bài toán này trong đó ta tổng hợp Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 13 các giải pháp tối ƣu đối với hai bài toán con để thiết lập giải pháp tối ƣu của bài toán gốc. Ta có các lựa chọn khi quyết định các bài toán để sử dụng trong một giải pháp tối ƣu. Sau đó, ta sẽ nhận thấy rằng ta chỉ cần một lựa chọn duy nhất - lựa chọn tham lam - và sau khi ta lựa chọn chỉ còn một bài toán con, một bài toán con còn lại sẽ rỗng. Dựa trên những nhận xét này, ta sẽ xây dựng một giải thuật tham lam đệ quy để giải quyết bài toán lập lịch hoạt động. Ta sẽ hoàn thành quá trình xây dựng giải thuật tham lam bởi việc biến đổi giải thuật đệ quy sang giải thuật lặp. Mặc dù những bƣớc ta thực hiện trong phần này thể hiện mối liên quan nhiều hơn là tiêu biểu cho sự phát triển của phƣơng pháp tham lam, chúng minh hoạ cho mối quan hệ của phƣơng pháp tham lam và quy hoạch động. Ta trƣớc tiên định nghĩa bài toán con Sij, mà cả hai i và j khác nhau. Ta đã thấy rằng nếu ta luôn thực hiện lựa chọn tham lam, ta có thể giới hạn các bài toán con đƣợc thành lập bởi Si,n+1 Nhƣ một sự lựa chọn, ta có thể tạo nên cấu trúc con tối ƣu với một lựa chọn tham lam có nghĩa. Điều đó là, ta có thể bỏ qua chỉ số dƣới thứ hai và định nghĩa các bài toán con của công thức Si = {ak S : fi ≤ Sk}. Sau đó, ta có thể chứng minh rằng một lựa chọn tham lam (hoạt động đầu tiên am để kết thúc Si ), kết hợp với một giải pháp tối ƣu để đi đến tập còn lại Sm của các hoạt động tƣơng thích, mang lại một giải pháp tối ƣu đối với Si. Tổng quát hơn, ta thiết kế thuật toán tham lam theo chuỗi các bƣớc: 1. Tìm lựa chọn sao cho bƣớc tiếp theo chỉ việc giải quyết một bài toán con 2. Chứng minh rằng với sự lựa chọn tham lam tại mỗi bƣớc ta luôn tìm đƣợc một giải pháp tối ƣu của bài toán ban đầu. 3. Chỉ ra rằng, với sự lựa chọn tham lam tại mỗi bƣớc, giải pháp tối ƣu của bài toán con còn lại kết hợp với sự lựa chọn tham lam này sẽ đi đến một giải pháp tối ƣu cho bài toán ban đầu. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 14 Có thể nói một cách nhƣ thế nào nếu một giải thuật tham lam sẽ giải quyết đƣợc một bài toán tối ƣu riêng biệt? Không có cách tổng quát, nhƣng chiến lƣợc lựa chọn tham lam và cấu trúc con tối ƣu là hai thành phần then chốt. Nếu ta có thể chứng minh rằng bài toán có các thuộc tính này, sau đó ta thuận lợi trong cách xây dựng một thuật toán tham lam cho nó. 1.2. Ví dụ 1.2.1. Bài toán lựa chọn công việc Giả sử rằng ta có một tập S = { 1,2,..., n} của n công việc sử dụng cùng một tài nguyên, ví dụ nhƣ một phòng họp, tại một thời điểm chỉ có một công việc đƣợc tiến hành. Các công việc i đƣợc bắt đầu tại thời điểm si và kết thúc tại thời điểm f i với s ≤ f . Nếu đƣợc chọn, công việc i sẽ chiếm khoảng thời gian là [s , f ) i i i i Hãy lựa chọn các công việc không mâu thuẫn nhau (nghĩa là hoạt động i và j là tƣơng thích nếu khoảng thời gian [s , f ] và [s , f ] không phủ lấp lên nhau(tức là i i i j j và j là tƣơng thích nếu s >= f hay s >= f ) sao cho số các công việc đƣợc chọn là i j j i nhiều nhất. 1.2.2. Xác định bài toán INPUT: Thời gian khởi đầu s[1..n]; Thời gian kết thúc f[1..n] OUTPUT: Lựa chọn các công việc không mâu thuẫn nhau sao cho số công việc đƣợc chọn là nhiều nhất. 1.2.3. Tính chất của lời giải Giả sử dãy công việc đƣợc sắp xếp tăng dần theo thời điểm kết thúc : f  f  ...  f 1 2 n 1. Luôn tồn tại một lời giải tối ƣu chứa công việc thứ nhất 2. Nếu A  S là lời giải tối của bài toán có chứa việc 1 thì A – {1} là lời giải tối ƣu của bài toán với tập S’ gồm các công việc bắt đầu từ thời điểm f 1 trở đi. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 15 1.2.4. Các bước của thuật giải tham lam 1. Xác định cấu trúc tối ƣu của bài toán Tìm cấu trúc tối ƣu để xây dựng một lời giải tối ƣu cho bài toán từ những lời giải tối ƣu của các bài toán con. Gọi Sij là tập con của các hoạt động trong S có thể bắt đầu sau khi hoạt động a kết thúc và trƣớc khi hoạt động a bắt đầu i j Sij chứa các hoạt động tƣơng thích với ai và aj và cũng tƣơng thích với tất cả các hoạt động kết thúc không muộn hơn và bắt đầu không sớm hơn bắt đầu của aj. Giả sử các hoạt động đƣợc sắp xếp theo thứ tự tăng thời gian kết thúc của các hoạt động Để tìm cấu trúc con cho bài toán xếp lịch, khảo sát các bài toán con Sij khác rỗng và giả thuyết lời giải Sij chứa một số hoạt động ak sao cho: f - Xem thêm -