Thuật toán xấp xỉ ứng dụng vào một số bài toán lớp NP

ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

NGUYỄN HỮU CHUYÊN

THUẬT TOÁN XẤP XỈ

ỨNG DỤNG VÀO MỘT SỐ BÀI TOÁN LỚP NP

LUẬN VĂN THẠC SỸ KHOA HỌC MÁY TÍNH

Thái Nguyên – 2020

ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

NGUYỄN HỮU CHUYÊN

THUẬT TOÁN XẤP XỈ

ỨNG DỤNG VÀO MỘT SỐ BÀI TOÁN LỚP NP

LUẬN VĂN THẠC SỸ KHOA HỌC MÁY TÍNH

Chuyên ngành: KHOA HỌC MÁY TÍNH

Mã số: 84 8 01 01

Người hướng dẫn: TS. Vũ Vinh Quang

Thái Nguyên - 2020

i

LỜI CẢM ƠN

Để hoàn thành luận văn này trước tiên, em xin được gửi lời cảm ơn sâu

sắc tới thầy giáo hướng dẫn TS. Vũ Vinh Quang đã tận tình hướng dẫn và đưa

ra nhiều ý kiến đóng góp cho em trong suốt quá trình thực hiện và hoàn thành

luận văn này.

Em cũng xin được gửi lời cảm ơn đến các thầy giáo, cô giáo Trường

Đại học Công nghệ Thông tin và Truyền thông – Đại học Thái Nguyên trực

tiếp giảng dạy và truyền đạt những kiến thức quý báu cho em trong suốt quá

trình học tập tại trường.

Mặc dù đã cố gắng hoàn thành luận văn trong phạm vi và khả năng của

mình, tuy nhiên sẽ không tránh khỏi những thiếu sót. Em rất mong nhận được

sự cảm thông và chỉ bảo của quý thầy cô và các bạn. Em xin chân thành cảm

ơn.

ii

LỜI CAM ĐOAN

Tôi xin cam đoan Luận văn “Thuật toán xấp xỉ ứng dụng vào một số

bài toán lớp NP” là do tôi thực hiện dưới sự hướng dẫn trực tiếp của thầy TS.

Vũ Vinh Quang. Các kết quả, số liệu nêu trong luận văn là trung thực.

Tất cả những tham khảo từ những nghiên cứu liên quan đều được nêu

rõ nguồn gốc trong danh mục tài liệu tham khảo và được chỉ rõ tham khảo

trong tài liệu nào. Mọi sao chép không hợp lệ và vi phạm quy chế đào tạo, tôi

xin chịu hoàn toàn trách nhiệm.

HỌC VIÊN

Nguyễn Hữu Chuyên

iii

MỤC LỤC

LỜI CẢM ƠN............................................................................................................I

LỜI CAM ĐOAN .................................................................................................... II

DANH MỤC CÁC BẢNG .......................................................................................V

DANH MỤC CÁC HÌNH........................................................................................V

LỜI MỞ ĐẦU............................................................................................................1

CHƯƠNG 1................................................................................................................2

MỘT SỐ KIẾN THỨC CƠ BẢN ............................................................................2

1.1 Thuật toán............................................................................................................2

1.1.1 Khái niệm bài toán ........................................................................................2

1.1.2. Khái niệm thuật toán....................................................................................2

1.1.3. Các yêu cầu của thuật toán..........................................................................2

1.1.4 Các phương pháp mô tả thuật toán ..............................................................3

1.2. Độ phức tạp của thuật toán...............................................................................4

1.2.1. Chi phí phải trả cho một quá trình tính toán..............................................4

1.2.2. Thời gian thực hiện giải thuật.....................................................................4

1.2.3. Độ phức tạp của thuật toán..........................................................................5

1.2.4. Các qui tắc xác định độ phức tạp thuật toán ..............................................6

1.3. Vấn đề phân lớp các bài toán............................................................................6

1.4 Mô hình Bài toán Knapsack...............................................................................7

