Tài liệu NGHIÊN CỨU KHOA HỌC ỨNG DỤNG GIẢI THUẬT TÔ MÀU ĐỒ THỊ VÀO BÀI TOÁN XẾP LỊCH THI
Chủ nhiệm đề tài : TS. Dương Tuấn Anh
Thành viên:
KS. Nguyễn Hữu Hải
KS. Nguyễn Lư Đăng Khoa
Mục Lục:
Lời giới thiệu..............................................................................................1
Chương 1 Mô tả bài toán xếp lịch thi......................................................2
1.1Một số thuật ngữ......................................................................................... 2
1.2Bài toán xếp lịch thi.................................................................................... 2
Chương 2 Giải thuật tô màu đồ thị .........................................................4
2.1
Bài toán tô màu đồ thị...................................................................................... 4
2.2Một số heuristic tô màu đồ thị..................................................................... 5
2.2.1 Largest degree first.................................................................................. 5
2.2.2 Largest degree first : fill from top............................................................ 5
2.2.3 Largest degree first recursive : fill from top............................................ 5
2.2.4 Largest modified degree first................................................................... 6
Chương 3 Thiết kế và hiện thực.................................................................7
3.1
Chọn lựa giải thuật tô màu............................................................................... 7
3.1.1 Bias selection ........................................................................................... 7
3.1.2 Giải thuật được sử dụng trong đề tài....................................................... 7
3.2
Giải quyết các ràng buộc .................................................................................. 8
3.2.1 Tính bậc của các môn thi......................................................................... 8
3.2.2 Giải quyết các ràng buộc......................................................................... 8
3.3Giải thuật xếp phòng thi ........................................................................... 10
3.3.1 Bài toán Bin Packing ............................................................................. 10
3.3.2 Bài toán Knapsack................................................................................. 12
3.3.3 Giải thuật chọn lựa ............................................................................... 15
3.4
Quá trình xếp lịch thi....................................................................................... 15
3.5Giao diện chương trình................................... ........................................... 16
3.5.1 Dialog Chuẩn bị : .................................................................................. 17
3.5.2 Dialog Danh mục tiết bắt đầu................................................................ 17
3.5.3 Dialog Lựa chọn khóa............................................................................ 17
3.5.4 Dialog ghép song song........................................................................... 18
3.5.5 Dialog Hiệu chỉnh.................................................................................. 19
3.5.6 Dialog Ngày bận cho tất cả các nhóm................................................... 19
________________________________________
Page 4
3.5.7 Dialog Ngày bận cho từng nhóm........................................................... 20
3.5.8 Dialog Chỉnh thông số giải thuật........................................................... 20
3.5.9 Dialog Xếp lịch thi................................................................................. 20
3.5.10 Dialog Xem lịch thi sinh viên............................................................... 20
3.5.11 Dialog Xem, sửa lịch thi ...................................................................... 21
3.5.12 Chức năng In lịch thi theo ngày........................................................... 22
3.6Hiện thực ứng dụng và kết quả thực nghiệm........................................... 24
3.6.1 Hiện thực ứng dụng................................................................................ 24
3.6.2 Kết quả thực nghiệm .............................................................................. 25
Chương 4 Kết luận..................................................................................26
Tài liệu tham khảo.....................................................................................27
Phụ lục ........................................................................................................28
________________________________________
Page 5
Danh mục hình
Hình 2.1. Một đồ thị xung đột............................................................................................. 5
Hình 3.1. Giải thuật tính bậc của các môn thi.................................................................... 8
Hình 3.2. Penalty matrix..................................................................................................... 9
Hình 3.3. Giải thuật cập nhật ma trận phạt...................................................................... 10
Hình 3.4. Giải thuật Next Fit........................................................................................... 11
Hình 3.5. Giải thuật First Fit ........................................................................................... 11
Hình 3.6. Giải thuật Worst Fit.......................................................................................... 12
Hình 3.7. Giải thuật Best Fit............................................................................................ 12
Hình 3.8. Giải thuật Knapsack 1 ..................................................................................... 13
Hình 3.9. Giải thuật Knapsack 2 ..................................................................................... 14
Hình 3.10. Giao diện chính của chương trình. ................................................................. 16
Hình 3.11. Dialog chuẩn bị................................................................................................ 17
Hình 3.12. Dialog Danh mục tiết bắt đầu.......................................................................... 17
Hình 3.13. Dialog Lựa chọn khóa. ................................................................................... 18
Hình 3.14. Dialog Ghép song song. .................................................................................. 18
Hình 3.15. Dialog Hiệu chỉnh............................................................................................ 19
Hình 3.16. Dialog Ngày bận cho tất cả các nhóm............................................................. 20
Hình 3.17. Dialog Chỉnh thông số giải thuật.................................................................... 21
Hình 3.18. Dialog Xếp lịch thi ......................................................................................... 21
Hình 3.19. Dialog Xem lịch thi sinh viên.......................................................................... 22
Hình 3.20. Dialog Xem, sửa lịch thi.................................................................................. 23
Hình 3.21. Dialog In lịch thi theo ngày............................................................................. 23

_________________________________________
Bài viết được đăng bởi: sandykg09
Đăng trên: Tinhoc2

Hãy cùng chia sẻ với bạn bè bằng cách
Copy đường link dưới đây gửi đến nick yahoo bạn bè!

--> http://tinhoc2.net/tai-lieu-ung-dung-giai-thuat-to-mau-vao-sap-xep-lich-thi/ Xin lỗi đã Spam , gửi cho bạn bè tin này dùm mình nha ( an tâm là không có virus đâu )

Xem bài viết Tài liệu : ứng dụng giải thuật tô màu vào sắp xếp lịch thi cực hay - Tài liệu : ứng dụng giải thuật tô màu vào sắp xếp lịch thi cực hấp dẫn