ĐẠ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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Tên bảng
Bảng 2.1 Mô tả bảng phương án của phương pháp quy hoạch động
Bảng 3.1: Ma trận ràng buộc B
Bảng 3.2: Ma trận ràng buộc Y
Bảng 3.3: Lịch trực các buổi trong tuần
Bảng 3.4: Số buổi trực đối với các Bác sĩ – Y tá
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)
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)
Bảng 3.7: Bảng các Bác sĩ sẵn sàng nhận buổi trực (tham lam)
Bảng 3.8: Bảng các Y tá sẵn sàng nhận buổi trực (tham lam)
Bảng 3.9: Lịch trực tại các phòng trong các buổi (tham lam)
Bảng 3.10: Số buổi trực đối với các Bác sĩ (tham lam)
Bảng 3.11: Số buổi trực đối với các Y tá (tham lam)
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)
Bảng 3.13: Bảng các Y tá phù hợp với chuyên môn phòng khám (GA)
Bảng 3.14: Bảng các Bác sĩ sẵn sàng nhận buổi trực (GA)
Bảng 3.15: Bảng các Y tá sẵn sàng nhận buổi trực (GA)
Bảng 3.16: Lịch trực tại các phòng trong các buổi (GA)
Bảng 3.17: Số buổi trực đối với các Bác sĩ (GA)
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
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
Hình
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:
Cực đại hóa
n
hàm F ( X ) p j x j sao cho
j 1
n
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
Cực đại hóa hàm F ( X ) p j x j sao cho
j 1
n
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
iT
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()
{
cout<<"Nhap so do vat: ";cin>>n;
cout<<"Nhap the tich ba lo: ";cin>>M;
cout<<"Nhap the tich cac do vat: ";printf("\n");
for (int i=1;i<=n;i++) {cout<<"Do vat: "<>W[i];}
cout<<"Nhap gia tri cac do vat : ";printf("\n");
for (int i=1;i<=n;i++) {cout<<"Do vat: "<>P[i];}
fmax=0;
}
void output()
{ int f,T;
f=0;T=0;
for (int i=1;i<=n;i++) {T=T+X[i]*W[i];f=f+X[i]*P[i];}
if ((T<=M)&(f>fmax))
{
fmax=f;
for (int i=1;i<=n;i++) Xluu[i]=X[i];}
}
void Try(int k)
{
int j;
for (j=0;j<=1;j++)
{ X[k]=j;if (k==n) output();else Try(k+1);}
}
int main()
{
input();
Try(1);
cout<<"Phuong an toi uu: ";
for (int i=1;i<=n;i++) cout<- Xem thêm -