Có chiếc mũ thuật toán nào đã biết có thể giải quyết vấn đề sau: Chúng tôi có một phiên có nhiều cuộc nói chuyện đồng thời. Người dùng nên đánh dấu các cuộc nói chuyện quan tâm và sau đó chúng tôi sẽ tạo lịch trình các cuộc nói chuyện để hầu hết người của tôi có thể tham dự các buổi nói chuyện của họ và giảm thiểu xung đột về lịch trình.

Điều này có giống với bất kỳ vấn đề nào đã biết với một thuật toán giải đã biết không?

câu trả lời hay nhất

Điều này nghe giống như một bài toán NP-đầy đủ vì không gian tìm kiếm tăng theo cấp số nhân với số lượng phòng và bài giảng.

Tôi nghĩ bạn có thể đưa ra một số thuật toán tham lam có thể tạo ra giải pháp khả thi nhưng có thể chưa tối ưu.

Tôi đã suy nghĩ về nó và đưa ra thuật toán sau. Đề xuất, cải tiến và các thuật toán khác đều được chào đón :)

Giả sử có m phòng, mỗi phòng có tôi các khe, các khe được căn chỉnh và có n người tham gia. Khi đó sẽ có nhiều nhất m*tôi Bài giảng. Tôi sẽ tạo một tập tin chứa # bài giảng Một biểu đồ hoàn chỉnh về các đỉnh trong đó các cạnh sẽ có trọng số được tính toán dựa trên sở thích của người tham gia. Tôi sẽ yêu cầu người tham gia cung cấp một danh sách các bài giảng theo thứ tự. Tôi sẽ chỉ định một số giá trị cho từng vị trí - ví dụ 20 cho vị trí đầu tiên và 1 cho vị trí cuối cùng. Sau đó, đối với mỗi người tham gia, tôi sẽ chấp nhận thứ hạng của anh ta cho bài giảng Một, mình sẽ cộng giá trị vị trí cho mỗi cạnh liền kề trừ đi giá trị vị trí của nút đối diện.

Lời giải thích này nghe có vẻ hơi bất cập, hãy đưa ra một ví dụ. Có bốn nútMột,b,c,d. Những người tham gia sắp xếp chúng theo thứ tự bảng chữ cái. 1. nghĩa là 20 điểm, 2. -> 10 điểm, 3. -> 5 điểm, 4. -> 0 điểm. Vì thế Một Và b Các dòng giữa sẽ có 10 điểm. Một Và d Giữa 20 phút.

Sơ đồ này thể hiện mối quan hệ giữa các bài giảng. Giá trị càng nhỏ thì việc hai bài giảng diễn ra ở những thời điểm khác nhau càng quan trọng. Hoặc ngược lại, càng cao càng tốt và đặt chúng ở nhiều phòng khác nhau cùng một lúc.

Bây giờ chúng ta cần tìm độ dài của tôi nhỏ nhất m lối đi riêng từng phòng mx Phân công một nhóm bài giảng. Khó đấy (không có bằng chứng :)). Bây giờ là lúc đưa ra thuật toán tham lam để tìm cực tiểu cục bộ nào đó. Ví dụ, chúng ta có thể tìm cây bao trùm tối thiểu bằng cách sử dụng thuật toán Kruscal (hay đúng hơn là thuật toán của Prim vì đồ thị sẽ rất dày đặc) và sau đó tìm cây bao trùm tối thiểu. chiều dài là tôi con đường. Sau đó, chúng tôi xóa các nút của đường dẫn và gán chúng cho phòng m1. Tìm giá trị nhỏ nhất. Cây bao trùm trong biểu đồ mới. Tổng cộng lặp lại m Hạng hai.

Các giải pháp không nhất thiết là tối ưu vì nếu chúng được xây dựng bằng cách sử dụng hai cạnh của đường đi tối thiểu thứ nhất,m Tổng các đường đi tối thiểu có thể thấp hơn nên thuật toán sẽ không tìm được giải pháp tối ưu.

Tôi quan tâm đến suy nghĩ của bạn.

Về thuật toán giảm thiểu xung đột lịch trình phiên, chúng tôi đã tìm thấy một câu hỏi tương tự trên Stack Overflow: https://stackoverflow.com/questions/37360943/