Алгоритм поиск оптимального TimeTable

Я ищу алгоритм или общий способ решить следующую задачу:Алгоритм поиск оптимального TimeTable

студентов, ..., M вписаны для письменных examniations различных модулей. Надписи приведены в следующей таблице. Если каждый студент может сделать один экзамен в день, сколько дней необходимо, как минимум, для организации сеанса?

  |A|B|C|D|E|F|G|H|I|J|K|L|M| 
Module 1 | | | |X| |X|X| |X|X| | | | 
Module 2 |X| | | | |X| | | |X|X| | | 
Module 3 | |X| | | | | |X| | |X| |X| 
Module 4 |X| | |X| | | | | | | | | | 
Module 5 | | |X| |X| | | | |X| | |X| 
Module 6 | | |X| | | | |X| | | | | | 
Module 7 |X|X| | | | | | |X| |X| | | 
Module 8 | | |X| | | |X| | | | |X| |

Как я решаю проблему?

источник

2015-11-09 BennoDual

Я бы сказал, что первый шаг должен построить таблицу совместимости, то есть таблица, которая говорит вам, если это возможно, чтобы иметь модуль х и модуль у того же день. – njzk2

это домашнее задание? – Jelle

Я бы предложил изучить метод критического пути. –

С графикой окраски.

Создайте узел для каждого модуля, и всякий раз, когда у ученика есть модули i и j, существует край между узлами i и j. Цвет графика, цвета представляют дни. Между узлами есть край, когда модули не могут быть в один и тот же день, поэтому раскраска дает правильное расписание. Минимальная раскраска дает кратчайший график.

Как предложение на самом деле решения экземпляра (то есть, алгоритм раскраски графа), для такого размера я бы простой довольно грубой силы подход, вроде этого:

for k in 1 .. 
    tryColour(k, 1) 

tryColour(k, i): 
    if i > numnodes: 
     found it 
    for c in 1 .. k: 
     if node i can have colour c: 
      colours[i] = c 
      tryColour(k, i+1)

я заплатил не внимание к деталям там, это просто идея: выберите узел, придайте ему цвет, который не сразу невозможно, а затем рекурсивно окрасить остальные. Если рекурсивная раскраска становится пустой, повторите попытку со следующим цветом. Делайте все это с увеличением количества цветов, пока не найдете решение.

источник

2015-11-09 19:01:05 harold

Спасибо. При этом я мог бы решить проблему «вручную». Но когда я построил график, есть ли алгоритм для вычисления минимально необходимого количества цветов? – BennoDual

Если вы используете java, вы можете добавить состояние к своим узлам и просто посчитать их или использовать любой другой механизм. – Jelle

@Jelle, как это придает окраску? – harold

После того, как у вас есть таблица несовместимости, которая должна выглядеть как:

a[1] = [2,4,5,7,8] 
a[2] = [1,3,4,5,7] 
a[3] = [2,3,5,6,7] 
a[4] = [1,2,7,8] 
a[5] = [1,2,3,6,8] 
a[6] = [3,5,8] 
a[7] = [1,2,3,4] 
a[8] = [1,5,6]

Я думаю, что это что-то в идее:

Создать день-узел, поместить модуль в это с его несовместимыми модулями.
Затем, до тех пор, как любой узел до сих пор несовместимые модули не решены:
- поп несовместимый модуль из этого узла,
- либо поместить его в узел, который является совместимым, или создать новый день- узел
- затем удалите этот модуль из любого другого дня узла, в котором он был до сих пор присутствует

каждого день узел содержит список модулей, которые будут происходить в тот же день, и список модулей, которые не могут произойти в тот день. Я не совсем уверен, как доказать, что это оптимально. Кажется, потому что он рассматривает несовместимости с модулями, которые были замечены первыми.

Пример быстрой и грязной реализации питона: https://repl.it/BY2B

источник

2015-11-09 19:55:45 njzk2

Алгоритм поиск оптимального TimeTable

ответ

Смежные вопросы