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

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

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

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

Спасибо!


algorithm language-agnostic planning
person Razzie    schedule 02.12.2009    source источник

Ответы (4)


arrow_upward
3
arrow_downward

Я думаю, это довольно легко.

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

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

person Henri    schedule 02.12.2009
comment
Это тоже была моя первая идея. Но у меня все еще есть ощущение, что таким образом можно столкнуться с проблемами. Но опять же, может быть, я ошибаюсь. Возможно, мне придется сначала написать это на бумаге. +1 в любом случае! - person Razzie; 03.12.2009
comment
Совершенно уверен, что у вас не будет проблем. Единственное, о чем я могу думать, это то, что родитель должен вернуться через два дня. Но вы можете исправить это с помощью некоторых условий. Более того, я думаю, что этот алгоритм настолько прост, что вы даже можете доказать его с помощью небольшой магии формальных методов. - person Henri; 03.12.2009

arrow_upward
3
arrow_downward

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

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

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

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

person Chris Pitman    schedule 02.12.2009
comment
Вау, я не знал о ECLiPSe, выглядит очень весело! Я мог бы просто попробовать! - person Razzie; 03.12.2009

arrow_upward
1
arrow_downward

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

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

person Kevin Buchan    schedule 02.12.2009
comment
Проблема рюкзака здесь не применима. Предположительно времени хватит на все конференции, иначе время конференции сократилось бы. Даже если бы это было не так, большое количество родителей с одним ребенком в классе облегчило бы постоянное заполнение. - person David Thornley; 02.12.2009
comment
Причина, по которой я подумал о проблеме рюкзака, заключается в том, что это реальный мир, и, вероятно, будут дополнительные бизнес-правила, которые могут иметь вес для разных детей для определенных учителей/администраторов. Я предполагаю, что это может стать более сложным, чем просто заполнить оставшиеся места одинокими детьми. - person Kevin Buchan; 03.12.2009
comment
Кевинг, я склонен согласиться, поскольку я также предполагаю, что это может стать более сложным. Самое смешное, что я просто не уверен, поэтому, возможно, мне придется написать что-то на бумаге. Коллега также упомянул алгоритм рюкзака (хотя я думал, что он называется алгоритмом рюкзака). +1 - person Razzie; 03.12.2009

arrow_upward
1
arrow_downward

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

person Freddy    schedule 02.12.2009
comment
спасибо за ссылку. Беглый взгляд говорит мне, что это, по крайней мере, очень связано с моей проблемой. Я дам ему прочитать. +1 - person Razzie; 03.12.2009