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. | CÁC GIẢI THUẬT XẾP LỊCH Trình bày : Nguyễn Đức Khánh 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 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) 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 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. Thuật | CÁC GIẢI THUẬT XẾP LỊCH Trình bày : Nguyễn Đức Khánh 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 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) 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 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. 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) 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 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 Mô hình hóa Sự kiện là một nhóm .
