CÁC GIẢI THUẬT XẾP CÁC GIẢI THUẬT XẾP LỊCHLỊCH
Trình bày : Nguyễn Đức Khánh Trình bày : Nguyễn Đức Khánh
11
Kế hoạch trình bày Kế hoạch trình bày
Tìm kiếm địa phương Tìm kiếm địa phương Các bài toán kinh điển Các bài toán kinh điển Tabu, Generic, simulated anealing, graph Tabu, Generic, simulated anealing, graph coloring. coloring. Mô hình hóa Mô hình hóa Bài toán tín chỉ Bài toán tín chỉ Hỏi và trả lời Hỏi và trả lời
22
Tìm kiếm địa phương Tìm kiếm địa phương
Bài toán xếp lịch thuộc lớp các bài toàn Bài toán xếp lịch thuộc lớp các bài toàn NPcomplete. Không thể tìm kết quả tối NPcomplete. Không thể tìm kết quả tối ưu.ưu. Hàm mục tiêu Hàm mục tiêu Ràng buộc Ràng buộc một tập hợp các biến số – một tập hợp các biến số thỏa mãn phương trình, bất phương trình. – thỏa mãn phương trình, bất phương trình. Tìm kiếm địa phương (Local Search) Tìm kiếm địa phương (Local Search)
33
Các bài toán kinh điển Các bài toán kinh điển
Bài toán 8 con hậu (n hậu) Bài toán 8 con hậu (n hậu) Tô màu bản đồ (graph coloring) Tô màu bản đồ (graph coloring) SEND MORE MONEY SEND MORE MONEY Sodoku Sodoku Xếp lịch Xếp lịch TKB – TKB Làm việc – Làm việc Máy bay – Máy bay – ……
44
Simulated annealing Simulated annealing
Process annealing Process annealing Mục tiêu dựng thanh đao đúng hình dạng đủ bền – Mục tiêu dựng thanh đao đúng hình dạng đủ bền vững vững Phương pháp: nung nóng chảy, và tôi thép thành hình – Phương pháp: nung nóng chảy, và tôi thép thành hình thanh đao, rồi làm nguội = nước. thanh đao, rồi làm nguội = nước. Khi tôi 1 lần thanh đao sẽ rất giòn, nếu quá trình tôi – Khi tôi 1 lần thanh đao sẽ rất giòn, nếu quá trình tôi thực hiện nhiều lần (nung nóng, tôi hình, làm nguội) thực hiện nhiều lần (nung nóng, tôi hình, làm nguội) thanh đao sẽ thỏa mãn các ràng buộc thanh đao sẽ thỏa mãn các ràng buộc Các kết quả sau tốt hơn các kết quả trước, nhiệt độ – Các kết quả sau tốt hơn các kết quả trước, nhiệt độ nung của các lần sau sẽ giảm dần. nung của các lần sau sẽ giảm dần.
55
Thuật toán di truyền Thuật toán di truyền
Dựa trên lý thuyết di truyền của Darwin Dựa trên lý thuyết di truyền của Darwin Cá thể mạnh tồn tại, cá thể yếu chết Cá thể mạnh tồn tại, cá thể yếu chết Mama và papa gặp nhau (2 cá thể mạnh gặp nhau) Mama và papa gặp nhau (2 cá thể mạnh gặp nhau) Chung sống với nhau và sinh ra 1 cá thể con mới (có bộ Chung sống với nhau và sinh ra 1 cá thể con mới (có bộ gen khỏe = gen papa + gen mama) đồng thời chết đi 1 gen khỏe = gen papa + gen mama) đồng thời chết đi 1 cá thể yếu. cá thể yếu. Do 1 sinh 1 mất nên tổng số cá thể bảo toàn trong mỗi Do 1 sinh 1 mất nên tổng số cá thể bảo toàn trong mỗi chu kỳ sinh nở. chu kỳ sinh nở. Sau nhiều chu kỳ sinh nở các cá thể còn tồn tại là các cá Sau nhiều chu kỳ sinh nở các cá thể còn tồn tại là các cá thể có bộ gen rất mạnh (kết quả rất tối ưu thỏa mãn các thể có bộ gen rất mạnh (kết quả rất tối ưu thỏa mãn các ràng buộc) ràng buộc)
66
Tô màu đồ thị Tô màu đồ thị
Bài toán: mỗi nước trên bản đồ thế giới tô Bài toán: mỗi nước trên bản đồ thế giới tô = 1 màu, các nước gần nhau có màu # = 1 màu, các nước gần nhau có màu # nhau. nhau. Áp dụng tốt nhất cho TKB Áp dụng tốt nhất cho TKB Mỗi màu là một sự kiện Mỗi màu là một sự kiện Tô màu vào bảng thời gian mỗi người sao Tô màu vào bảng thời gian mỗi người sao cho các sự kiện (màu) chỉ suất hiện 1 lần cho các sự kiện (màu) chỉ suất hiện 1 lần
77
Tabu Search Tabu Search
Ý tưởng chính là tạo một bộ khóa. Ý tưởng chính là tạo một bộ khóa. Trong quá trình tìm kiếm kết quả chúng ta Trong quá trình tìm kiếm kết quả chúng ta thường gặp tình huống kết quả lần trước thường gặp tình huống kết quả lần trước và lần sau là giống nhau. và lần sau là giống nhau. Chương trình tìm kiếm sẽ rơi vào vòng lặp Chương trình tìm kiếm sẽ rơi vào vòng lặp vô hạn. vô hạn. Để tránh vòng lặp vô hạn và có kết quả tốt Để tránh vòng lặp vô hạn và có kết quả tốt hơn chúng ta sử dụng Tabu hơn chúng ta sử dụng Tabu
88
Mô hình hóa Mô hình hóa
Sự kiện là một nhóm sinh viên học một Sự kiện là một nhóm sinh viên học một môn học duới sự giảng dạy của một giáo môn học duới sự giảng dạy của một giáo viên tại một phòng viên tại một phòng Nếu coi bảng thời gian của giáo viên, Nếu coi bảng thời gian của giáo viên, phòng, lớp, sinh viên là các bảng 2 chiều phòng, lớp, sinh viên là các bảng 2 chiều mxn.mxn. Xếp lịch là hành động xếp các sự kiện vào Xếp lịch là hành động xếp các sự kiện vào các ô trống thời gian, đảm bảo các ràng các ô trống thời gian, đảm bảo các ràng buộc buộc
99
Bài toán TKB Bài toán TKB
Không giáo viên, phòng, sinh viên .. Cùng Không giáo viên, phòng, sinh viên .. Cùng thời gian có 2 sự kiện. thời gian có 2 sự kiện. Độ khó của bài toán phụ thuộc vào các Độ khó của bài toán phụ thuộc vào các chiều giáo viên, phòng học, sinh viên, lớp chiều giáo viên, phòng học, sinh viên, lớp ……
1010
Giải pháp chung Giải pháp chung
Tìm kiếm phương án khởi tạo Init Tìm kiếm phương án khởi tạo Init Từ phương án khởi tạo, tìm các kết quả Từ phương án khởi tạo, tìm các kết quả mới tốt hơn dựa trên các thuật toán có sẵn mới tốt hơn dựa trên các thuật toán có sẵn hoặc lai ghép các thuật toán. hoặc lai ghép các thuật toán. Tìm kiếm địa phương sử dụng phương Tìm kiếm địa phương sử dụng phương pháp tính trước hậu quả để dự đoán kết pháp tính trước hậu quả để dự đoán kết quả sau có tốt hơn không? quả sau có tốt hơn không?
1111
Tín chỉ Tín chỉ
Bài toán 1 : xếp lịch học tín chỉ trước, sau đó xếp Bài toán 1 : xếp lịch học tín chỉ trước, sau đó xếp SV vào các lớp. SV vào các lớp. Đơn giản dễ viết ít ràng buộc – Đơn giản dễ viết ít ràng buộc Một số SV không được chấp nhận lựa chọn của mình – Một số SV không được chấp nhận lựa chọn của mình vì không còn lớp vì không còn lớp
Bài toán 2 : Xếp lịch học sau khi SV đăng ký Bài toán 2 : Xếp lịch học sau khi SV đăng ký Khó phức tạp vì nhiều ràng buộc – Khó phức tạp vì nhiều ràng buộc Có thể nảy sinh trường hợp không tìm ra kết quả – Có thể nảy sinh trường hợp không tìm ra kết quả
1212
Câu hỏi? Câu hỏi?
1313
