Luận văn Thạc sĩ Khoa học máy tính: Thuật toán xấp xỉ ứng dụng vào một số bài toán lớp NP

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:72

Thêm vào BST

Báo xấu

19
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Nội dung chính của luận văn là nghiên cứu cơ sở toán học của các thuật toán gần đúng giải lớp các bài toán thuộc lớp NP và NPC, tìm hiểu chi tiết các bước mô tả thuật toán và các yêu cầu thiết kế các thuật toán. Trên cơ sở các thuật toán đã nghiên cứu, luận văn phân tích một số các bài toán thuộc lớp NP, NPC, xây dựng lời giải đúng và gần đúng, đánh giá kết quả.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Khoa học máy tính: Thuật toán xấp xỉ ứng dụng vào một số bài toán lớp NP

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG NGUYỄN HỮU CHUYÊN THUẬT TOÁN XẤP XỈ ỨNG DỤNG VÀO MỘT SỐ BÀI TOÁN LỚP NP LUẬN VĂN THẠC SỸ KHOA HỌC MÁY TÍNH Thái Nguyên – 2020
ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG NGUYỄN HỮU CHUYÊN THUẬT TOÁN XẤP XỈ ỨNG DỤNG VÀO MỘT SỐ BÀI TOÁN LỚP NP LUẬN VĂN THẠC SỸ KHOA HỌC MÁY TÍNH Chuyên ngành: KHOA HỌC MÁY TÍNH Mã số: 84 8 01 01 Người hướng dẫn: TS. Vũ Vinh Quang Thái Nguyên - 2020
i LỜI CẢM ƠN Để hoàn thành luận văn này trước tiên, em xin được gửi lời cảm ơn sâu sắc tới thầy giáo hướng dẫn TS. Vũ Vinh Quang đã tận tình hướng dẫn và đưa ra nhiều ý kiến đóng góp cho em trong suốt quá trình thực hiện và hoàn thành luận văn này. Em cũng xin được gửi lời cảm ơn đến các thầy giáo, cô giáo Trường Đại học Công nghệ Thông tin và Truyền thông – Đại học Thái Nguyên trực tiếp giảng dạy và truyền đạt những kiến thức quý báu cho em trong suốt quá trình học tập tại trường. Mặc dù đã cố gắng hoàn thành luận văn trong phạm vi và khả năng của mình, tuy nhiên sẽ không tránh khỏi những thiếu sót. Em rất mong nhận được sự cảm thông và chỉ bảo của quý thầy cô và các bạn. Em xin chân thành cảm ơn.
ii LỜI CAM ĐOAN Tôi xin cam đoan Luận văn “Thuật toán xấp xỉ ứng dụng vào một số bài toán lớp NP” là do tôi thực hiện dưới sự hướng dẫn trực tiếp của thầy TS. Vũ Vinh Quang. Các kết quả, số liệu nêu trong luận văn là trung thực. Tất cả những tham khảo từ những nghiên cứu liên quan đều được nêu rõ nguồn gốc trong danh mục tài liệu tham khảo và được chỉ rõ tham khảo trong tài liệu nào. Mọi sao chép không hợp lệ và vi phạm quy chế đào tạo, tôi xin chịu hoàn toàn trách nhiệm. HỌC VIÊN Nguyễn Hữu Chuyên
iii MỤC LỤC LỜI CẢM ƠN ............................................................................................................ I LỜI CAM ĐOAN .................................................................................................... II DANH MỤC CÁC BẢNG ....................................................................................... V DANH MỤC CÁC HÌNH ........................................................................................ V LỜI MỞ ĐẦU ............................................................................................................1 CHƯƠNG 1................................................................................................................2 MỘT SỐ KIẾN THỨC CƠ BẢN ............................................................................2 1.1 Thuật toán ............................................................................................................2 1.1.1 Khái niệm bài toán ........................................................................................2 1.1.2. Khái niệm thuật toán ....................................................................................2 1.1.3. Các yêu cầu của thuật toán ..........................................................................2 1.1.4 Các phương pháp mô tả thuật toán ..............................................................3 1.2. Độ phức tạp của thuật toán ...............................................................................4 1.2.1. Chi phí phải trả cho một quá trình tính toán ..............................................4 1.2.2. Thời gian thực hiện giải thuật .....................................................................4 1.2.3. Độ phức tạp của thuật toán ..........................................................................5 1.2.4. Các qui tắc xác định độ phức tạp thuật toán ..............................................6 1.3. Vấn đề phân lớp các bài toán. ...........................................................................6 1.4 Mô hình Bài toán Knapsack ...............................................................................7 Hình 1.1 Bài toán xếp ba lô dạng 0-1 ...................................................................8 CHƯƠNG 2..............................................................................................................13 MỘT SỐ THUẬT TOÁN XẤP XỈ ........................................................................13 2.1 Khái niệm về thuật toán xấp xỉ ........................................................................13 2.2 Phương pháp quy hoạch động ........................................................................15 2.2.1 Một số khái niệm .........................................................................................15 2.2.2 Các bước thực hiện .....................................................................................16 2.3 Phương pháp tham lam ....................................................................................19 2.3.1 Giới thiệu chung ..........................................................................................19 2.3.2 Đặc trưng của phương pháp tham lam ......................................................20 2.3.3 Các thành phần cơ bản ...............................................................................20
iv 2.3.4 Các bước xây dựng thuật toán tham lam ...................................................21 2.3.5 Mô hình thuật toán tham lam .....................................................................22 2.4 Thuật toán Di truyền GA .................................................................................27 2.4.1 Giới thiệu .....................................................................................................27 2.4.2 Các khái niệm cơ bản ..................................................................................28 2.4.3 Thuật toán GA .............................................................................................29 2.4.4 Cơ chế thực hiện GA ...................................................................................29 CHƯƠNG 3..............................................................................................................37 MÔ HÌNH BÀI TOÁN LẬP LỊCH TRONG BỆNH VIỆN ................................37 3.1 Đặt vấn đề ..........................................................................................................37 3.2 Giới thiệu tổng quan bệnh viện A ....................................................................37 3.3 Các mô hình phân công các ca trực .................................................................40 3.3.1 Bài toán phân công trực tại các khoa chuyên môn ...................................41 3.3.2 Bài toán phân công trực tại các Phòng khám............................................45 KẾT LUẬN ..............................................................................................................60 TÀI LIỆU THAM KHẢO ......................................................................................61 PHẦN PHỤ LỤC.....................................................................................................62
v DANH MỤC CÁC BẢNG STT Tên bảng 1 Bảng 2.1 Mô tả bảng phương án của phương pháp quy hoạch động 2 Bảng 3.1: Ma trận ràng buộc B 3 Bảng 3.2: Ma trận ràng buộc Y 4 Bảng 3.3: Lịch trực các buổi trong tuần 5 Bảng 3.4: Số buổi trực đối với các Bác sĩ – Y tá 6 Bảng 3.5: Bảng các Bác sĩ phù hợp với chuyên môn phòng khám (tham lam) 7 Bảng 3.6: Bảng các Y tá phù hợp với chuyên môn phòng khám (tham lam) 8 Bảng 3.7: Bảng các Bác sĩ sẵn sàng nhận buổi trực (tham lam) 9 Bảng 3.8: Bảng các Y tá sẵn sàng nhận buổi trực (tham lam) 10 Bảng 3.9: Lịch trực tại các phòng trong các buổi (tham lam) 11 Bảng 3.10: Số buổi trực đối với các Bác sĩ (tham lam) 12 Bảng 3.11: Số buổi trực đối với các Y tá (tham lam) 13 Bảng 3.12: Bảng các Bác sĩ phù hợp với chuyên môn phòng khám (GA) 14 Bảng 3.13: Bảng các Y tá phù hợp với chuyên môn phòng khám (GA) 15 Bảng 3.14: Bảng các Bác sĩ sẵn sàng nhận buổi trực (GA) 16 Bảng 3.15: Bảng các Y tá sẵn sàng nhận buổi trực (GA) 17 Bảng 3.16: Lịch trực tại các phòng trong các buổi (GA) 18 Bảng 3.17: Số buổi trực đối với các Bác sĩ (GA) 19 Bảng 3.18: Số buổi trực đối với các Y tá (GA) DANH MỤC CÁC HÌNH STT Tên hình Hình 1 Khối bắt đầu (Kết thúc) 2 Khối kiểm tra 3 Khối tính toán 4 Cung định hướng
1 LỜI MỞ ĐẦU Trong thực tế, lớp các bài toán giải được bằng các thuật toán có thời gian đa thức là không nhiều mà chủ yếu là chúng ta gặp các bài toán tối ưu mà việc tìm lời giải đúng của bài toán không trong thời gian đa thức (còn gọi là lớp NP, NPC). Để giải quyết các bài toán này, nói chung người ta phải xây dựng các thuật toán tìm nghiệm gần đúng tối ưu cho bài toán. Các thuật toán như vậy thường được gọi là các thuật toán xấp xỉ hay là các thuật toán gần đúng. Các thuật toán này hiện nay là mục tiêu nghiên cứu quan trọng trong công nghệ thông tin đặc biệt là đối với lớp các bài toán dữ liệu lớn. Nội dung chính của luận văn là nghiên cứu cơ sở toán học của các thuật toán gần đúng giải lớp các bài toán thuộc lớp NP và NPC, tìm hiểu chi tiết các bước mô tả thuật toán và các yêu cầu thiết kế các thuật toán. Trên cơ sở các thuật toán đã nghiên cứu, luận văn phân tích một số các bài toán thuộc lớp NP, NPC, xây dựng lời giải đúng và gần đúng, đánh giá kết quả. Dự kiến nội dung báo cáo của luận văn gồm: Phần mở đầu, 3 chương chính, phần kết luận, tài liệu tham khảo, phụ lục. Bố cục được trình bày như sau: Phần mở đầu của luận văn đưa ra lý do chọn đề tài và hướng nghiên cứu chính của luận văn. Chương 1: Trình bày các kiến thức cơ bản về thuật toán và độ phức tạp thuật toán bao gồm: khái niệm cơ bản về thuật toán, Vấn đề đánh giá độ phức tạp thuật toán. Phân lớp các bài toán dựa trên độ phức tạp của thuật toán. Chương 2: Trình bày cơ sở toán học của một số thuật toán xấp xỉ bao gồm: thuật toán tham lam, thuật toán quy hoạch động, Thuật toán GA và một số mô hình thực tế về các bài toán NP, NPC như: Bài toán Knapsack , bài toán đổi tiền, bài toán Domino cùng với các thuật giải tương ứng. Chương 3: Nghiên cứu mô hình 2 bài toán lập lịch trực các ca tại bệnh viện A Thái Nguyên bao gồm: Tìm hiểu xây dựng mô hình bài toán, xây dựng các ràng buộc thực tế và hàm mục tiêu, thiết lập các điều kiện tối ưu. Xây dựng thuật giải các bài toán bằng thuật toán tham lam và GA và cài đặt thuật toán trên máy tính điện tử. Tất cả các thuật toán tình bày trong luận văn được cài đặt trên máy tính điện tử bằng các ngôn ngữ lập trình C++ và Matlab.
2 CHƯƠNG 1 MỘT SỐ KIẾN THỨC CƠ BẢN VỀ THUẬT TOÁN VÀ ĐỘ PHỨC TẠP CỦA THUẬT TOÁN Nội dung chính của chương 1 trình bày các kiến thức cơ bản về thuật toán và độ phức tạp thuật toán bao gồm: khái niệm cơ bản về thuật toán, Vấn đề đánh giá độ phức tạp thuật toán. Phân lớp các bài toán dựa trên độ phức tạp của thuật toán. Các kiến thức cơ bản được tham khảo trong các tài liệu [1, 2, 3, 5, 6, 7] 1.1 Thuật toán 1.1.1 Khái niệm bài toán Một bài toán trong tin học là một bài toán thỏa mãn: xuất phát từ bộ INPUT đầu vào, chúng ta phải thu được bộ OUTPUT đầu ra. Một số vấn đề cần quan tâm + Bài toán được giải bằng máy tính điện tử + Cần làm rõ: dữ liệu cần được đưa vào máy tính (Input) là gì và cần lấy ra (Output) thông tin gì? + Làm thế nào để từ Input ta có được Output? (Thuật toán giải) Hiển nhiên đối với bài toán tin học là nghiên cứu thuật toán giải bài toán tương ứng. 1.1.2. Khái niệm thuật toán Định nghĩa 1.1: Thuật toán là một dãy hữu hạn các thao tác được sắp xếp theo một trình tự nhất định để sau khi thực hiện dãy các thao tác đó, từ input ta có output cần tìm [1]. Trong lý thuyết thuật toán, cụm từ “thuật toán” đôi khi người ta dùng bằng một từ khác là “giải thuật”. 1.1.3. Các yêu cầu của thuật toán Thuật toán phải đảm bảo được các yêu cầu sau đây: - Tính tổng quan: thuật toán phải đúng đối với mọi bộ dữ liệu đầu vào.
3 - Tính xác định: Các bước của thuật toán phải được trình bày rõ ràng, mạch lạc, đảm bảo cho người đọc chỉ hiểu theo một nghĩa duy nhất. - Tính khả thi: Thuật toán phải thực hiện được, nghĩa là ta có thể sử dụng máy tính kết hợp giữa các ngôn ngữ lập trình để thể hiện thuật toán trong thời gian hữu hạn. - Tính dừng: Nếu dữ liệu vào thỏa mãn điều kiện đầu vào thì thuật toán phải kết thúc và cho ra kết quả sau một số hữu hạn bước. - Tính chính xác (tính đúng đắn): Thuật toán phải cho kết quả chính xác và thể hiện đúng đắn trên cơ sở toán học. - Tính tối ưu: Thuật toán phải có chi phí về không gian bộ nhớ ít nhất và chạy trong thời gian nhanh nhất. 1.1.4 Các phương pháp mô tả thuật toán Thuật toán được thể hiện bằng một trong các cách sau:  Phương pháp liệt kê: Liệt kê lần lượt các bước để thực hiện thuật toán, tại mỗi bước ta sử dụng các ký hiệu toán học kết hợp với ngôn ngữ tự nhiên (cách này ít khi dùng).  Phương pháp sử dụng sơ đồ khối Sử dụng ba loại hình khối để thể hiện là: hình elip chỉ điểm bắt đầu hay kết thúc, hình thoi chỉ khối kiểm tra và hình chữ nhật chỉ khối tính toán. Có một cung định hướng để chỉ hướng đi của thuật toán. Khối bắt đầu (kết thúc) Khối kiểm tra Khối tính toán Cung định hướng Ta kết hợp ba loại hình khối và cung định hướng này để biểu diễn thuật toán.  Mô tả thuật toán bằng các chương trình Sử dụng ngôn ngữ lập trình để thể hiện thuật toán, cấu trúc chặt chẽ của các ngôn ngữ lập trình cho phép chúng ta thể hiện thuật toán một cách rõ ràng và dễ hiểu. Phương pháp này được áp dụng rộng rãi nhất. Trong các tài liệu, các thủ tục thể hiện thuật toán thường được mô tả bằng ngôn ngữ tựa Algol.
4 1.2. Độ phức tạp của thuật toán 1.2.1. Chi phí phải trả cho một quá trình tính toán Xét một quá trình tính toán, chi phí phải trả cho một quá trình tính toán bao gồm: + Chi phí về không gian: bộ nhớ - số ô nhớ cần sử dụng trong quá trình tính toán. + Chi phí về thời gian: thời gian cần sử dụng cho một quá trình tính toán. Nếu cho một thuật toán A. Thuật toán này thực hiện trên bộ dữ liệu e. Khi đó thuật toán A phải trả 2 giá: giá về không gian là LA(e), giá về thời gian là TA(e), e là bộ dữ liệu vào. Nhận xét: cùng một thuật toán A mà xác định thực hiện trên các bộ dữ liêu khác nhau sẽ trả các giá khác nhau. Khi đó ta có các khái niệm về chi phí phải trả trong các trường hợp như sau: + Chi phí phải trả trong trường hợp xấu nhất ứng với bộ dữ liệu xấu nhất so với Output + Chi phí phải trả trung bình: là tổng số các chi phí khác nhau ứng với các bộ số liệu chia cho tổng số số bộ số liệu. + Chi phí phải trả tiệm cận: Đó là biểu thức biểu diễn tốc độ tăng của chi phí thực tế phải trả. Nó có giá trị tiệm cận với chi phí thực tế. Nhận xét: Ngày nay do sự phát triển không ngừng của khoa học công nghệ kỹ thuật điện tử nên chi phí về bộ nhớ không còn là vấn đề cần thiết phải bàn tới mà ta chỉ quan tâm tới chi phí phải trả về thời gian thực hiện giải thuật. Từ đây ta chỉ xét đến thời gian thực hiện giải thuật T(n), hay đó chính là độ phức tạp của thuật toán. 1.2.2. Thời gian thực hiện giải thuật Với một bài toán, không chỉ có một giải thuật. Chọn một giải thuật đưa tới kết quả nhanh là một đòi hỏi thực tế. Nhưng căn cứ vào đâu để có thể nói được giải thuật này nhanh hơn giải thuật kia? Có thể thấy ngay: thời gian thực hiện một giải thuật, (hay chương trình thể hiện một giải thuật đó) phụ thuộc vào rất nhiều yếu tố. Một yếu tố cần chú ý trước tiên đó là kích thước của dữ liệu đưa vào. Chẳng hạn thời gian sắp xếp một dãy số
5 phải chịu ảnh hưởng của số lượng các số thuộc dãy số đó. Nếu gọi n là số lượng này (kích thước của dữ liệu vào) thì thời gian thực hiện T của một giải thuật phải được biểu diễn như một hàm của n: T(n). Các kiểu lệnh và tốc độ xử lý của máy tính, ngôn ngữ viết chương trình và chương trình dịch ngôn ngữ ấy đều ảnh hưởng tới thời gian thực hiện; nhưng những yếu tố này không đồng đều với mọi loại máy trên đó cài đặt giải thuật, vì vậy không thể đưa chúng vào khi xác lập T(n). Điều đó có nghĩa là T(n) không thể được biểu diễn thành đơn vị thời gian bằng giây, bằng phút được. Tuy nhiên, không phải vì thế mà không thể so sánh được các giải thuật về mặt tốc độ. Nếu như thời gian thực hiện của một giải thuật là T1(n) = c.n2 và thời gian thực hiện một giải thuật khác là T2(n) = k.n (với c và k là một hằng số nào đó), thì khi n khá lớn, thời gian thực hiện giải thuật T2 rõ ràng ít hơn so với thời gian thực hiện giải thuật T1. Như vậy, nếu nói thời gian thực hiện giải thuật bằng T(n) tỉ lệ với n2 hay tỉ lệ với n cũng cho ta ý niệm về tốc độ thực hiện giải thuật đó khi n khá lớn (với n nhỏ thì việc xét T(n) không có ý nghĩa). Cách đánh giá thời gian thực hiện giải thuật độc lập với máy tính và các yếu tố liên quan với máy như vậy sẽ dẫn tới khái niệm về cấp độ lớn của thời gian thực hiện giải thuật hay còn gọi là độ phức tạp tính toán của giải thuật. 1.2.3. Độ phức tạp của thuật toán Định nghĩa 1.2 : Một hàm f(n) được xác định là O(g(n)), kí hiệu f(n) = O(g(n)) nếu tồn tại các hằng số C và số nguyên n0 sao cho f(n) ≤ Cg(n) với mọi n ≥ n0 Thông thường các hàm thể hiện độ phức tạp tính toán của giải thuật có dạng: O(log2n), O(n), O(nlog2n), O(n2), O(n3), O(2n), O(n!), O(nn). Các hàm như 2n, nn được gọi là hàm loại mũ. Các dạng như n3, n2, nlog2n, log2n được gọi là các hàm loại đa thức. Giải thuật với thời gian thực hiện có cấp hàm đa thức thì thường hiệu quả và chấp nhận được.
6 1.2.4. Các qui tắc xác định độ phức tạp thuật toán  Quy tắc tổng: Giả sử T1(n) và T2(n) là thời gian thực hiện của 2 đoạn chương trình P1 và P2 kế tiếp nhau T1(n) = O(f(n)); T2(n) = O(g(n)) thì thời gian thực hiện P1 rồi P2 tiếp theo sẽ là:T1(n)+ T2(n)=O(max(f(n), g(n))).  Quy tắc nhân: Nếu tương ứng với P1 và P2 là T1(n)=O(f(n)); T2(n) = O(g(n)) thì thời gian thực hiện P1 và P2 lồng nhau sẽ là: T1(n).T2(n) = O(f(n).g(n)). Chú ý: Trong các ngôn ngữ lập trình, chúng ta có thể đánh giá + Thời gian thực hiện mỗi câu lệnh Gán, Read, Write là O(1). + Thời gian thực hiện mỗi chuỗi tuần tự các câu lệnh được tính theo quy tắc cộng. + Thời gian thực hiện cấu trúc If (điều kiện) then ... được tính bằng thời gian thực hiện câu lệnh sau then hoặc sau else. Còn câu lệnh điều kiện thường là O(1). + Thời gian thực hiện vòng lặp được tính là tổng trên tất cả số lần lặp thời gian thực hiện thân vòng lặp. Nếu thời gian thực hiện thân vòng lặp là hằng số thì thời gian thực hiện vòng lặp là tích của số lần lặp với thời gian thực hiện thân vòng lặp. 1.3. Vấn đề phân lớp các bài toán. Xét một bài toán tin học bất kì, chúng ta quan tâm đến các bài toán có lời giải. Vì độ phức tạp giải thuật đối với mỗi bài toán là khác nhau, trên cơ sở đó các bài toán cũng được phân chia thành các lớp thông qua độ phức tạp thuật toán giải chúng. Chúng ta xét các khái niệm sau:  Lớp bài toán P (Lớp P-Polynomial time): là lớp các bài toán có thể giải được bằng thuật toán đơn định đa thức có độ phức tạp đa thức  Lớp bài toán NP (Lớp NP - Nondeterministic Polynomial ): là lớp các bài toán có thể giải được bằng các thuật toán không đơn định đa thức. Hiện nay chúng ta đang chấp nhận P  NP.  Lớp NPC + Khái niệm dẫn về được: Bài toán B được gọi là dẫn về được bài toán A một cách đa thức nếu có một thuật toán đơn định đa thức để giải bài toán A thì cũng có một thuật toán đơn định đa thức để giải bài toán B. ký hiệu B  A.
7 + Bài toán NP – khó (NP hard): Bài toán A được gọi là NP – khó nếu có bài toán L  A với  L  NP. + Bài toán NP đầy đủ: Bài toán A được gọi là NP đầy đủ (NP-Complate) nếu: A là NP-khó và A  NP. Từ đây chúng ta định nghĩa về lớp NPC như sau: Định nghĩa 1.3: Lớp NPC là lớp các bài toán NP đầy đủ, có độ phức tạp hàm mũ. Qua đó cho thấy: P  NPC = Ø 1.4 Mô hình Bài toán Knapsack Mô hình bài toán Knapsack là vấn đề đã được nghiên cứu trong hơn một thế kỷ từ năm 1897 cho đến nay. Việc nghiên cứu bài toán Knapsack đã được đưa ra đầu tiên trong các công trình của nhà toán học Tobias Dantzig (1884-1956). Các công trình tiếp theo được giới thiệu lần đầu tiên bởi Gallo, Hammer và Simeone vào năm 1960. Một công trình nghiên cứu các tác giả thuộc Đại học Stony Brook năm 1998 cho thấy rằng trong số 75 vấn đề về các bài toán NPC, bài toán Knapsack là 1 trong 18 bài toán quan trọng nhất trong lĩnh vực Toán và Công nghệ thông tin. Bài toán KNAPSACK - Bài toán xếp ba lô là một bài toán tối ưu tổ hợp. Bài toán được đặt tên từ vấn đề chọn những gì quan trọng có thể nhét vừa vào trong một cái túi (với giới hạn khối lượng) để mang theo trong một chuyến đi. Các bài toán tương tự thường xuất hiện trong ngành kinh doanh, lý thuyết tổ hợp, lý thuyết độ phức tạp tính toán, lý thuyết mật mã học và một số lĩnh vực trong toán ứng dụng. Bài toán được phát biểu tổng quát như sau: Có N đồ vật kí hiệu là x1 ,..., xn . Mỗi đồ vật x j có một giá trị p j và một thể tích w j , j  1, N . Thể tích mà có thể chứa trong ba lô là M . Hãy xác định phương án chọn các đồ vật để sao cho: số đồ vật chứa vừa trong ba lô và tổng giá trị các đồ vật được chọn là lớn nhất có thể được.
8 Hình 1.1 Bài toán xếp ba lô dạng 0-1 Hình 1.1 trên là ví dụ về một bài toán xếp ba lô giới hạn 1 chiều: chọn các hộp nào để làm cực đại lượng tiền trong khi giữ được tổng khối lượng dưới 15 kg? Bài toán đa chiều có thể xét đến khối lượng riêng và kích thước của các hộp, đó là bài toán xếp vali điển hình Trong lớp các bài toán Knapsack, người ta thường đưa ra một số dạng bài toán điển hình như sau: + Bài xếp ba lô 0-1 là bài toán không hạn chế số đồ vật thuộc mỗi loại, bài toán được mô hình hóa như sau: n n Cực đại hóa hàm F ( X )   p j x j sao cho j 1 w j 1 j xj  M trong đó X   x1 , x2 ,..., xn  , x j  0,1 , j  1, n . + Bài xếp ba lô bị chặn hạn chế số đồ vật thuộc mỗi loại không được vượt quá một lượng xác định. Bài xếp ba lô bị chặn có thể được phát biểu bằng mô hình toán học như sau: n n Cực đại hóa hàm F ( X )   p j x j sao cho j 1 w j 1 j x j  M trong đó X   x1 , x2 ,..., xn  , x j   0,1 , . x j  0, b j  , b j  N , j  1, n.
9 Một trường hợp đặc biệt của bài toán Knapsack là bài toán thỏa mãn các tính chất sau đây:  Là một bài toán quyết định  Là một bài toán xếp ba lô dạng 0-1  Phương án tối ưu là số đồ vật xếp vừa khít ba lô. Đối với dạng bài toán này, trong thực tế thường xuất hiện ở các dạng sau đây: Dạng 1: Cho trước một tập các số nguyên, tồn tại hay không một tập con có tổng đúng bằng 0? Dạng 2: Cho một tập các số nguyên dương, tồn tại hay không một tập con có tổng đúng bằng M ? Các bài toán này được gọi là bài toán tổng các tập con (subset sum problem) được sử dụng nhiều trong ngành mật mã học. Tổng quát hóa, từ mô hình bài toán KNAPSACK cũng có rất nhiều cách phát biểu khác nhau. Sau đây là một số cách phát biểu bài toán: Bài toán tập con cực đại: Cho một tập hữu hạn U  ui  , i  1,...n , mỗi phần tử ui  U có kích cỡ S (ui ) và số tự nhiên B . Hãy xác định một tập con U '  U sao cho  S (u )  B . Trong đó, ui  U ' . i Knapsack thuộc lớp bài toán NPC. Nói chung không có thuật toán hữu hiệu nào để giải nó cho trường hợp bất kỳ. Điều này không có nghĩa là tất cả các trường hợp đều có cùng độ phức tạp. Nhận xét: + Bài toán trên có thể xác định lời giải chính xác bẳng thuật toàn duyệt toàn bộ theo tư tưởng như sau: Hãy duyệt mọi tổ hợp của các đồ vật, ứng với mỗi tổ hợp (i1,i2,..,ik) thử điều kiện w(i1)+w(i2)+…+w(ik) = M để xác định nghiệm đúng. Khi đó số phương án được duyệt chính bằng C n1 + C n2 + ...C nn - 1 + C nn ; 2n tức là chúng ta có độ phức tạp của thuật toán là hàm mũ.
10 + Chúng ta có thể giải bài toán bằng thuật toán không đơn định đa thức như sau: sử dụng hàm: CHOICE(0,1): là hàm chọn các đồ vật. Khi đó bài toán được đưa về bài toán sau đây Liệu có tồn tại tập chỉ số T  {1,2,.. ,n} thỏa mãn w iT i M. Khi đó bài toán được giải bằng thuật toán sau đây: For i:=1 to n do xi:= CHOICE({0,1}); n if x a i 1 i i =B then TRUE else FALSE Thuật toán trở thành thuật toán không đơn định đa thức với độ phức tạp O(n). + Bài toán trên có thể đưa về dạng tổng quát hơn bằng cách thay Output bằng: “Hãy xác định nhóm đồ vật đặt trong balo sao cho phần thừa còn lại là ít nhất”. Khi đó việc giải bài toán cũng được thực hiện tương tự, tuy nhiên chúng ta phải đưa thêm hàm mục tiêu f=b-(a(i1)+a(i2)+…+a(ik)). Khi đó phương án cần xác định là phương án thỏa mãn f đạt giá trị nhỏ nhất (f>=0).  Bài toán KNASPACK mở rộng Input: + Cho n đồ vật, đồ vật thứ i có thể tích là wi, có giá trị là pi + Cho 1 ba lô có thể tích M Output: Hãy xác định nhóm đồ vật thỏa mãn: tổng thể tích không vượt quá ba lô đồng thời tổng giá trị là lớn nhất Nhận xét: + Bài toán trên có thể xác định lời giải chính xác bằng thuật toán duyệt toàn bộ theo tư tưởng như sau: Kí hiệu (x 1, x 2 , ...x n ) là một phương án lựa chọn các đồ vật với x i Î {0,1} . Khi đó hãy duyệt mọi phương án (x 1, x 2 , ...x n ) , ứng với mỗi phương án xác định điều kiện w1x 1 + w2x 2 + ... + wn x n £ M . Nếu thỏa mãn thì
11 xác định tiếp giá trị hàm mục tiêu f (X ) = p1x 1 + p2x 2 + ... + pn x n từ đó xác định phương án tốt nhất. Hiển nhiên bài toán đưa về bài toán duyệt mọi dãy nhị phân có độ dài n với độ phức tạp hàm mũ. Thuật toán giải được mô tả như sau: using namespace std; int X[N],W[N],M,P[N],n,fmax,Xluu[N]; void input() { coutn; coutM; cout
12 được đưa về bài toán sau đây: Liệu có tồn tại tập chỉ số T  {1,2,.. ,n} thỏa mãn n n w x i i  M và  p i xi đạt max. Khi đó bài toán được giải bằng thuật toán sau i 1 i 1 đây: For i:=1 to n do xi:= CHOICE({0,1}); n if x w i 1 i i
13 CHƯƠNG 2 MỘT SỐ THUẬT TOÁN XẤP XỈ Nội dung chính của chương 2 sẽ nghiên cứu một số thuật toán xấp xỉ đã được nghiên cứu trong các kĩ thuật thiết kế thuật toán như: Thuật toán tham lam, thuật toán quy hoạch động, thuật toán di truyền GA, cùng các bài toán mẫu mực trong thực tế. Các thuật toán đã được tham khảo trong các tài liệu [3, 4, 5, 6, 7, 8]. Việc mô phỏng các thuật toán được thực hiện trên nền ngôn ngữ lập trình C++ hoặc Matlab. 2.1 Khái niệm về thuật toán xấp xỉ Nhiều bài toán có ý nghĩa rất quan trọng trong thực tiễn lại là NP đầy đủ. Nếu là một bài toán NP đầy đủ, ta không thể tìm một thuật toán thời gian đa thức để giải nó chính xác. Có hai cách tiếp cận để khắc phục tính đầy đủ NP. Thứ nhất: nếu các đầu vào thực tế là nhỏ, một thuật toán có thời gian thực hiện hàm mũ có thể hoàn toàn chấp nhận được Thứ hai: vẫn có thể tìm các giải pháp gần tối ưu trong thời gian đa thức (hoặc trong trường hợp xấu nhất hoặc tính trung bình). Trong thực tế để tính gần tối ưu thường là đủ. Một thuật toán trả về các giải pháp gần tối ưu được gọi là một thuật toán xấp xỉ. Xét một bài toán tối ưu hóa, ở đó mỗi giải pháp có thể đưa ra có một mức hao phí dương, và ta muốn tìm giải pháp gần tối ưu. Tùy thuộc vào bài toán, một giải pháp gần tối ưu có thể được định nghĩa là một giải pháp có mức hao phí khả dĩ cực đại hoặc một giải pháp có mức hao phí khả dĩ cực tiểu, bài toán có thể là bài toán cực đại hóa hoặc cực tiểu hóa. Một số thuật toán xấp xỉ cho bài toán có một cận tỷ số P(n) nếu với bất kỳ đầu vào có kích cỡ n , mức hao phí C của giải pháp mà thuật toán xấp xỉ tạo sẽ nằm trong một thừa số p(n) của mức hao phí C* của một giải pháp tối ưu: Max  C C*   * ,  ≤ p(n) C C 