ĐẠ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
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
các bài toán dữ liệu lớ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ó đồ vật kí hiệu là . Mỗi đồ vật có một giá trị và một thể
,
tích . Thể tích mà có thể chứa trong ba lô là . 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
n
n
w
x M
toán được mô hình hóa như sau:
F X (
)
j
j
p x j
j
sao cho
j
1
j
1
X
,...,
,
x
j
1,
n
Cực đại hóa hàm trong đó
.
0,1 ,
x x , 1 2
x n
j
+ 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
n
n
w
x M
F X (
)
toán học như sau:
j
j
p x j
j
sao cho
j
1
j
1
X
,...,
,
x
Cực đại hóa hàm trong đó
0,1 ,
x x , 1 2
x n
j
x
0,
b
,
b
N j ,
1,
n .
j
j
j
.
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 ?
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 , mỗi phần
tử có kích cỡ và số tự nhiên . Hãy xác định một tập con sao
cho . Trong đó, .
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 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 .
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});
if =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 là một phương án lựa chọn các đồ
vật với . Khi đó hãy duyệt mọi phương án , ứng với mỗi
phương án xác định điều kiện . Nếu thỏa mãn thì
11
xác định tiếp giá trị hàm mục tiêu 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:
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: "<
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];}
for (j=0;j<=1;j++) { X[k]=j;if (k==n) output();else Try(k+1);}
input();
Try(1);
cout<<"Phuong an toi uu: ";
for (int i=1;i<=n;i++) cout< #include 25 if (M-W[i]>0){cout< i=1;T=0;
while (i<=n)
{
printf("\n");
cout<<"Tong gia tri: "< , số lượng các mệnh giá là không hạn chế. } Ví dụ 2.3: Bài toán đổi tiền
Input:
+ Có n loại tiền với các mệnh giá
+ Có số tiền thừa là b
Output: Phương án trả tiền thừa cho khách hàng sao cho tổng số tờ là ít nhất. Phân tích: Hiển nhiên theo tư tưởng tự nhiên thì để số tờ là ít nhất, chúng ta cần thực hiện chiến lược trả loại tiền có mệnh giá cao nhất tại thời điểm hiện tại, sau đó chọn tiếp các mệnh giá thấp hơn để trả cho đến khi trả hết số tiền thừa. Vì vậy ta xây dựng thuật toán theo tư tưởng tham lam như sau Bước 1: Sắp xếp các tờ mệnh giá theo giá trị mệnh giá giảm dần Bước 2: Khởi động S=0 (S chứa giá trị tiền đã trả) Bước 3: Lần lượt trả các tờ tiền mệnh giá lớn nhất (Tại thời điểm hiện tại), mỗi lần trả cần kiểm tra S-b>0 tức là việc trả là hợp lệ. Nếu không hợp lệ thì chọn tờ tiền có mệnh giá tiếp sau. Quá trình sẽ kết thúc khi S-b=0. Thuật toán được mô tả bằng ngôn ngữ lập trình C++ như sau: tg=a;a=b;b=tg;} #include 26 cout<<"Nhap so menh gia: ";cin>>n;
cout<<"Nhap so tien thua: ";cin>>T;
cout<<"Nhap menh gia cac dong tien: ";printf("\n");
for (int i=1;i<=n;i++) {cout<<"Loai tien thu: "< for (int i=1;i<=n;i++) cout< if (A[j-1] int A[N],X[N];
input(A,T,n);
for (i=1;i<=n;i++) X[i]=i;
bubble_sort(A,X,n);
cout<<"Phuong an tra tien thua: Hay tra cac loai menh gia: ";
printf("\n");
for (i=1;i<=n;i++)
{ k=T/A[i];
if (k>0) {T=T-k*A[i];cout<<"Menh gia"<< A[i]<<" So to tien :"< { cout<<"Don vi quy uoc la ngan dong: ";printf("\n");
}
void output(int A[],int X[],int n)
{ cout<<"Cac menh gia sau khi sap xep theo gia tri giam dan: ";printf("\n");
}
void bubble_sort(int A[],int X[],int n)
{int i,j;int C[n];
for (i=n;i>1;i--)
{ for (j=2;j<=i;j++)
}}
int main()
{ int i,n,T,k;
else cout<<"Menh gia: "<< A[i]<<" So to tien :"<<0;
printf("\n");} cout<<"So du: "< 27 Nhận xét: Qua 2 ví dụ trên chúng ta có thể thấy + Thuật toán tham lam được thiết kế rất đơn giản, dễ hiểu + Thuật toán thường sử dụng phương án sắp xếp do đó có độ phức tạp thuật toán là thấp (Nếu dùng sắp xếp đệ quy thì độ phức tạp là O(nlogn)). + Về cơ bản nghiệm thu được chỉ là nghiệm xấp xỉ. Để tìm nghiệm chính xác chỉ có thể nhận được bằng thuật toán quay lui. + Điểm mấu chốt của thuật toán chính là việc xác định được cơ chế chọn Select() 2.4 Thuật toán Di truyền GA 2.4.1 Giới thiệu Thuật toán di truyền GA do D.E. Goldberg đề xuất là kỹ thuật phỏng theo quá trình thích nghi tiến hóa của các quần thể sinh học dựa trên học thuyết Darwin. Trong GA, việc tìm kiếm được bắt đầu với một quần thể, hay một tập hợp có chọn lọc ban đầu. Các cá thể của quần thể hiện tại khởi nguồn cho quần thể thế hệ kế tiếp bằng các hoạt động lai ghép và đột biến ngẫu nhiên – được lấy mẫu sau các quá trình tiến hóa. Ở mỗi bước, cá thể nào phát triển hơn, thích ứng hơn với môi trường sẽ tồn tại và ngược lại sẽ bị đào thải. GA giải quyết các bài toán tối ưu thông qua các quá trình cơ bản: lai tạo, đột biến và chọn lọc cho các cá thể trong quần thể. Để sử dụng GA đòi hỏi phải xác định được: khởi tạo quần thể ban đầu, hàm đánh giá các lời giải theo mức độ thích nghi – hàm mục tiêu, các toán tử di truyền tạo hàm sinh sản. Trong công nghệ thông tin GA là một lĩnh vực mới được coi là có tốc độ phát triển nhanh. Có thể chia thành 5 hướng nghiên cứu như sau : - GA (Genetic Algorithm - GA): Dựa vào quá trình di truyền trong tự nhiên để cải tiến lời giải qua các thế hệ bắt nguồn từ một tập các lời giải ban đầu. - Quy hoạch tiến hoá (Evolutionary Programming - EP): Dựa vào quy luật tiến hoá, tìm phương pháp kết hợp đủ khả năng giải quyết trọn vẹn một bài toán từ một lớp các phương pháp giải quyết được một số phần của bài toán. 28 - Các chiến lược tiến hoá (Evolutionary Strategies - ES): Dựa trên một số chiến lược ban đầu, tiến hoá để tạo ra những chiến lược mới phù hợp với môi trường thực tế một cách tốt nhất. - Lập trình di truyền (Genetic Programming - GP): Mở rộng GA trong lĩnh vực các chương trình của máy tính. Mục đích của nó là để sinh ra một cách tự động các chương trình máy tính giải quyết một cách tối ưu một vấn đề cụ thể. - Các hệ thống phân loại (Classifier Systems- CS): Các GA đặc biệt được dùng trong việc học máy và việc phát hiện các quy tắc trong các hệ dựa trên các quy tắc. Ngày nay GA càng trở nên quan trọng, đặc biệt là trong lĩnh vực tối ưu hoá với lớp các bài toán NP, một lĩnh vực có nhiều bài toán thú vị, được ứng dụng nhiều trong thực tiễn nhưng thường khó và chưa có giải thuật hiệu quả để giải . 2.4.2 Các khái niệm cơ bản Cá thể, nhiễm sắc thể: Trong GA, một cá thể biểu diễn một phương án của bài toán. Trong trường hợp tổng quát, một cá thể có nhiều NST (NST), ở đây ta quan niệm một cá thể chỉ có một NST. Do đó khái niệm cá thể và NST trong GA coi như là tương đương. Quần thể: Quần thể là một tập hợp các cá thể có cùng một số đặc điểm nào đấy. Trong GA ta quan niệm quần thể là một tập các lời giải của một bài toán. Chọn lọc: Chọn lọc trong GA chính là cách chọn các cá thể có độ thích nghi tốt để đưa vào thế hệ tiếp theo hoặc để cho lai ghép, với mục đích là sinh ra các cá thể mới tốt hơn. Thông thường việc chọn lọc được thông qua hàm mục tiêu Lai ghép: Trong GA, lai ghép được coi là một sự tổ hợp lại các tính chất trong hai lời giải cha mẹ nào đó để sinh ra một lời giải mới mà có đặc tính mong muốn là tốt hơn thế hệ cha mẹ. Đây là một quá trình xảy ra chủ yếu trong GA. Đột biến: Đột biến có thể tạo ra một cá thể mới tốt hơn hoặc xấu hơn cá thể ban đầu. Tuy nhiên trong GA thì ta luôn muốn tạo ra những phép đột biến cho phép cải thiện lời giải qua từng thế hệ. 29 2.4.3 Thuật toán GA Với các khái niệm được giới thiệu ở trên, giải thuật GA được thực hiện thông qua các bước cơ bản sau đây: 1. Xác lập các tham số ban đầu của bài toán. 2. Khởi tạo: Sinh ngẫu nhiên một quần thể gồm n cá thể (là n lời giải ban đầu của bài toán). 3. Xác lập quần thể mới: 3.1 Tiến hành lai ghép các cặp bố-mẹ với một xác suất lai ghép được chọn để tạo ra một cá thể mới đưa tiếp vào quần thể. 3.2 Tính độ thích nghi của tất cả các cá thể thuộc quần thể. 3.3 Chọn lọc n cá thể mới từ quần thể mới theo độ thích nghi để tạo ra quần thể cho thế hệ tiếp sau. 3.4 Đột biến k các thể 4. Kiểm tra điều kiện dừng: Nếu điều kiện được thỏa mãn thì thuật toán kết thúc và trả về lời giải tốt nhất chính là quần thể hiện tại. 2.4.4 Cơ chế thực hiện GA
Mã hóa Để có thể thực hiện GA, vấn đề đầu tiên là xuất phát từ bài toán thực tế, ta cần phải mô tả các phương án của bài toán dưới một dạng nào đó (mô hình toán học, tin học, …). Vấn đề mô tả đó được gọi là các phương pháp mã hóa. Thông + Mã hoá nhị phân: Mã hoá nhị phân là phương pháp mã hoá NST phổ biến thường người ta sử dụng một trong các phương pháp như sau: nhất. Trong mã hoá nhị phân, mỗi NST là một chuỗi nhị phân. Khi đó, mỗi chuỗi nhị phân sẽ biểu diễn hàm tại một tập giá trị của các biến. Mã hoá nhị phân tuy là phổ biến nhưng nó có một nhược điểm là có thể tạo ra không gian mã hoá lớn hơn so với không gian giá trị của NST. Do đó, với nhiều bài toán thì biểu diễn nhị phân là không hữu hiệu. 30 + Mã hoá hoán vị: Trong mã hoá hoán vị, mỗi NST là một chuỗi các số biểu diễn một thứ tự sắp xếp. Mã hoá hoán vị phù hợp cho các bài toán liên quan đến thứ tự. Đối với các bài toán này. Mã hoá hoán vị có thể được sử dụng trong các bài toán liên quan đến thứ tự như bài toán du lịch hay bài toán lập lịch. + Mã hoá số thực: Mã hoá trực tiếp theo giá trị có thể được dùng trong các bài toán sử dụng giá trị phức tạp như trong số thực. Trong đó, mỗi NST là một chuỗi các giá trị thực. Mã hoá số thực thường dùng cho các bài toán đặc biệt. Thông thường mỗi NST được mã hóa là một véc tơ trong không gian. Cách mã hóa này thường sử dụng đối với các bài toán tối ưu số và được phát triển mạnh trong giai đoạn hiện nay. Khởi tạo quần thể ban đầu Khởi tạo quần thể ban đầu là bước đầu tiên trong GA để tạo ra một cách ngẫu nhiên các lời giải ban đầu. Tuỳ vào từng bài toán cụ thể mà ta có các phương pháp khởi tạo khác nhau. Chất lượng của quần thể ban đầu càng cao thì lời giải mà GA đưa ra càng tốt. Thông thường chúng ta dùng phương pháp ngẫu nhiên để khởi tạo. Xác định hàm thích nghi Hàm thích nghi được xây dựng sao cho giá trị thích nghi phải phản ánh được giá trị thực của NST trong việc đáp ứng yêu cầu của bài toán. Đối với bài toán tối ưu hóa thì hàm thích nghi chính là hàm mục tiêu của bài toán. Cơ chế lựa chọn Cơ chế lựa chọn được áp dụng khi chọn các cá thể từ quần thể để thực hiện việc lai ghép và đột biến, tạo ra quần thể ở thế hệ tiếp sau Có nhiều cách để lựa chọn các cá thể từ một quần thể. Tùy từng mô hình bài toán khác nhau, chúng ta có thể xây dựng các phương pháp lựa chọn khác nhau: thông thường người ta sử dụng một trong 2 phương pháp sau để lựa chọn các cá thể vào quá trình lai ghép + Lựa chọn ngẫu nhiên theo xác suất từ quần thể lấy N cá thể để thực hiện lại ghép + Chọn tất cả các cá thể cùng tham gia lai ghép. 31 Các toán tử di truyền Các toán tử di truyền của GA là toán tử lai ghép và đột biến. Đây là hai toán tử có tác động lớn đến chất lượng của giải thuật. Các toán tử này được xây dựng phụ thuộc vào cách mã hoá các NST. Tuỳ thuộc vào các bài toán cụ thể và cách mã hoá NST mà ta xây dựng hai loại toán tử này thích hợp. Thông thường người ta thưởng sử dụng các toán tử lai ghép dưới dạng sau đây + Lai ghép đơn điểm: - Một điểm cắt được chọn tại một vị trí thứ k trên NST. - Từ đầu NST đến vị trí thứ k, NST con sao chép từ cha, phần còn lại sao chép từ mẹ. + Lai ghép hai điểm: - Hai điểm cắt được chọn . - Từ đầu cho đến điểm cắt thứ nhất được sao chép từ cha, từ điểm cắt thứ nhất đến điểm cắt thứ hai sao chép từ mẹ và phần còn lại sao chép từ cha. + Lai ghép mặt nạ : - Xây dựng một mặt nạ là một chuỗi nhị phân có chiều dài bằng chiều dài NST, Mặt nạ được phát sinh ngẫu nhiên đối với từng cặp cha mẹ. - Xây dựng NST mới: Duyệt qua mặt nạ, bit có giá trị 1 thì sao chép gen tại vị trí đó từ NST cha sang con, bit có giá trị 0 thì sao chép từ mẹ. Sau đây chúng ta nghiên cứu một số bài toán NP mà lời giải xấp xỉ nhận được từ GA Ví dụ 2.4: Bài toán KNAPSACK Input: + Cho n đồ vật, đồ vật thứ i có thể tích là ai, có giá trị là pi + Cho 1 ba lô có thể tích b 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 Phân tích Kí hiệu: Một phương án lấy đồ vật là một dãy nhị phân có độ dài n trong đó giá trị bit 0 tương ứng với không lấy đồ vật và giá trị bit 1 là lấy đồ
vật tương ứng. 32 Khi đó: + Hàm mục tiêu của bài toán là + Điều kiện ràng buộc của bài toán Chúng ta sử dụng toán tử lại ghép nhị phân đơn điểm hoặc đa điểm. Trong quá trình lai ghép và chọn lọc luôn luôn chọn các phương án thỏa mãn điều kiện ràng buộc. function KA = KNAPSACK (A,C,b,KK)
clc;
N=length(A);M=10;%popsize
%Khoi tao
M=0;
while M<=10
z=round(rand(1,N));s=0;
for i=1:N
s=s+A(i)*z(i);
end;
if s<=b
M=M+1;
Quan_the(M,:)=z;
end;
end;
% thuat toan GA
count=0;k=3;
while count Khi đó thuật toán GA được mô tả bằng ngôn ngữ Matlab như sau end;
if s1<=b
socon=socon+1;
Quan_the(socon,:)=con1;
end;
s2=0;
for l=1:N
s2=s2+A(l)*con2(l);
end;
if s2<=b
socon=socon+1;
Quan_the(socon,:)=con2;
end;
end;
end; %Ket thuc lai ghep
% Chon loc
for i=1:socon
f(i)=0;
for j=1:N
f(i)=f(i)+Quan_the(i,j)*C(j);
end;
end;
for i=1:socon-1
for j=i+1:socon
if f(i) 33 Ví dụ 2.5: Bài toán quân cờ DOMINO Định nghĩa 1: Một quân bài Domino là một bộ (a,b) trong đó được gọi a là số hàng
trên, b là số hàng dưới.
Định nghĩa 2: Phép lật quân được hiểu là một phép biến đổi bộ (a,b) thành bộ (b,a)
Bài toán:
Input: Cho n quân bài Domino (a1,b1),(a2,b2),...(an,bn) xếp thành một hàng ngang. 34 Output: Hãy xác định các phép lật quân để sao cho độ chênh lệnh giữa tổng các số
hàng trên so với tổng các số hàng dưới đạt giá trị nhỏ nhất. .... a1
b1 a2
b2 an-1
bn-1 an
bn Có thể thấy rằng mô hình bài toán trên cũng là bài toán thuộc lớp NP.
Phân tích
+ Kí hiệu một phương án lật quân là một bộ X=(x1,x2,…,xn) trong đó xk=1
tức là lật quân thứ k, xk=0 tức là không lật quân thứ k. Khi đó để tìm phương án lật
quân tối ưu, chúng ta có thể sử dụng thuật toàn duyệt toàn bộ tất cả các phương án
từ đó xác định phương án có độ chênh lệch nhỏ nhất. Kí hiệu hàm mục tiêu Chú ý: =1 ứng với trạng thái không lật quân, = -1 ứng với trạng thái lật quân
Khi đó sử dụng thuật toán duyệt tất cả các dãy nhị phân độ dài n bằng thuật toán
quay lui, ta có thể tìm được lời giải chính xác của bài toán. Tuy nhiên khi n là lớn
thì thuật toán không khả thi vì độ phức tạp của thuật toán là O(n!)
Sau đây chúng ta thiết kế thuật toán GA tìm lời giải xấp xỉ. + Kí hiệu 1 cá thể là X=(x1,x2,…,xn) ứng một phương án lật quân trong đó xk=1 tức là lật quân thứ k, xk=0 tức là không lật quân thứ k. + Sử dụng phương pháp toán tử lai ghép đa điểm hoặc lại ghép mặt nạ + Quá trình chọn lọc luôn sử dụng hàm mục tiêu f(X). function domino=domino(tren,duoi,KK)
clc;
N=length(tren);M=10;%popsize
z=round(rand(M,N));
for i=1:M
for j=1:N
if z(i,j)==0
A(i,j)=tren(j);
B(i,j)=duoi(j);
else
A(i,j)=duoi(j);
B(i,j)=tren(j);
end;
end; Khi đó thuật toán GA được mô tả bằng ngôn ngữ Matlab như sau end;
% thuat toan GA
count=0;k=3;
while count 35 tg=A(7,5);A(7,5)=B(7,5);B(7,5)=tg;
end;
phuong_an_toi_uu=A(1,:) B(1,:)
Gia_tri_toi_uu=f(1) 36 Nhận xét: Qua 2 ví dụ trên chúng ta có thể thấy + Thuật toán GA được thiết kế rất đơn giản, dễ hiểu, các bài toán tương tự thì cấu trúc của các chương trình là như nhau + Thuật toán chỉ sử dụng 1 vòng lặp duy nhất nên độ phức tạp là rất thấp + Các thao tác lai ghép, đột biến, thích nghi đều thao tác trên vector nên khả năng thiết kế thuật toán song song trên máy tính có bộ nhớ vector là rất khả thi + Vì là thuật toán xác suất nên lời giải là gần đúng và với các lần thử nghiệm khác nhau thì kết quả có thể là khác nhau. Kết luận: Nội dung chương 2 đã nghiên cứu một số nguyên tắc thiết kế các thuật toán giải bài toán tối ưu theo tư tưởng Heuristic tìm nghiệm xấp xỉ của các bài toán thuộc lớp NP. Các ví dụ minh họa chứng tỏ tính khả thi của các thuật toán ứng dụng cho các bài toán trong thực tế. 37 CHƯƠNG 3 MÔ HÌNH BÀI TOÁN LẬP LỊCH TRONG BỆNH VIỆN 3.1 Đặt vấn đề Trong thực tế hiện nay thì lớp các bài toán lập lịch là một lớp các bài toán quan trọng vì tính thời sự của nó, có thể kể đến các mô hình: Lập lịch kế hoạch sản xuất trong các xí nghiệp, lập lịch giảng dạy trong các trường học, lập lịch bay cho các sân bay, lập lịch trực cho các nhà máy, bệnh viện… Đặc điểm chung của các bài toán lập lịch là do rất nhiều các ràng buộc từ điều kiện thực tế nên khó có thể tìm được lịch biểu tối ưu, trong khi đó lịch biểu vẫn phải lập và thực hiện do nhu cầu thường ngày của các đơn vị nhà trường và doanh nghiệp. Do đó việc sử dụng các thuật toán xấp xỉ để tìm lịch biểu gần tối ưu luôn luôn là một lựa chọn hợp lý nhiều khi là bắt buộc. Trong các mô hình thực tế hiện nay, mô hình phân công các ca trực tại các phòng khám của các bệnh viện là một mô hình đã và đang diễn ra thường xuyên liên tục. Mô hình này là mô hình chung cho tất cả các bênh viện tuy rằng với mỗi bệnh viện lại có những ràng buộc đặc thù riêng biệt. Vì lý do đó, trong luận văn, chúng tôi sẽ nghiên cứu chi tiết hai mô hình bài toán lập lịch các ca trực tại các bệnh viện. Mô hình được tham khảo từ bệnh viện A tỉnh Thái Nguyên. 3.2 Giới thiệu tổng quan bệnh viện A - Lịch sử phát triển Ngày 4/9/1965 Ty Y tế Bắc Thái thành lập Ban kiến thiết Bệnh viện dã chiến (tiền thân của Bệnh viện A) tại xã Vô Tranh, huyện Phú Lương. Ngày 31/12/1965, Uỷ ban Hành chính tỉnh Bắc Thái chính thức có Quyết định số 657/TCDC về việc tiếp nhận và điều động 73 cán bộ nhân viên do UBHC Khu chuyển giao về và cho thành lập Bệnh viện tỉnh Bắc Thái với quy mô 100 giường bệnh và chỉ tiêu biên chế 62 cán bộ, bao gồm: 02 bác sỹ, 01 dược sỹ đại học, 14 y sỹ, 17 y tá, 02 nữ hộ sinh, 02 dược tá, 01 xét nghiệm viên, 11 hộ lý. 38 Được sự quan tâm của Tỉnh uỷ, UBND tỉnh và Bộ Y tế, Chính Phủ đã quyết định đầu tư cho tỉnh một bệnh viện phụ sản quy mô 200 giường bệnh, diện tích xây dựng 14.000m2 với tổng vốn xây lắp 43 tỷ đồng và trang thiết bị 16 tỷ đồng, trên một phần đất trước đây đã được cấp tại tổ 19, phường Thịnh Đán, T.P Thái Nguyên. Từ năm 2012, số bệnh nhân điều trị nội trú tăng lên nhiều, số giường bệnh phải tăng lên hàng năm: Năm 2012: 380 giường, năm 2013: 420 giường, năm 2014: 470 giường, năm 2015: 510 giường. - Cơ cấu tổ chức Cơ cấu tổ chức các khoa phòng hiện tại: 31 khoa/phòng, gồm: phòng Tổ chức - Hành chính, phòng Tài chính - Kế toán, phòng Kế hoạch - Tổng hợp, phòng Vật tư thiết bị y tế, phòng Điều dưỡng, phòng Công tác xã hội, phòng Quản lý chất lượng, phòng Đào tạo và chỉ đạo tuyến. Các khoa trong Bệnh viện gồm: khoa Khám bệnh, khoa Hồi sức cấp cứu, khoa Nội tổng hợp, khoa Nội Tim mạch - Bảo vệ sức khỏe cán bộ, khoa Ngoại Tổng hợp, Khoa Ngoại Chấn thương, Khoa Sản, Khoa Nhi, Khoa Phẫu thuật - Gây mê hồi sức, Khoa Hồi sức cấp cứu, khoa Mắt, khoa Răng - Hàm - Mặt, khoa Tai - Mũi - Họng, khoa Dược, khoa Truyền nhiễm, Khoa Y học cổ truyền - Vật lý trị liệu, khoa Da liễu, khoa Hỗ trợ sinh sản, khoa Giải phẫu bệnh, khoa Kiểm soát nhiễm khuẩn, khoa Chẩn đoán hình ảnh, khoa Huyết học truyền máu, khoa Sinh hóa - Vi sinh. - Đội ngũ Hiện nay, tổng số cán bộ viên chức trong biên chế của Bệnh viện là 610, bao gồm 138 bác sĩ, trong đó có 16 bác sĩ chuyên khoa cấp II, 37 bác sĩ chuyên khoa cấp I, 5 thạc sĩ; 80 bác sĩ đa khoa, 28 dược sĩ , 351 điều dưỡng, kỹ thuật viên, hộ sinh và 66 đại học. 39 - Quy trình Điều trị, khám bệnh NHẬP KHOA VIỆN PHÍ DỰ TRÙ VÀ HOÀN TRẢ HAO PHÍ THEO KHOA
PHÒNG CHỈ ĐỊNH TẠM
ỨNG CÔNG NỢ CHỈ ĐỊNH CẬN LÂM SÀNG PHẪU THUẬT, THỦ
THUẬT DỰ TRÙ VÀ HOÀN TRẢ HAO PHÍ THEO BỆNH
NHÂN THỰC HIỆN CẬN LÂM SÀNG DƯỢC XUẤT TỪ TRỰC XUẤT KHOA VIỆN PHÍ KẾT THÚC
QUÁ TRÌNH NỘI TRÚ 40 - Quy trình xếp lịch thủ công Ca trực được phân thành 2 ca: Ca ngày từ 7h – 17h cùng ngày; Ca đêm từ 17h – 5h sáng hôm sau. Người trực ca đêm thì hôm sau được nghỉ; Nếu trong ca trực có người nghỉ đột xuất thì sẽ đôn người ở ca trực tiếp theo vào thay thế. Đối với điều dưỡng thì điều dưỡng trưởng của từng khoa phân công lịch trực nộp lên phòng kế hoạch tổng hợp để báo cáo và tổng hợp. Lịch trực Bác sĩ, trực hành chính, trực cận lâm sàng (siêu âm, X quang, xét nghiệm, nội soi), … do phòng kế hoạch tổng hợp sắp xếp. + Tiếp nhận danh sách nhân sự: Họ tên, ngày sinh, giới tính, điện thoại, khoa, chức vụ. + Tiếp nhận danh sách ràng buộc: - Yêu cầu xếp lịch từ các khoa (số lượng Bác sĩ, y tá, điều dưỡng…). - Yêu cầu cấp trực: trực lãnh đạo, ca trực, chức danh và khoa. + Thời gian ca trực: ca ngày, ca đêm. + Xếp lịch trực. + Cập nhật lịch trực. - Hiện trạng Việc xếp lịch trực của Bác sĩ hiện nay được thực hiện bằng tay (thủ công) và được lưu trữ thông tin trên giấy nên không thể tránh khỏi những sai sót như: trùng lặp người trực, mất thông tin, … Cho nên để có được lịch trực chính xác, không xảy ra những sai sót thì chỉ có những người thực hiện công việc xếp lịch là người có kịnh nghiệm và thực hiện công việc này trong thời gian dài, nên việc xây dựng thuật toán lập lịch trên máy tính điện tử và ứng dụng vào công việc nêu trên là cần thiết, nâng cao chất lượng công việc. 3.3 Các mô hình phân công các ca trực Xuất phát từ tìm hiểu thực tế, tại bệnh viện tồn tại 2 mô hình phân công các bác sĩ và y tá trực tại các lịch trực, đó là: 1. Mô hình phân công trực tại các khoa chuyên môn 2. Mô hình phân công trực tại các phòng khám 41 Hai mô hình trên có tính chất chuyên môn cũng như độ phức tạp là hoàn toàn khác nhau. Sau đây chúng ta phân tích chi tiết 2 mô hình và tìm lời giải tối ưu trên từng mô hình 3.3.1 Bài toán phân công trực tại các khoa chuyên môn
Giả sử tại một khoa chuyên môn (Nội, Ngoại, Nhi, Sản,…) qua khảo sát thu được các thông tin như sau: + Tập BS={1,2,3,..,NB} các bác sĩ được mã số thứ tự từ 1 đến NB + Tập YT={1,2,3,..,NY} các y tá được mã số thứ tự từ 1 đến NY + Tập T={1,2,3,….,NT} danh sách các ca trực được mã số thứ tự từ 1 đến NT Các bác sĩ và y tá đều phải tham gia vào các ca trực cấp cứu tại khoa theo các yêu cầu sau đây: + Mọi bác sĩ và y tá đều có nghĩa vụ, trách nhiệm cũng như quyền lợi như nhau + Mỗi bác sĩ và y tá đều có thể đưa ra yêu cầu được nghỉ một số buổi trong lịch tùy theo hoàn cảnh mỗi người. + Tại mọi thời điểm tại phòng trực cấp cứu luôn luôn phải đảm bảo có 1 bác sĩ và 1 y tá trực. Yêu cầu: Hãy lên lịch phân công trực cấp cứu cho các khoa trong bệnh viện sao cho các yêu cầu của mọi người đều thỏa mãn đồng thời số buổi trực của các bác sĩ là tương đương, số buổi trực của các Y tá là tương đương. Phân tích: + Hiển nhiên mô hình các khoa là tương đương đồng thời giữa các khoa là hoạt động độc lập nên chúng ta chỉ cần xây dựng thuật toán phân lịch cho 1 khoa làm đại diện từ đó suy rộng cho toàn bệnh viện. + Do Bác sĩ và Y tá trong 1 khoa là độc lập nên chúng ta cũng chỉ cần phân lịch L1 cho bác sĩ và phân lịch L2 cho Y tá sau đó kết hợp lại chúng ta sẽ được lịch chung toàn khoa. Hiển nhiên 2 bài toán lập lịch L1 và L2 là tương đương. Như vậy chúng ta chỉ cần xét bài toán phân lịch cho các bác sĩ là đủ: 42 Kí hiệu L=(L(1),L(2),….,L(NB)) là lịch trực cần tìm trong đó L(i)=k (k=1..NB) được hiểu là bác sĩ k sẽ trực vào ca trực thứ i trong lịch (i=1..NT) Kí hiệu B=(B(i,j)) là ma trận ràng buộc yêu cầu trong đó B(i,j)=0 được hiểu là Bác sĩ thứ i không sẵn sàng trực tại ca thứ j trong lịch, B(i,j)=1 được hiểu là Bác sĩ thứ i sẵn sàng nhận nhiệm vụ. Hiển nhiên bài toán cần xây dựng phương án trực L thỏa mãn ràng buộc B sao cho số buổi trực của các bác sĩ là xấp xỉ bằng nhau. Để giải quyết bài toán trên, có nhiều phương pháp đưa ra lời giải gần đúng. Trong trường hợp này chúng ta sẽ xây dựng thuật toán gần đúng (theo tư tưởng tham lam) giải bài toán như sau: Tư tưởng: Lần lượt xếp các bác sĩ vào lịch trực (mỗi bác sĩ 1 lần) sao cho thỏa mãn điều kiện. Quá trình lặp đi lặp lại cho đến khi kín lịch thì dừng lại. Hiển nhiên do xếp lần lượt các bác sĩ (mỗi bác sĩ 1 lần) nên số các ca trực của các bác sĩ chỉ chênh lệnh nhiều nhất là 1 buổi, do đó ta đạt được nghiệm theo yêu cầu. Thuật toán Input: + NB, NY, NT + Ma trận B Output: L Bước 1: Xuất phát L=(0,0,…..,0) Chưa xếp bác sĩ nào vào lịch Bước 1: (Bước lặp) k=1; %Xuất phát từ bác sĩ thứ nhất + Tìm ca chưa xếp đầu tiên mà bác sĩ k không bận xếp bác sĩ k vào lịch + Dich chuyển đến ca tiếp theo + k:=k=1; Lấy bác sĩ tiếp sau. Bước 2 Kiểm tra điều kiện dừng (Lịch đầy) Quay lại bước 1 Hiển nhiên độ phức tạp của thuât toán là O(NB.NT) 43 Thuật toán được mô tả chi tiết bằng ngôn ngữ Matlab function lap_lich=Tham_lam_1
clear all;
clc;NT=14;NB=5;
load d:\chuyen_dai_tu\B;
% Phan lich truc cho bac si
while KT(X)>0
k=1;
while and(k<=NB,KT(X)>0)
i=1;ok=0;
while and(i<=NT,ok==0)
if and((X(i)==0),(B(k,i)==1))
X(i)=k;ok=1;
else i=i+1;
end;
end;
k=k+1;
end;
end;
CB=zeros(1,NB);CY=zeros(1,NY);
for k=1:NB
for i=1:NT
if (X(i)==k) CB(k)=CB(k)+1;end;
end;
end;
Lich_truc_bac_si=X
So_ca_truc=CB
function KT=KT(X)%Hàm kiem tra
s=0;
for i=1:length(X)
if X(i)==0
s=s+1;
end;
end;
KT=s; 44 Sau đây là kết quả xếp lịch trực cho các bác sĩ và y tá tại 1 khoa chuyên môn với các số liệu như sau + Số bác sĩ là 5 + Số y tá là 7 + Số ca trực là 14 Ma trận ràng buộc của các bác sĩ và y tá được cho bởi bảng C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12 C13 C14 Bảng 3.1: Ma trận ràng buộc B
(1-Sẵn sàng, 0-Không sẵn sàng) BS 2 BS 3 BS 4 BS 5 BS 1 1
0
0
1
1 1
1
0
1
1 0
1
1
0
1 1
0
1
1
0 1
1
0
1
1 1
1
1
0
1 1
1
1
1
1 0
1
1
1
1 1
0
1
1
0 1
1
0
1
1 1
1
1
0
1 1
1
1
1
1 1
1
1
1
0 0
1
1
1
1 C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12 C13 C14 Bảng 3.2: Ma trận ràng buộc Y
(1-Sẵn sàng, 0-Không sẵn sàng) Yta 2 Yta 3 Yta 4 Yta 5 Yta 6 Yta 1 Yta 7 0
1
1
0
1
1
1 1
0
1
1
0
1
0 1
1
1
1
1
1
1 1
0
1
0
1
1
1 0
1
1
1
1
0
1 1
1
0
1
1
1
1 1
1
1
1
1
1
1 1
1
1
1
1
1
1 1
1
1
1
0
1
0 0
1
1
1
1
1
0 1
0
1
0
1
1
1 1
1
0
1
1
1
1 1
1
1
1
0
1
1 1
1
0
1
1
0
1 Kết quả chạy chương trình được đưa ra trong bảng 3.3 và 3.4 (Lap_lich_tham_lam_1.m) Bảng 3.3: Lịch trực các buổi trong tuần B1
2-1 B2
1-2 B3
4-3 B4 B5 B6 B7 B8
1-1
5-7
3-4 3-6 2-5 B9
4-2 B10 B11 B12 B13 B14
4-7
3-5
5-3 2-4 1-6 Bs1
3 Bs 2
3 (Số hiệu bác sĩ – Số hiệu y tá) Yta1 Yta2
2 Yta3 Yta4
2 Bs4
3 Bs5
2 Bs3
3 Yta6
2 Yta7
2 Bảng 3.4: Số buổi trực đối với các bác sĩ – y tá
Yta5
2 2 2 45 Nhận xét: + Thuật toán cho kết quả là chấp nhận được tức là số buổi trực của các bác sĩ là đồng đều nhau, số buổi trực các Y tá là đồng đều nhau. + Mô hình bài toán là đơn giản, dễ giải quyết trong thực tế vì số ràng buộc là ít + Mô hình áp dụng tốt cho tất cả các khoa tại bệnh viện A Thái Nguyên 3.3.2 Bài toán phân công trực tại các Phòng khám Chúng ta xét bài toán: Giả sử tham khảo thông tin tại phòngTổ chức cán bộ tại bệnh viện A, ta thu được các thông tin sau: Thông tin cơ bản + Bảng 1 gồm NBS các bác sĩ: (Số hiệu, tên, chuyên môn đào tạo) + Bảng 2 gồm NYT các y tá: (Số hiệu, tên, chuyên môn đào tạo) + Bảng 3 gồm NPK các phòng khám (Số hiệu, tên phòng khám) + Bảng 4 gồm NBT các buổi trực (Số hiệu, thời gian, ngày) Trong đó số hiệu được đánh số từ 1,2,…,N Để đảm bảo về chất lượng chuyên môn: Ban giám đốc yêu cầu mỗi Bác sĩ và Y tá chỉ được trực tại một số phòng khám phù hợp với chuyên môn đã được đào tạo (thông tin trong bảng gồm: Số hiệu bác sĩ (Y tá), Số hiệu phòng khám 1- Phù hợp, 0 – Không phù hợp) Để tạo điều kiện thuận lợi, cho phép mỗi Bác sĩ và Y tá được đăng kí các buổi trực mà cá nhân sẵng sàng nhận trực theo lịch phân công trong một số buổi xác định (thông tin trong bảng gồm: Số hiệu bác sĩ (Y tá), Số hiệu ca trực 1- Phù hợp, 0 – Không phù hợp) Yêu cầu hãy xếp lịch trực cho tất cả các Bác sĩ và Y tá tại tất cả các phòng khám trong danh sách tất cả các ca trực để sao cho tại mọi buổi, tất cả các phòng khám phải có đầy đủ 1 Bác sĩ và 1 Y tá trực phù hợp với chuyên môn đào tạo đồng thời số ca trực của các Bác sĩ là tương đương nhau, các Y tá là tương đương nhau. Hiển nhiên bài toán này là phức tạp hơn rất nhiều bài toán trực tại các khoa chuyên môn bởi vì một bác sĩ hoặc y tá có thể trực tại nhiều phòng khám khác nhau tại nhiều ca khác nhau (Bài toán 2 chiều) 46 Xuất phát từ bài toán trên, chúng ta có mô hình toán học chi tiết cho bài toán như sau: Sử dụng các kí hiệu - Tập BS={1,2,…,NBS} số hiệu các Bác sĩ. - Tập YT={1,2,…,NTY} số hiệu các Y tá. - Tập PK={1,2,…,NPK} số hiệu các phòng khám. - Tập BT={1,2,…,NBT} số hiệu các buổi trong lịch toàn lịch trực. - Mảng PBS(s,p) biểu diễn sự phù hợp chuyên môn giữa các Bác sĩ và phòng khám trong đó: PBS(s,p)=1 chuyên môn Bác sĩ số hiệu s phù hợp với phòng khám p, PBS(s,p)=0 – Không phù hợp. - Mảng PYT(s,p) biểu diễn sự phù hợp chuyên môn giữa các Y tá và phòng khám trong đó: PYT(s,p)=1 chuyên môn Y tá số hiệu s phù hợp với phòng khám p, PYT(s,p)=0 – Không phù hợp. - Mảng trạng thái MBS(s,t) trạng thái sẵn sàng nhận trực của Bác sĩ có số hiệu s trong ca trực thứ t trong đó MBS(s,t)=1 là sẵng sàng, MBS(s,t)=0 là không sẵn sàng - Mảng trạng thái MYT(s,t) trạng thái sẵn sàng nhận trực của Y tá có số hiệu s trong ca trực thứ t trong đó MYT(s,t)=1 là sẵng sàng, MYT(s,t)=0 là không sẵn sàng Các biến số cần xác định - Các biến XBS(p,t)=k – bác sĩ số hiệu k được xếp vào phòng khám p trong buổi trực t. - Các biến XYT(p,t)=k – y tá số hiệu k được xếp vào phòng khám p trong buổi trực t. - Các biến CBS(s) - Ghi lại tổng số buổi trực của bác sĩ s trong toàn lịch phân công trực tại các phòng khám. - Các biến CYT(s) - Ghi lại tổng số buổi trực của y tá s trong toàn lịch phân công trực tại các phòng khám. Các điều kiện ràng buộc: R1: Tại một thời điểm t, 1 Bác sĩ chỉ được trực nhiều nhất là 1 phòng khám. R2: Tại một thời điểm t, 1 Y tá chỉ được trực nhiều nhất là 1 phòng khám. 47 R3: Chỉ xếp lịch trực cho các Bác sĩ sẵn sàng trong buổi trực. R4: Chỉ xếp lịch trực cho các Y tá sẵn sàng trong buổi trực. R5: Các Bác sĩ và Y tá chỉ được phép trực tại các phòng khám phù hợp về chuyên môn. R6: Tại mọi thời điểm, các phòng khám đều phải có đầy đủ 1 Bác sĩ và 1 Y tá trực Yêu cầu: Hãy xây dựng bảng phân công trực tại các phòng khám cho tất cả các Bác sĩ và Y tá trong bệnh viện thỏa mãn tất cả các ràng buộc R1,…,R6 sao cho tổng số các buổi trực của các Bác sĩ được phân công là tương đương nhau, số các buổi trực của các Y tá được phân công là tương đương nhau. Nhận xét: Bài toán trên là một dạng bài toán quy hoạch rời rạc. Để nhận được lời giải đúng là rất khó thực hiện và trong nhiều trường hợp chúng ta không thể xác định được lịch biểu tối ưu (Phụ thuộc vào 2 ma trận sẵn sàng là TBS và TYT). Sau đây chúng ta sẽ nghiên cứu hai phương án thiết kế giải bài toán Phương án 1: Thuật toán tham lam Phân tích: + Do Bác sĩ và Y tá trong 1 bênh viện là độc lập nên chúng ta cũng chỉ cần phân lịch L1 cho bác sĩ và phân lịch L2 cho Y tá sau đó kết hợp lại chúng ta sẽ được lịch chung toàn khoa. Hiển nhiên 2 bài toán lập lịch L1 và L2 là tương đương. Như vậy chúng ta chỉ cần xét bài toán phân lịch cho các bác sĩ là đủ: + Kí hiệu L1=(L1(i,j)) là lịch trực cần tìm trong đó L1(i,j)=k (k=1..NB) được hiểu là bác sĩ k sẽ trực tại phòng khám i (i=1..NP) trong ca trực thứ i trong lịch (i=1..NT) + Kí hiệu BT=(BT(i,j)) là ma trận ràng buộc yêu cầu trong đó B(i,j)=0 được hiểu là Bác sĩ thứ i không sẵn sàng trực tại ca thứ j trong lịch, B(i,j)=1 được hiểu là Bác sĩ thứ i sẵn sàng nhận nhiệm vụ. + Kí hiệu BP=(BP(i,j)) là ma trận ràng buộc yêu cầu trong đó B(i,j)=0 được hiểu là Bác sĩ thứ i không đáp ứng chuyên môn tại phòng khám thứ j, B(i,j)=1 được hiểu là Bác sĩ thứ i đáp ứng chuyên môn 48 Hiển nhiên bài toán cần xây dựng phương án trực L1 thỏa mãn 2 ràng buộc BT và BP sao cho số buổi trực của các bác sĩ là xấp xỉ bằng nhau. Chúng ta sẽ xây dựng thuật toán gần đúng (theo tư tưởng tham lam) giải bài toán như sau: Tư tưởng: Bước 1: Khởi động ma trận L1 là rỗng (Chưa xếp lịch) Bước lặp: Lần lượt xét các bác sĩ k= 1..NB + Xét 1 ô L1(i,j) còn trống (Chưa xếp bác sĩ) + Nếu Bác sĩ k thỏa mãn yêu cầu tại ô (i,j): BT(k,j)=1; BP(i,k)=1 thì xếp bác sĩ k vào ô (i,j) + Tăng k=k+1; Quay lại bước lặp. Quá trình dừng lại khi tất cả các ô L1(i,j) đã đầy Hiển nhiên do xếp lần lượt các bác sĩ theo dạng quay vòng nên số các ca trực là xấp xỉ bằng nhau. Quá trình xếp các y tá là hoàn toàn tương tự Thuật toán Input: + NB, NY, NT + Ma trận B Output: L Bước 1: Xuất phát L=(0,0,…..,0) Chưa xếp bác sĩ nào vào lịch Bước 1: (Bước lặp) k=1; %Xuất phát từ bác sĩ thứ nhất + Tìm ca chưa xếp đầu tiên mà bác sĩ k không bận xếp bác sĩ k vào lịch + Dich chuyển đến ca tiếp theo + k:=k=1; Lấy bác sĩ tiếp sau. Bước 2 Kiểm tra điều kiện dừng (Lịch đầy) Quay lại bước 1 Hiển nhiên độ phức tạp của thuật toán là O(NB.NT.NP) Thuật toán được mô tả chi tiết bằng ngôn ngữ Matlab 49 function lap_lich=Tham_lam_2
clc;NT=14;NB=10;NY=14;NP=7;BT=ones(NB,NT);BP=ones(NB,NP);YT=ones(N
Y,NT);YP=ones(NY,NP);
load d:\chuyen_dai_tu\BT;
load d:\chuyen_dai_tu\BP;
load d:\chuyen_dai_tu\YT;
load d:\chuyen_dai_tu\YT;
X=zeros(NP,NT);
Z=zeros(NP,NT);
count=0;
while KT(X)>0
k=1;
while k<=NB
i=0;
while i 50 j=j+1;
if
and((Z(i,j)==0),and((YP(k,i)==1),and((YT(k,j)==1),(KT1(Z(:,j),k)==0))))
Z(i,j)=k;ok=1;
end;
end;
end;
k=k+1;
end;
end;
CY=zeros(1,NY);
for k=1:NY
for i=1:NP
for j=1:NT
if (Z(i,j)==k) CY(k)=CY(k)+1;end;
end;
end;
end;
Lich_truc_bac_si=X
So_ca_truc=CB
Lich_truc_Y_ta=Z
So_ca_truc=CY
function KT=KT(X)%Hàm kiem tra
NP=7;NT=14;
s=0;
for i=1:NP
for j=1:NT
if X(i,j)==0
s=s+1;
end;
end;
end;
KT=s;
function KT1=KT1(Z,k)%Hàm kiem tra
NP=7;
s=0;
for i=1:NP
if (Z(i)==k)
s=s+1;
end;
end;
KT1=s; 51 Bộ số liệu Test
+ Số các bác sĩ tham gia trực NBS=10.
+ Số các y tá tham gia trực NYT=14.
+ Số các phòng khám NP=7.
+ Số các buổi trong lịch: NT=14. Phòng 1 Phòng 2 Phòng 3 Phòng 4 Phòng 5 Phòng 6 Phòng 7 Bảng 3.5: Bảng các bác sĩ phù hợp chuyên môn với phòng khám
(1-Phù hợp, 0-Không phù hợp) Bs 2 Bs 3 Bs 4 Bs 5 Bs 6 Bs 7 Bs 8 Bs 9 Bs 10 Bs 1 0
1
1
0
1
0
1
0
0
1 1
0
1
1
0
1
0
1
1
1 1
1
0
1
1
1
1
0
1
1 0
1
0
1
1
0
1
1
1
0 1
1
1
1
1
1
1
1
1
1 1
1
1
0
0
1
1
1
1
1 1
0
1
1
1
1
0
1
1
1 Phòng 1 Phòng 2 Phòng 3 Phòng 4 Phòng 5 Phòng 6 Phòng 7 Bảng 3.6: Bảng các y tá phù hợp chuyên môn với phòng khám
(1-Phù hợp, 0-Không phù hợp) Yta 2 Yta 3 Yta 4 Yta 5 Yta 6 Yta 7 Yta 8 Yta 9 Yta 10 Yta 11 Yta 12 Yta 13 Yta 14 Yta 1 0
1
1
0
1
0
1
0
0
1
1
1
1
1 1
0
1
1
1
1
0
1
1
1
0
1
1
1 1
1
0
1
1
1
1
1
1
1
1
1
1
1 0
1
0
1
0
0
1
1
1
0
1
1
1
1 1
1
1
1
1
1
1
1
1
1
1
0
1
1 1
1
1
0
0
1
1
1
1
1
1
1
0
1 1
0
1
1
1
1
0
1
1
1
1
1
1
1 52 B1 B2 B3 B4 B5 B6 B7 B8 B9 B10 B11 B12 B13 B14 Bảng 3.7: Bảng các Bác sĩ sẵn sàng nhận buổi trực
(1-Sẵn sàng, 0-Không sẵn sàng) Bs 2 Bs 3 Bs 4 Bs 5 Bs 6 Bs 7 Bs 8 Bs 9 Bs 1 Bs
10 1
1
1
1
1
0
1
1
1
1 1
2
1
1
1
1
1
1
1
1 0
1
0
1
1
1
0
1
1
1 1
1
1
1
0
1
1
1
1
0 1
0
1
1
1
1
1
1
1
1 1
1
1
1
1
1
1
1
0
1 1
1
1
1
0
1
1
1
1
1 1
1
1
1
1
1
1
1
1
1 0
1
1
1
1
1
1
1
1
1 1
1
0
1
1
1
1
0
1
1 1
1
1
0
1
1
1
1
1
1 1
1
1
1
1
1
1
1
1
1 1
1
1
1
1
1
1
1
1
1 1
1
1
1
1
1
1
1
1
1 B1 B2 B3 B4 B5 B6 B7 B8 B9 B10 B11 B12 B13 B14 Bảng 3.8: Bảng các Y tá sẵn sàng nhận buổi trực
(1-Sẵn sàng, 0-Không sẵn sàng) Yta 2 Yta 3 Yta 4 Yta 5 Yta 6 Yta 7 Yta 8 Yta 9 Yta10 Yta11 Yta12 Yta13 Yta14 Yta 1 0
1
1
1
1
0
1
1
1
1
1
1
1
1 1
1
0
1
1
1
1
1
1
1
1
0
1
1 1
0
1
1
1
1
0
1
1
1
1
1
1
1 1
1
1
1
0
1
1
1
1
0
1
1
1
1 1
1
1
1
1
1
1
1
1
1
0
1
1
1 1
0
1
1
1
1
1
1
0
1
1
1
1
1 0
1
1
1
0
1
1
1
1
1
1
1
0
1 1
1
1
1
1
1
1
1
1
1
1
1
1
1 1
1
0
1
1
1
1
1
1
1
1
1
1
1 1
1
1
1
1
1
1
0
1
1
1
1
1
1 1
1
1
0
1
1
1
1
1
1
1
1
1
1 1
1
1
1
1
1
1
1
1
1
1
1
1
1 1
1
1
0
1
1
1
1
1
1
1
1
1
1 1
1
1
1
1
1
1
1
1
1
1
1
1
1 53 Kết quả chạy chương trình trên bộ số liệu thực tế được đưa ra trong các bảng 3.9 và 3.10 và 3.11 (Lap_lich_tham_lam_2) B6 B8 2-3
1-12 6-6
7-9
8-11
1-5 B2
B1
3-5
2-2
P1
P2
4-1
1-4
P3 9-11 10-2
7-4
8-7
P4
6-6
P5
3-3
1-7
P6 7-12
5-13
4-5
P7 B7
B3 B4
7-7 10-10 2-11 3-12 5-13 7-14 10-2
5-3
4-4
8-8
9-9
6-6
1-1
6-8
1-6
2-4
5-7
4-13
8-8
2-9
9-2
3-10 10-3
10-5 3-3
6-6
2-9
9-1
10-5
4-4
4-9 B9 B10 B11 B12 B13 B14
7-10
3-5
5-7
8-1
4-13 6-14
8-8
5-14
4-1
9-10 1-11 10-13 2-12
5-4
2-2
4-9
7-8
8-14 9-13 10-2
6-6
9-3
8-2
1-1
9-11 10-3 1-14 9-9
4-5
5-12
1-1
3-3
6-4 9-7
3-11
6-14
8-8 Bảng 3.9: Lịch trực tại các phòng trong các buổi
(Số hiệu bác sĩ – Số hiệu y tá)
B5 Bs1
11 Bs 2
9 Bs3
10 Bs4
10 Bs5
10 Bs6 Bs7
8
10 Bs8
10 Bs9
10 Bs10
10 Bảng 3.10: Số buổi trực đối với các bác sĩ Bảng 3.11: Số buổi trực đối với các y tá
YT1 YT2 YT3 YT4 YT5 YT6 YT7 YT8 YT9 YT10 YT11 YT12 YT13 YT14
7
7 7 7 7 8 7 6 7 7 7 6 8 7 Nhận xét: Kết quả nhận được là kết quả gần đúng. Điều kiện tối ưu chưa đảm bảo tốt vì thuật toán không xét đến hàm mục tiêu (Chỉ xét theo thứ tự lần lượt các bác sĩ và các y tá để xếp vào lịch mà không đánh giá hàm mục tiêu) Phương án 2: Thuật toán GA
Xây dựng cấu trúc dữ liệu Lựa chọn cấu trúc cá thể: Kí hiệu 1 phương án xếp lịch là cặp 2 ma trận [ZBS(NPK,NBT) ;ZYT(NPK,NBT] trong đó - ZBS(p,t)=k : Phân công bác sĩ có số hiệu k trực phòng khám p, tại buổi t, - ZYT(p,t)=k : Phân công Y tá có số hiệu k trực phòng khám p, tại buổi t. Như vậy tập hợp các phương án chính là tập hợp các cặp ma trận các phần tử là các số nguyên dương có giá trị là các số hiệu của các Bác sĩ hoặc của các Y tá. Điều kiện phân công hợp lệ là trên một cột của các ma trận ZBS và ZYT không có 54 các phần tử có giá trị trùng nhau tức là tại 1 thời điểm mỗi bác sĩ hoặc y tá chỉ được trực tại 1 phòng khám. Hàm CBS(k) có giá trị bằng tổng tất cả các phần tử trong ma trận phương án ZBS thỏa mãn điều kiện ZBS(p,t)=k, với mọi Như vậy CBS(k) chính là tổng số buổi trực của bác sĩ k trong toàn lịch trực. Hàm CYT(k) có giá trị bằng tổng tất cả các phần tử trong ma trận phương án ZYT thỏa mãn điều kiện XYT(p,t)=k, với mọi Như vậy CYT(k) chính là tổng số buổi trực của y tá s trong toàn lịch trực. Các ràng buộc của bài toán + R1: Tại một thời điểm t, 1 bác sĩ chỉ được trực nhiều nhất là 1 phòng khám sẽ tương đương với điều kiện: Trên một cột của ma trận ZBS không tồn tại 2 phần tử bằng nhau. Xây dựng hàm R1(ZBS) để kiểm tra điều kiện R1 trong phương án ZBS. + R2: Tại một thời điểm t, 1 y tá chỉ được trực nhiều nhất là 1 phòng khám sẽ tương đương với điều kiện: Trên một cột của ma trận ZYT không tồn tại 2 phần tử bằng nhau. Xây dựng hàm R2(ZYT) để kiểm tra điều kiện R2 trong phương án XY. + R3: Chỉ xếp lịch trực cho các bác sĩ sẵn sàng trong buổi trực tương ứng sẽ tương đương với điều kiện: Nếu ZBS(p,t)=s thì MBS(s,t)=1 hay MBS(ZBS(p,t),t)=1. + R4: Chỉ xếp lịch trực cho các y tá sẵn sàng trong buổi trực tương ứng sẽ tương đương với điều kiện: Nếu ZYT(p,t)=s thì MYT(s,t)=1 hay MYT(ZYT(p,t),t)=1. + R5: Các bác sĩ và Y tá chỉ được phép trực tại các phòng khám phù hợp về chuyên môn đào tạo sẽ tương đương với điều kiện: Nếu ZBS(p,t)=s thì PK(s,p)=1 hay PK(ZBS(p,t),p)=1. Nếu ZYT(p,t)=s thì PK(s,p)=1 hay PK(XY(p,t),p)=1. Kết hợp 3 điều kiện R3,R4 và R5, điều kiện thỏa mãn đồng thời chính là 55 BT(XB(p,t),t)× PBS(XB(p,t),p) × BT(XY(p,t),t)× PYT(X(p,t),p)=1; với mọi Xây dựng hàm R345(X) là hàm kiểm tra điều kiện H3, H4 và H3 trong phương án Z =[ZBS;ZYT]. + R6: Tại mọi thời điểm, các phòng khám đều phải có bác sĩ trực và y tá sẽ tương đương với tất cả các phần tử trong cặp ma trận Z=[ZBS;ZYT] đều dương. ZBS(p,t)>0; ZYT(p,t)>0; với mọi Chúng ta kí hiệu hàm R6(X) để kiểm tra điều kiện H6. Hàm mục tiêu của bài toán: Vì tổng số các buổi trực của các bác sĩ và y tá luôn bằng NP×NT (Giả thiết tất cả các phòng khám đều phải xếp kín tất cả các buổi), do đó sử dụng bất đẳng thức Bunhiakovski: “Tổng các phần tử là không đổi thì tích sẽ đạt giá trị lớn nhất khi tất cả các phần tử bằng nhau”, ta suy ra để đảm bảo yêu cầu của bài toán: số các buổi trực của các bác sĩ là xấp xỉ bằng nhau sẽ tương đương với: Hãy xác định phương án Z=[ZBS;ZYT] thỏa mãn tất cả các ràng buộc để sao cho 2 hàm mục tiêu: Như vậy bài toán lập trực được đưa về bài toán: Hãy xác định phương án X thỏa mãn cás sĩc ràng buộc mô tả bởi các hàm ràng buộc R1(X), R2(X), R345(X), R6(X) để sao cho hàm mục tiêu Thuật toán GA
B1: Khởi tạo quần thể ban đầu 1.1 Sử dụng phương pháp khởi tạo ngẫu nhiên N cặp ma trận Z=[ZBS;ZYT] kích thước NBS×NYT các phần tử trong khoảng (0,NBS+1);(0,NYT+1), trên các cột của ma trận thỏa mãn các điều kiện R1 và R345. 1.2 Xác định độ thích nghi của các các cá thể trong quần thể xuất phát. 56 1.3 Xác định giá trị hàm mục tiêu ban đầu B2: Quá trình lai ghép + Để đảm bảo ràng các rành buộc, chúng ta dụng phương pháp lai ghép 2 điểm cắt theo chiều thời gian t giữa cá thể thứ i (Bố) với cá thể thứ j (i thu được quần thể gồm N+(N-1)×(N-2) cá thể. + Kiểm tra độ thích nghi của tất cả các cá thể, ta thu được M các thể thỏa mãn. B3: Quá trình chọn lọc Tính giá trị hàm F(X) với mọi các thể trong quần thể gồm M cá thể, từ đó ta lựa chọn lấy N cá thể tốt nhất để sử dụng cho thế hệ kế tiếp B4: Đột biến: Sử dụng kỹ thuật đột biến m các thể bất kì bằng cách thay đổi ngẫu nhiên 1 giá trị trong ma trận Z phù hợp với bài toán. ( - Xác suất đột biến). B4: Quay lại B2 với N cá thể trong thế hệ tiếp sau. Điều kiện dừng lặp của thuật toán là số lần lặp đặt tới số lần định hạn trước. Một số kết quả tính toán Với thuật toán trên, chúng tôi đã thiết kế hoàn chỉnh chương trình trên mô Kết quả chạy chương trình với dữ liệu giả định trường Matlab version 7.0 (Chi tiết thuật toán được đưa ra trong phần phụ lục). Bộ số liệu Test
+ Số các bác sĩ tham gia trực NBS=15. + Số các y tá tham gia trực NYT=10. + Số các phòng khám NP=7. + Số các buổi trong lịch: NT=14. 57 Phòng 1 Phòng 2 Phòng 3 Phòng 4 Phòng 5 Phòng 6 Phòng 7 Bảng 3.12: Bảng các bác sĩ phù hợp chuyên môn với phòng khám
(1-Phù hợp, 0-Không phù hợp) Bs 2 Bs 3 Bs 4 Bs 5 Bs 6 Bs 7 Bs 8 Bs 9 Bs 10 Bs 11 Bs 12 Bs 13 Bs 14 Bs 15 Bs 1 0
0
1
1
1
1
1
1
0
0
1
1
1
1
1 1
1
0
0
1
1
1
1
1
1
0
0
1
1
1 0
0
1
1
1
1
0
0
1
1
1
1
1
1
0 1
1
1
1
0
0
1
1
1
1
1
1
0
0
1 1
1
0
0
1
1
1
1
0
0
1
1
1
1
1 1
1
1
1
0
0
1
1
1
1
0
0
1
1
1 1
1
1
1
1
1
0
0
1
1
1
1
0
0
0 Phòng 1 Phòng 2 Phòng 3 Phòng 4 Phòng 5 Phòng 6 Phòng 7 Bảng 3.13: Bảng các y tá phù hợp chuyên môn với phòng khám
(1-Phù hợp, 0-Không phù hợp) Yta 2 Yta 3 Yta 4 Yta 5 Yta 6 Yta 7 Yta 8 Yta 9 Yta 10 Yta 1 1
0
1
0
1
1
1
1
1
1 0
1
0
1
1
1
1
1
1
1 1
1
0
1
1
1
0
0
1
1 1
1
1
1
1
0
1
1
0
1 1
0
1
1
0
1
0
1
0
1 0
1
1
1
0
1
1
0
1
1 1
1
1
0
1
0
1
1
1
1 58 B1 B2 B3 B4 B5 B6 B7 B8 B9 B10 B11 B12 B13 B14 Bảng 3.14: Bảng các Bác sĩ sẵn sàng nhận buổi trực
(1-Sẵn sàng, 0-Không sẵn sàng) Bs 2 Bs 3 Bs 4 Bs 5 Bs 6 Bs 7 Bs 8 Bs 9 Bs 10 Bs 11 Bs 12 Bs 13 Bs 14 Bs 15 Bs 1 1
1
1
1
1
1
0
1
1
1
1
1
1
1
1 1
0
1
1
1
1
1
1
0
1
1
1
1
1
1 0
1
1
1
1
1
1
1
1
1
1
1
1
1
1 1
1
0
1
1
1
1
1
1
1
0
1
1
1
1 1
1
1
0
1
1
1
0
1
1
1
0
1
1
1 1
1
1
1
0
1
1
1
1
1
1
1
0
1
1 1
0
1
1
1
0
1
1
1
0
1
1
1
0
1 1
1
0
1
1
1
1
1
1
1
1
1
1
1
0 1
1
1
1
1
1
1
1
1
1
1
1
1
1
0 0
1
1
1
1
1
1
1
0
1
1
1
1
0
1 1
1
1
1
0
1
1
1
1
1
1
1
0
1
1 1
1
1
1
1
1
0
1
1
1
1
0
1
1
1 1
1
1
0
1
1
1
0
1
1
0
1
1
1
1 1
1
1
1
1
0
1
1
1
0
1
1
1
1
1 B1 B2 B3 B4 B5 B6 B7 B8 B9 B10 B11 B12 B13 B14 Bảng 3.15: Bảng các Y tá sẵn sàng nhận buổi trực
(1-Sẵn sàng, 0-Không sẵn sàng) Yta 2 Yta 3 Yta 4 Yta 5 Yta 6 Yta 7 Yta 8 Yta 9 Yta10 Yta 1 1
1
0
1
1
1
1
1
1
1 1
1
1
1
1
1
1
1
1
1 0
1
1
1
1
1
1
1
1
1 1
1
1
1
1
1
1
1
1
0 1
1
1
1
1
1
1
1
1
1 1
1
1
1
1
1
1
1
1
1 1
0
1
1
1
1
1
1
1
1 1
1
1
1
1
0
1
1
0
1 1
1
1
1
1
1
1
1
1
1 1
1
1
1
1
1
1
1
0
1 1
1
1
1
1
1
1
0
1
1 1
1
1
1
1
1
0
1
1
1 1
1
1
0
1
1
1
1
1
1 1
1
1
1
0
1
1
1
1
1 59 Kết quả chạy chương trình được đưa ra trong các bảng 3.16; 3.17 và 3.18
(Lap_lich_test_2.m) B5 B8 B9 B6 B3 B4 B1 B2 B10 B11 B12 B13 B14 7-5 8-3 Bảng 3.16: Lịch trực
(Số hiệu bác sĩ – Số hiệu y tá)
B7 8-8 7-6 6-7 14-6 11-9 13-1 12-6 13-6 12-3 7-8 5-7 5-9 15-7 14-9 P2 9-5 6-7 10-8 5-5 14-4 10-5 15-2 2-7 13-6 2-4 9-6 2-8 10-4 3-3 7-8 P3 15-3 15-7 4-7 8-8 4-10 2-3 15-2 1-5 9-5 2-3 12-2 P4 11-9 5-9 13-6 10-4 13-4 9-1 3-1 6-6 13-10 11-1 3-10 5-9 13-9 11-4 P5 12-10 1-1 11-4 12-1 1-6 6-10 2-6 14-10 12-8 8-4 12-6 14-8 14-3 7-4 P6 7-6 2-2 10-10 15-7 9-9 1-2 8-4 4-9 4-6 7-10 3-2 1-7 4-7 4-3 P7 3-1 9-3 5-2 9-1 10-5 6-10 11-9 11-8 6-3 5-5 5-2 6-2 3-1 7 7 7 7 6 7 6 7 7 6 6 6 6 7 YT1
9 YT2
10 YT3
10 YT4
10 YT5
9 YT6
11 YT7
10 YT8
10 YT9
10 YT10
9 Bảng 3.18: Số buổi trực đối với các y tá Nhận xét + Do thuật toán là thuật toán xác suất nên mỗi lần sẽ thu được các kết quả là khác nhau. Do đó trong thực tế nên chạy nhiều lần để chọn kết quả đồng đều nhất về các ca trực + Thông qua các kết quả thực nghiệm kiểm tra thuật toán GA tìm phương án xếp lịch trực tại các phòng khám của bệnh viện A tỉnh Thái Nguyên, qua bộ số liệu thực tế giả định, chúng ta có thể thấy rằng thuật toán GA đề xuất là khả thi, kết quả thu được tốt hơn thuật toán tham lam vì đã xét cực đại hàm mục tiêu. Các kết quả nhận được là chấp nhận được trong thực tế. Thuật toán có thể áp dụng tốt với bài toán lập lịch trực tại mô hình tất cả các bệnh viện với các ràng buộc trong thực tế phát sinh. 60 Nội dung chính của luận văn là nghiên một số thuật toán xấp xỉ và áp dụng vào một số các bài toán thuộc lớp NP. Các kết quả chính của luận văn bao gồm 1. Trình bày các kiến thức cơ bản về lý thuyết về độ phức tạp của thuật toán. Nguyên tắc phân lớp các bài toán theo độ phức tạp. 2. Nghiên cứu các khái niệm cơ bản về thuật toán xấp xỉ, Một số thuật toán xấp xỉ kinh điển như thuật toán quy hoạch động, thuật toán tham lam, thuật toán GA. 3. Trình bày lời giải xấp xỉ của một số bài toán thuộc lớp NP kinh điển như bài toán Knapsack, bài toán đổi tiền, bài toán Domino. Các thuật toán đã được cài đạt chính xác bằng các ngôn ngữ C++ hoặc Matlab 4. Nghiên cứu mô hình 2 bài toán lập lịch tại bệnh viên A Thái Nguyên: đó là mô hình lập lịch trực các khoa chuyên môn (Bài toán 1 chiều) và mô hình lập lịch trực tại các phòng khám (Bài toán 2 chiều). 5. Xây dựng các thuật toán tham lam và GA để tìm nghiệm xấp xỉ của 2 bài toán. Thử nghiệm các thuật toán trên các ví dụ cụ thể trong môi trường Matlab để khẳng định tính chính xác của các thuật toán. Thông qua các kết quả thực nghiệm kiểm tra thuật toán GA tìm phương án xếp lịch trực tại các phòng khám của bệnh viện A tỉnh Thái Nguyên, qua bộ số liệu thực tế giả định, chúng ta có thể thấy rằng thuật toán GA đề xuất là khả thi, kết quả thu được tốt hơn thuật toán tham lam vì đã xét cực đại hàm mục tiêu. Các kết quả nhận được là chấp nhận được trong thực tế. Hướng phát triển tiếp sau của luận văn là cải tiến các thuật toán lập lịch ứng dụng trên các mô hình phức tạp hơn trong thực tế. 61 TÀI LIỆU THAM KHẢO Tài liệu tiếng Việt [1] Nguyễn Thanh Bình (2007), Giáo trình - bài giảng thuật toán nâng cao, trường Đại học Bách khoa Đại học Đà Nẵng. [2] Hồ Sĩ Đàm (2009), Tài liệu giáo khoa chuyên tin, Nxb Giáo dục. [3] Nguyễn Hữu Điển (2002), Một số vấn đề về thuật toán, Nxb Giáo dục. [4] Nguyễn Xuân Huy (2011), Sáng tạo trong thuật toán và lập trình, Tập 1, 2, 3 Nxb Thông tin và truyền thông. [5] Vũ Vinh Quang, Trương Hà Hải (2007), Lý thuyết thuật toán, Bài giảng trường ĐH CNTT&TT. Tài liệu tiếng Anh [6] Introduction to Algorithms_ 2nd Ed - Thomas H. Cormen, Hanover, 2001. [7] Garey Michael R-David S Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, 2007 [8] Silvano Martello, Silvano; Paolo Toth , Knapsack Problems: Algorithms and Computer Implementations, John Wiley & Sons, 2009 [9] David, A.Coley: An Instroduction to Genetic Algorithm. [10] Eiben, E. et al (1994), Genetic algorithms with multi-parent recombination. PPSN III: Proceedings of the International Comference on Evolutionary Computation 78-87. 62 PHẦN PHỤ LỤC while (k 63 end;
end;
for s=1:NB
CB(s)=0;
for p=1:NP
for t=1:NT
if (XB(p,t,1)==s)
CB(s)=CB(s)+1;
end;
end;
end;
end;
for s=1:NY
CY(s)=0;
for p=1:NP
for t=1:NT
if (XY(p,t,1)==s)
CY(s)=CY(s)+1;
end;
end;
end;
end;
Lich_truc_Bac_si=XB(:,:,1)
So_ca_truc_cac_bac_si=CB
Lich_truc_Y_ta_si=XY(:,:,1)
So_ca_truc_cac_Y_ta=CY
%%%%%% cac ham
function Y=Y(TS,PS,NP,NT,NB)
for t=1:NT
B=ones(NB,1);
p=1;
while (p<=NP)
a=round(NB*rand(1))+1;
if and(a>0,a<=NB)
if and(and(B(a)==1,TS(a,t)==1),PS(a,p)==1)
B(a)=0;A(p,t)=a;
p=p+1;
end;
end;
end;
end;
Y=A;
function FH23=FH23(Y,TS,PS,NP,NT)
count=0;
p=0;a=1;
while and(p 64 T=1;
for s=1:NB
CB(s)=0;
for p=1:NP
for t=1:NT
if (Y(p,t)==s)
CB(s)=CB(s)+1;
end;
end;
end;
T=T*CB(s);
end;
FB=T;
function FY=FY(Y,NP,NT,NB)
T=1;
for s=1:NB
CY(s)=0;
for p=1:NP
for t=1:NT
if (Y(p,t)==s)
CY(s)=CY(s)+1;
end;
end;
end;
T=T*CY(s);
end;
FY=T; 65BỆNH NHÂN PHÒNG KHÁM
NỘI
TRÚ
7-14
6-10
8-10 10-8 3-11 2-12
1-6
3-10 5-12 6-13
P1
9-2
Bảng 3.17: Số buổi trực đối với các bác sĩ
Bs1 Bs2 Bs3 Bs4 Bs5 Bs6 Bs7 Bs8 Bs9 Bs10 Bs11 Bs12 Bs13 Bs14 Bs15
6
KẾT LUẬN
1. Bài toán lập lịch
function lap_lich=lap_lich_2020
clear all;
clc;
popsize=30;
NP=5;NT=7;NB=10;NY=7;
TS=ones(NB,NT);
PS=ones(NB,NP);
TY=ones(NY,NT);
PY=ones(NY,NP);
PS(1,1)=0;
PS(2,1)=0;
PS(3,2)=0;
PS(4,2)=0;
PS(5,3)=0;
PS(6,3)=0;
PS(7,4)=0;
PS(8,4)=0;
PS(9,5)=0;
PS(10,5)=0;
PY(1,5)=0;
PY(2,4)=0;
PY(3,2)=0;
PY(4,5)=0;
PY(5,4)=0;
PY(6,1)=0;
PY(7,3)=0;
PY(8,1)=0;
TS(1,1)=0;
TS(2,5)=0;
TS(3,2)=0;
TS(4,3)=0;
TS(5,4)=0;
TS(6,5)=0;
TS(7,7)=0;
TS(8,3)=0;
TS(9,2)=0;
TS(10,5)=0;
TY(1,2)=0;
TY(2,5)=0;
TY(3,4)=0;
TY(4,1)=0;
TY(5,3)=0;
TY(6,7)=0;
TY(7,5)=0;
TY(8,6)=0;
%TY(9,2)=0;
%TY(10,5)=0;
% Khoi tao Quan the ban dau
k=0;
