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

Question

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

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

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

Спасибо!

Answer 1

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

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

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

Answer 2

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

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

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

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

Answer 3

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

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

Answer 4

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