Hình 1.1 Bài toán xếp ba lô dạng 0-1...................................................................8

CHƯƠNG 2..............................................................................................................13

MỘT SỐ THUẬT TOÁN XẤP XỈ ........................................................................13

2.1 Khái niệm về thuật toán xấp xỉ........................................................................13

2.2 Phương pháp quy hoạch động ........................................................................15

2.2.1 Một số khái niệm .........................................................................................15

2.2.2 Các bước thực hiện .....................................................................................16

2.3 Phương pháp tham lam ....................................................................................19

2.3.1 Giới thiệu chung..........................................................................................19

2.3.2 Đặc trưng của phương pháp tham lam ......................................................20

2.3.3 Các thành phần cơ bản ...............................................................................20

iv

2.3.4 Các bước xây dựng thuật toán tham lam ...................................................21

2.3.5 Mô hình thuật toán tham lam.....................................................................22

2.4 Thuật toán Di truyền GA .................................................................................27

2.4.1 Giới thiệu .....................................................................................................27

2.4.2 Các khái niệm cơ bản..................................................................................28

2.4.3 Thuật toán GA .............................................................................................29

2.4.4 Cơ chế thực hiện GA...................................................................................29

CHƯƠNG 3..............................................................................................................37

MÔ HÌNH BÀI TOÁN LẬP LỊCH TRONG BỆNH VIỆN ................................37

3.1 Đặt vấn đề ..........................................................................................................37

3.2 Giới thiệu tổng quan bệnh viện A....................................................................37

3.3 Các mô hình phân công các ca trực.................................................................40

3.3.1 Bài toán phân công trực tại các khoa chuyên môn ...................................41

3.3.2 Bài toán phân công trực tại các Phòng khám............................................45

KẾT LUẬN..............................................................................................................60

TÀI LIỆU THAM KHẢO ......................................................................................61

PHẦN PHỤ LỤC.....................................................................................................62

v

DANH MỤC CÁC BẢNG

STT Tên bảng

1 Bảng 2.1 Mô tả bảng phương án của phương pháp quy hoạch động

2 Bảng 3.1: Ma trận ràng buộc B

3 Bảng 3.2: Ma trận ràng buộc Y

4 Bảng 3.3: Lịch trực các buổi trong tuần

5 Bảng 3.4: Số buổi trực đối với các Bác sĩ – Y tá

6 Bảng 3.5: Bảng các Bác sĩ phù hợp với chuyên môn phòng khám (tham lam)

7 Bảng 3.6: Bảng các Y tá phù hợp với chuyên môn phòng khám (tham lam)

8 Bảng 3.7: Bảng các Bác sĩ sẵn sàng nhận buổi trực (tham lam)

9 Bảng 3.8: Bảng các Y tá sẵn sàng nhận buổi trực (tham lam)

10 Bảng 3.9: Lịch trực tại các phòng trong các buổi (tham lam)

11 Bảng 3.10: Số buổi trực đối với các Bác sĩ (tham lam)

12 Bảng 3.11: Số buổi trực đối với các Y tá (tham lam)

13 Bảng 3.12: Bảng các Bác sĩ phù hợp với chuyên môn phòng khám (GA)

14 Bảng 3.13: Bảng các Y tá phù hợp với chuyên môn phòng khám (GA)

15 Bảng 3.14: Bảng các Bác sĩ sẵn sàng nhận buổi trực (GA)

16 Bảng 3.15: Bảng các Y tá sẵn sàng nhận buổi trực (GA)

17 Bảng 3.16: Lịch trực tại các phòng trong các buổi (GA)

18 Bảng 3.17: Số buổi trực đối với các Bác sĩ (GA)

19 Bảng 3.18: Số buổi trực đối với các Y tá (GA)

DANH MỤC CÁC HÌNH

STT Tên hình Hình

1 Khối bắt đầu (Kết thúc)

2 Khối kiểm tra

3 Khối tính toán

4 Cung định hướng