Thuật toán lập lịch trình phù hợp tốt nhất

Question

Tôi đang viết một chương trình lập lịch biểu với một vấn đề lập trình khó. Có một số sự kiện, mỗi sự kiện có nhiều lần họp. Tôi cần phải tìm một sự sắp xếp của thời gian họp như vậy mà mỗi lịch trình có chứa bất kỳ sự kiện cụ thể một lần, sử dụng một trong nhiều lần họp của mỗi sự kiện.

Rõ ràng là tôi có thể sử dụng lực lượng vũ phu, nhưng đó hiếm khi là giải pháp tốt nhất. Tôi đoán đây là một vấn đề khoa học máy tính tương đối cơ bản, mà tôi sẽ tìm hiểu về một khi tôi có thể bắt đầu tham gia các lớp khoa học máy tính. Trong thời gian chờ đợi, tôi thích bất kỳ liên kết nào mà tôi có thể đọc về điều này, hoặc thậm chí chỉ là một cái tên tôi có thể sử dụng Google.

Answer 1

Tôi nghĩ rằng bạn nên sử dụng thuật toán di truyền vì:

• Nó là thích hợp nhất cho trường hợp vấn đề lớn.
• Điều này làm giảm độ phức tạp của thời gian đối với giá câu trả lời không chính xác (Không phải là tối ưu nhất)
• Bạn có thể chỉ định các ràng buộc & tùy chọn dễ dàng bằng cách điều chỉnh các hình phạt thể dục.
• Bạn có thể chỉ định giới hạn thời gian để thực thi chương trình.

• Chất lượng của giải pháp phụ thuộc vào bao nhiêu thời gian bạn có ý định dành giải quyết chương trình ..

  Genetic Algorithms Definition

  Genetic Algorithms Tutorial

  Class scheduling project with GA

Answer 2

Mô tả sự cố của bạn không hoàn toàn rõ ràng, nhưng nếu tất cả những gì bạn đang cố gắng tìm thấy lịch biểu không có sự kiện chồng chéo thì đây là vấn đề đơn giản bipartite matching.

Bạn có hai bộ nút: sự kiện và thời gian. Vẽ một cạnh từ mỗi sự kiện cho mỗi thời gian họp có thể. Sau đó, bạn có thể xây dựng kết hợp một cách hiệu quả (tập hợp các cạnh có thể lớn nhất giữa các nút) bằng cách sử dụng augmented paths. Điều này hoạt động bởi vì bạn luôn có thể chuyển đổi biểu đồ hai chân thành thành biểu đồ luồng tương đương.

Ví dụ về mã thực hiện điều này là BIM. Thư viện đồ hoạ chuẩn như GOBLIN và NetworkX cũng có triển khai kết hợp hai bên.

Answer 3

Điều này nghe như thế này có thể là một ứng cử viên tốt cho giải pháp dynamic programming, cụ thể là điều gì đó tương tự như sự cố interval scheduling.

Có một số hình ảnh here cho vấn đề lập lịch trình theo thời gian cụ thể, điều này có thể làm cho khái niệm rõ ràng hơn. Here là một hướng dẫn tốt về lập trình động tổng thể.

Answer 4

Có một số cách để làm này

Một cách tiếp cận là lập trình ràng buộc. Đó là một trường hợp đặc biệt của chương trình năng động được đề xuất bởi feanor. Thật hữu ích khi sử dụng một thư viện chuyên ngành có thể thực hiện giới hạn và phân nhánh cho bạn. (Google cho "gecode" hoặc "comet-online" để tìm thư viện)

Nếu bạn đang nghiêng về mặt toán học thì bạn cũng có thể sử dụng lập trình số nguyên để giải quyết vấn đề.Ý tưởng cơ bản ở đây là dịch vấn đề của bạn thành một tập bất đẳng thức tuyến tính. (Google cho "lập lịch số nguyên" để tìm nhiều ví dụ thực tế đời sống và google cho "Abacus COIN-OR" cho một thư viện hữu ích)

Tôi đoán rằng lập trình ràng buộc là cách tiếp cận dễ nhất, nhưng lập trình số nguyên rất hữu ích nếu bạn muốn bao gồm các biến thực sự trong bạn vấn đề tại một số điểm.