Алгоритм для инструмента планирования
Я пишу небольшое программное приложение, которое должно служить простым инструментом планирования для местной школы. "Проблема", которую нужно решить, довольно проста. А именно, учителя должны общаться с родителями всех детей. Однако у некоторых детей, разумеется, есть братья и сестры в разных группах, поэтому эти беседы должны быть запланированы рядом друг с другом, чтобы избежать ситуаций, когда родители разговаривают в 6 часов вечера, а другой - в 10 часов вечера. Таким образом, короче говоря, учитывая набор из n детей, где у некоторых детей есть 1 или более братьев или сестер, составьте расписание, в котором все разговоры этих детей планируются рядом друг с другом.
Теперь, может быть, проблема может быть решена очень легко, но с другой стороны, я чувствую, что это может быть довольно сложной проблемой, которая нуждается и может быть решена с помощью какого-то алгоритма. Элегантно. Но я прав? Есть? Я посмотрел на венгерский алоритм, но он не совсем подходит для этой конкретной проблемы.
Редактировать: я забыл упомянуть, что все разговоры занимают одинаковое количество времени.
Спасибо!
4 ответа
Я думаю, что это довольно легко.
Сначала группа детей, которые принадлежат друг к другу, потому что они имеют общих родителей. Планируйте детей в группе последовательно, планируйте остальных как случайных.
Еще один способ абстрагироваться от этой проблемы и облегчить ее - взглянуть с точки зрения родителей, увидеть братьев и сестер как "детей" и дать им больше времени. Тогда вы можете просто назначить родителей наугад, но некоторым нужно больше времени (потому что у них несколько детей).
Один из подходов заключается в том, чтобы определить проблему на языке декларативных ограничений, а затем разрешить ее для вас. В прошлый раз, когда я сделал это, я использовал ECLiPSe, который является изящным маленьким языком, где вы определяете свое проблемное пространство по ограничениям, а затем позволяете ему находить допустимые значения, которые удовлетворяют этим ограничениям.
Например, я считаю, что у вас есть два класса ограничений:
- Учитель может проводить только одну конференцию одновременно
- Все ученики в одной семье должны иметь последовательные слоты
Как только вы определите их в ECLiPSe, он рассчитает значения для каждого учащегося, которые удовлетворяют требованиям. Если вы пойдете по этому пути, вы также можете легко добавлять ограничения по мере необходимости. Например, легко сказать, что учение недоступно для слота Y, или учителя должны по очереди выполнять административную работу и т. Д.
Это похоже на проблему типа "алгоритм рюкзака". Вы должны сгруппировать членов семьи вместе, а затем заполнить соответствующие места.
Если вы воспользуетесь "алгоритмом рюкзака" в Google, вы увидите достаточно рецензий, чтобы заставить вашу голову крутиться, а также несколько хороших закодированных решений.
Я думаю, что если бы каждый разговор можно было свести к "занятиям", где у каждого занятия есть время начала и время окончания, вы могли бы использовать алгоритм выбора вида деятельности, изученный в информатике. Он основан на жадном подходе и может быть решен в O(n) (где n - количество действий). Вы можете найти больше информации здесь. Я уверен, что вам нужно будет выполнить предварительную обработку здесь, чтобы иметь возможность уменьшить проблему брата / сестры как действия того же типа.