CÁC GIẢI THUẬT XẾP LỊCH

Chia sẻ: Tham Tham | Ngày: | Loại File: PPT | Số trang:13

0
164
lượt xem
43
download

CÁC GIẢI THUẬT XẾP LỊCH

Mô tả tài liệu
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Kế hoạch trình bày: Tìm kiếm địa phương, Các bài toán kinh điển, Tabu, Generic, simulated anealing, graph coloring, Mô hình hóa, Bài toán tín chỉ, Hỏi và trả lời.

Chủ đề:
Lưu

Nội dung Text: CÁC GIẢI THUẬT XẾP LỊCH

  1. CÁC GIẢI THUẬT XẾP  LỊCH Trình bày : Nguyễn Đức Khánh 1
  2. Kế hoạch trình bày  Tìm kiếm địa phương  Các bài toán kinh điển  Tabu, Generic, simulated anealing, graph  coloring.  Mô hình hóa  Bài toán tín chỉ  Hỏi và trả lời 2
  3. 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  NP­complete. Không thể tìm kết quả tối  ưu.  Hàm mục tiêu  Ràng buộc – 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.  Tìm kiếm địa phương (Local Search) 3
  4. Các bài toán kinh điển  Bài toán 8 con hậu (n hậu)  Tô màu bản đồ (graph coloring)  SEND MORE MONEY  Sodoku  Xếp lịch – TKB  – Làm việc  – Máy bay – … 4
  5. Simulated annealing  Process annealing – Mục tiêu dựng thanh đao đúng hình dạng đủ bền  vững – 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. – 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)  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 độ  nung của các lần sau sẽ giảm dần. 5
  6. Thuật toán di truyền  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  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ộ  gen khỏe = gen papa + gen mama) đồng thời chết đi 1  cá thể yếu.  Do 1 sinh 1 mất nên tổng số cá thể bảo toàn trong mỗi  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á  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) 6
  7. Tô màu đồ thị  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 #  nhau.  Áp dụng tốt nhất cho TKB  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  cho các sự kiện (màu) chỉ suất hiện 1 lần 7
  8. Tabu Search  Ý 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  thường gặp tình huống kết quả lần trước  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  vô hạn.   Để 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 8
  9. Mô hình hóa  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  viên tại một phòng  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  mxn.  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  buộc 9
  10. Bài toán TKB  Không giáo viên, phòng, sinh viên .. Cùng  thời gian có 2 sự kiện.  Độ 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  … 10
  11. Giải pháp chung  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ả  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.  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  quả sau có tốt hơn không? 11
  12. Tín chỉ  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.  – Đơ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  vì không còn lớp  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 – Có thể nảy sinh trường hợp không tìm ra kết quả 12
  13. Câu hỏi? 13
Đồng bộ tài khoản