Tài liệu Một số thuật toán giải bài toán phủ tập hợp và ứng dụng

ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG HOÀNG XUÂN THÁI MỘT SỐ THUẬT TOÁN GIẢI BÀI TOÁN PHỦ TẬP HỢP VÀ ỨNG DỤNG LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Thái Nguyên - Năm 2014 Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 1 ĐẠI HOẠC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG HOÀNG XUÂN THÁI MỘT SỐ THUẬT TOÁN GIẢI BÀI TOÁN PHỦ TẬP HỢP VÀ ỨNG DỤNG 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 GS. TS. ĐẶNG QUANG Á Thái Nguyên - Năm 2014 Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 2 MỤC LỤC Trang LỜI CẢM ƠN ............................................................................................................ 4 LỜI CAM ĐOAN ...................................................................................................... 5 DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT ................................................ 6 DANH MỤC BẢNG .................................................................................................. 7 DANH MỤC HÌNH ................................................................................................... 8 MỞ ĐẦU .................................................................................................................... 9 Chƣơng 1. TỔNG QUAN ........................................................................................ 11 1.1. KIẾN THỨC CƠ SỞ VỀ LÝ THUYẾT BÀI TOÁN NP-HARD ..............11 1.1.1. Định nghĩa về lớp bài toán P và NP ......................................................11 1.1.2. Các ví dụ về bài toán NP .......................................................................14 1.2. LÝ THUYẾT QUY HOẠCH TOÁN HỌC ................................................15 1.2.1. Khái niệm chung....................................................................................16 1.2.2. Quy hoạch tuyến tính ............................................................................19 1.2.3. Quy hoạch rời rạc ..................................................................................22 1.3. TỔNG KẾT CHƢƠNG ...............................................................................25 Chƣơng 2. BÀI TOÁN PHỦ TẬP HỢP ................................................................. 26 2.1. GIỚI THIỆU BÀI TOÁN PHỦ TẬP HỢP ....................................................26 2.1.1. Một số ví dụ về bài toán phủ tập hợp ....................................................26 2.1.2. Bài toán phủ tập hợp..............................................................................28 2.2. MỘT SỐ KẾT QUẢ LÝ THUYẾT VỀ BÀI TOÁN PHỦ TẬP HỢP ..........29 2.2.1. Hƣớng tiếp cận giải bài toán SCP ...........................................................29 Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 3 2.2.2. Một số phƣơng pháp tìm giải pháp gần tối ƣu cho bài toán SCP ...........31 2.3. THUẬT TOÁN HEURISTIC GIẢI BÀI TOÁN PHỦ TẬP HỢP ................35 2.3.1. Thuật toán Heuristic ..............................................................................35 2.3.2. Ứng dụng thuật toán Heuristics giải bài toán SCP ................................36 2.3.3. Tính hiệu quả của thuật toán Heuristic ..................................................45 2.4. THUẬT TOÁN CHÍNH XÁC .......................................................................50 2.4.1. Ví dụ về thuật toán nhánh cận .....................................................................50 2.4.2. Thuật toán chính xác giải bài toán SCP ......................................................54 2.5. TỔNG KẾT CHƢƠNG .................................................................................57 Chƣơng 3. CÀI ĐẶT CHƢƠNG TRÌNH VÀ ỨNG DỤNG .................................. 58 3.1. BÀI TOÁN PHÂN LỊCH TRỰC BÁC SĨ .....................................................58 3.1.1. Phát biểu bài toán ........................................................................................58 3.1.2. Cài đặt thuật toán tham lam ........................................................................59 3.1.3. Cài đặt thuật toán Nhánh cận ......................................................................60 3.2. XÂY DỰNG CHƢƠNG TRÌNH PHÂN LỊCH TRỰC BÁC SĨ ...................64 3.2.1. Công cụ lựa chọn ...................................................................................64 3.2.2. Modul chƣơng trình ...............................................................................64 3.2.3. Giao diện chƣơng trình ..........................................................................66 3.3. THỬ NGHIỆM VÀ ĐÁNH GIÁ ...................................................................70 3.4. TỔNG KẾT CHƢƠNG .................................................................................70 KẾT LUẬN VÀ KIẾN NGHỊ ................................................................................. 72 DANH MỤC TÀI LIỆU THAM KHẢO ................................................................. 74 Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 4 LỜI CẢM ƠN Em xin chân thành cảm ơn Ban Giám hiệu, Phòng Đào tạo Sau Đại học, Khoa Công nghệ Thông tin Trường Đại học công nghệ thông tin và truyền thông Thái Nguyên đã tận tình giúp đỡ, tạo mọi điều kiện thuận lợi cho em trong quá trình học tập, nghiên cứu và thực hiện luận văn. Đặc biệt, em xin gửi lời tri ân sâu sắc đến GS. TS Đặng Quang Á – người đã dành nhiều thời gian, công sức và tận tình hướng dẫn khoa học cho em trong suốt quá trình hình thành và hoàn chỉnh luận văn. Xin chân thành cảm ơn Quý Thầy, Cô đã giảng dạy, truyền đạt cho em những tri thức quý báu, thiết thực trong suốt khóa học. Cuối cùng xin bày tỏ lòng biết ơn đối với gia đình, người thân, bạn bè, đồng nghiệp đã giúp đỡ, động viên, đóng góp ý kiến quý báu cho em trong việc hoàn thành luận văn này. Thái Nguyên, ngày tháng năm 2014 Tác giả Hoàng Xuân Thái Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 5 LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi dưới sự hướng dẫn trực tiếp của GS.TS. Đặng Quang Á. Mọi trích dẫn sử dụng trong báo cáo này đều được ghi rõ nguồn tài liệu tham khảo theo đúng qui định. Mọi sao chép không hợp lệ, vi phạm quy chế đào tạo, hay gian trá, tôi xin chịu hoàn toàn trách nhiệm. Thái Nguyên, ngày tháng năm 2014 Tác giả Hoàng Xuân Thái Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 6 DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT Tiếng Anh Từ viết tắt Tên đầy đủ Diễn giải GA Genetic Algorithm Giải thuật di truyền LP Linear Programming Quy hoạch tuyến tính NP Nondeterministic Polynomial Time Thuật toán bất định trong thời gian đa thức SA Simulated Annealing Giải thuật luyện thép SCP Set Covering Problem Bài toán phủ tập hợp Tiếng Việt BTQHTT Bài toán quy hoạch tuyến tính BTQHPT Bài toán quy hoạch phi tuyến BTQHL Bài toán quy hoạch lồi BTQHTP Bài toán quy hoạch toàn phƣơng Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 7 DANH MỤC BẢNG Trang Bảng 3.1. Danh sách các bác sĩ và các dịch vụ mà bác sĩ đó có thể thực hiện trong trƣờng hợp tổng quát .................................................................................................58 Bảng 3.2. Thời gian trung bình (miligiây) ................................................................70 Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 8 DANH MỤC HÌNH Trang Hình 1.1 Mô hình phân lớp các bài toán P, NP, CO-NP, NP-Complete, NP-hard 15 Hình 1.2. Đồ thị hàm f(x) 17 Hình 2.1. Thuật toán Meta-RaPS tìm giải pháp cơ sở 38 Hình 2.2. Thủ tục cập nhật 38 Hình 2.3. Thủ tục tìm giải pháp láng giềng 39 Hình 2.4. Thuật toán Meta-RaPS giải bài toán SCP 40 Hình 2.5. Ví dụ bài toán SCP 42 Hình 2.6. Kết quả sau khi thực hiện thuật toán tham lam 43 Hình ví dụ thuật toán tham lam 44 Hình 2.7. Kết quả cây phân nhánh 52 Hình 2.8. Ma trận chi phí của bài toán ngƣời du lịch 54 Hình 2.9. Cây phân nhánh giải bài toán ngƣời du lịch 54 Hình 3.1. Giao diện chính của chƣơng trình 67 Hình 3.2. Giao diện nạp dữ liệu 68 Hình 3.3. Giao diện phân lịch bằng thuật toán tham lam 68 Hình 3.4. Giao diện phân lịch bằng thuật toán tham lam 69 Hình 3.5. Giao diện lƣu kết quả phân lịch 69 Hình 3.6. Đồ thị biểu diễn thời gian thực hiện trung bình 70 Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 9 MỞ ĐẦU 1. Lý do chọn đề tài Bài toán tối ƣu tổ hợp là dạng bài toán có độ phức tạp tính toán cao thuộc lớp NP khó. Đã có nhiều giải thuật đƣợc đƣa ra để giải quyết bài toán trên nhƣ họ giải thuật kiến (Ant Algorithm), giải thuật luyện thép SA (Simulated Annealing), giải thuật di truyền GA (Genetic Algorithm) và giải thuật Meta-Heuristic. Những giải thuật này đã giải quyết các bài toán với hiệu quả cao và cho kết quả lời giải gần tối ƣu. Với độ phức tạp tính toán cao của các bài toán tối ƣu tổ hợp cũng nhƣ đòi hỏi về mặt thời gian, việc giải các bài toán này với tính chất tuần tự của các giải thuật sẽ gặp phải những vấn đề về thời gian thực hiện chƣơng trình, tốc độ xử lý, khả năng lƣu trữ của bộ nhớ, xử lý dữ liệu với quy mô lớn, … Kích thƣớc bài toán tăng lên và không gian tìm kiếm càng lớn yêu cầu cần phải có các giải thuật để tăng tốc độ và hiệu quả của giải thuật. Bài toán phủ tập hợp (set covering problem) là một bài toán tối ƣu tổ hợp cơ bản. Dạng bài toán này có rất nhiều trong thực tế nhƣ: lập lịch biểu, lập kế hoạch sản xuất, định tuyến, phân bổ đầu tƣ, …Đã có nhiều nghiên cứu về phƣơng pháp hiệu quả để giải quyết bài toán này bao gồm các giải thuật heuristic, thuật toán sử dụng ý tƣởng tham lam (Greedy Method) và các thuật toán sử dụng các phƣơng pháp của quy hoạch nguyên. Vì vậy, việc tìm hiểu bài toán dạng phủ tập hợp, các thuật toán giải quyết bài toán để từ đó ứng dụng vào trong thực tế là một việc làm có ý nghĩa khoa học và thực tiễn. Đây chính là mục đích của luận văn này. 2. Đối tƣợng nghiên cứu Đối tƣợng nghiên cứu của luận văn này là bài toán phủ tập hợp và các vấn đề liên quan, các thuật toán để giải quyết pài toán phủ tập hợp. Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 10 3. Phạm vi nghiên cứu Luận văn tập trung nghiên cứu các kiến thức có liên quan, các cơ sở lý thuyết nhƣ: Lý thuyết các bài toán NP-hard, quy hoạch tuyến tính, quy hoạch nguyên, các phƣơng pháp giải chúng và áp dụng vào bài toán phủ tập hợp. 4. Nhiệm vụ nghiên cứu - Tìm hiểu và hệ thống các kiến thức cơ sở về lý thuyết các bài toán NP-hard - Tìm hiểu về quy hoạch toán học, bài toán phủ tập hợp và ứng dụng. - Tìm hiểu một vài thuật toán chính xác giải bài toán phủ tập hợp. - Cài đặt và thử nghiệm một vài thuật toán. 5. Những nội dung nghiên cứu chính Bố cục của luận văn gồm phần mở đầu trình bày lý do chọn đề tài, đối tƣợng và nhiệm vụ nghiên cứu của đề tài. Chƣơng một, tập trung trình bày những kiến thức tổng quan về lý thuyết NP-hard và quy hoạch toán học. Chƣơng hai, giới thiệu bài toán phủ tập hợp, một số kết quả lý thuyết về bài toán phủ tập hợp, trình bày thuật toán Heuristic và thuật toán chính xác giải bài toán phủ tập hợp. Chƣơng 3, ứng dụng những kiến thức về bài toán phủ tập hợp và những thuật toán đã trình bày, trong chƣơng này chúng tôi trình bày phần cài đặt chƣơng trình ứng dụng. Với những kết quả đạt đƣợc, phần cuối của luận văn nêu ra những phép đo tính hiệu quả của nghiên cứu, đánh giá thuật toán và nêu vài đề xuất nhằm tối ƣu thuật toán, đánh giá các kết quả đạt đƣợc, những hạn chế và đề xuất hƣớng nghiên cứu tiếp theo của đề tài. 6. Phƣơng pháp nghiên cứu - Phƣơng pháp đọc tài liệu - Phƣơng pháp quan sát - Phƣơng pháp phân tích – tổng hợp lý thuyết. - Phƣơng pháp thực nghiệm. Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 11 Chƣơng 1. TỔNG QUAN KIẾN THỨC CƠ SỞ VỀ LÝ THUYẾT BÀI TOÁN NP-HARD 1.1. 1.1.1. Định nghĩa về lớp bài toán P và NP 1.1.1.1. Khái niệm các loại thời gian tính Thời gian tính tốt nhất: là thời gian tính tối thiểu cần thiết để thực hiện thuật toán với mọi bộ dữ liệu đầu vào kích thƣớc n. Thời gian tính tồi nhất: là thời gian tính tối đa cần thiết để thực hiện thuật toán với mọi bộ dữ liệu đầu vào có kích thƣớc n. Thời gian tính trung bình: là thời gian tính cần thiết để thực hiện thuật toán trên một tập hữu hạn các bộ dữ liệu đầu vào có kích thƣớc n. Thời gian tính trung bình đƣợc tính theo công thức sau: Thời gian tính trung bình=(Tổng thời gian tính tất cả các bộ dữ liệu có thể)/ Số bộ dữ liệu. Định nghĩa 1.1 [1]. Bài toán quyết định là bài toán mà đầu ra chỉ có thể là „yes‟ hoặc „no‟ (đúng/sai, 0/1). Đối với một bài toán quyết định, có những bộ dữ liệu vào cho ra câu trả lời (đầu ra) là „yes‟, chúng ta gọi đây là bộ dữ liệu „yes‟, nhƣng cũng có những bộ dữ liệu vào cho ra câu trả lời là „no‟, chúng ta gọi những bộ dữ liệu này là bộ dữ liệu „no‟. 1.1.1.2. Bằng chứng ngắn gọn dễ kiểm tra Rất nhiều các bài toán quyết định có một đặc điểm chung, đó là để xác nhận câu trả lời ặc điểm chung, đó là để xác nhận câu trả lời „yes‟ đối với bộ dữ liệu vào „yes‟ của chúng, chúng ta có thể đƣa ra bằng chứng ngắn gọn dễ kiểm tra xác nhận câu trả lời „yes‟ cho bộ dữ liệu vào „yes‟ đó. Tính ngắn gọn dễ kiểm tra ám chỉ việc thời gian kiểm tra để đƣa ra kết quả chỉ mất thời gian đa thức. Ví dụ về những bài toán quyết định kiểu này: - Bài toán kiểm tra tính hợp số: “Có phải số n là hợp số?”, để xác nhận câu trả lời „yes‟ cho đầu vào n, chúng ta có thể đƣa ra một ƣớc số b (1 - Xem thêm -