Алгоритм инструмента планирования

Question

Я пишу небольшое программное приложение, которое должно служить простым инструментом планирования для местной школы. «Проблема», которую нужно решить, довольно проста. А именно, учителя должны разговаривать с родителями всех детей. Однако у некоторых детей, конечно, есть братья и сестры в разных группах, поэтому эти беседы должны быть запланированы рядом друг с другом, чтобы избежать ситуаций, когда родители разговаривают в 6 часов вечера, а другой - в 10 часов вечера. Таким образом, вкратце, учитывая совокупность n детей, где у некоторых детей есть 1 или более братьев или сестер, составьте график, в котором все разговоры этих детей планируются рядом друг с другом.

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

Редактировать: Я забыл упомянуть, что все разговоры занимают одинаковое количество времени.

Спасибо!

Answer 1

Один подход woul dbe, чтобы определить проблему на языке декларативных ограничений и затем разрешить ее для вас. В последний раз, когда я делал это, я использовал ECLiPSe , который является изящным маленьким языком, где вы определяете свое проблемное пространство по ограничениям, а затем позволяете ему находить допустимые значения, которые удовлетворяют этим ограничениям.

Например, я считаю, что у вас есть два класса ограничений:

1. Учитель может иметь только одного конференция одновременно
2. Все студенты в одной семье должны иметь последовательные слоты

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

Answer 2

Я думаю, что это довольно просто.

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

Еще один способ абстрагировать его и облегчить проблему - это взглянуть с точки зрения родителей, увидеть братьев и сестер как «детей» и дать им больше времени. Тогда вы можете просто назначить родителей наугад, но некоторым нужно больше времени (потому что у них несколько детей).

Answer 3

Я думаю, что если бы каждый разговор можно было свести к «занятиям», где у каждого занятия есть время начала и время окончания, вы могли бы использовать алгоритм выбора вида деятельности, изученный в информатике. Он основан на жадном подходе и может быть решен в O (n) (где n - количество действий). Вы можете найти больше информации здесь . Я уверен, что вам нужно будет выполнить предварительную обработку здесь, чтобы иметь возможность уменьшить проблему брата / сестры как действия того же типа.

Answer 4

Это похоже на проблему типа «алгоритм рюкзака». Вам необходимо сгруппировать членов семьи, а затем заполнить соответствующие ячейки.

Если вы воспользуетесь «алгоритмом рюкзака» Google, вы увидите достаточно рецензий, чтобы заставить вашу голову крутиться, а также несколько хороших кодированных решений.