Как правильно подходить к следующей задаче планирования

Question

Я думаю о следующей проблеме планирования:

1. У меня X человек.
2. У меня есть Y слотов собраний с Z ролями собраний, доступными в каждомсовещание.
3. Для некоторых ролей один и тот же человек может объединить два из них в одном собрании, но большинство из них - один человек = одна роль.
4. Для каждого человека x в X,Я знаю множество фактов о них: а) в последний раз они присутствовали на собрании и играли определенную роль (историческая);б) их доступность для любой встречи y в Y;c) Их конкретное предпочтение ролей z в Z или набора ролей (без конкретных дат) для группы собраний.
5. Я хотел бы построить планировщик со следующими целями вум: а) Все роли встречи заполнены.б) предпочтения учитываются, если это возможно;c) Распределение людей / ролей должно быть равномерным (т. е. если один человек назначается на каждую встречу, а другой только на одну встречу время от времени - это недопустимо; если один человек назначен на одну и ту же роль снова и снова и снова и сноваопять же - это неприемлемо).

Теперь у меня есть чувство, что задача совсем не легкая :), поэтому мои конкретные вопросы:

1. Какой язык лучше подходит для этой задачи (как-то я чувствую, что Пролог может с этим справиться, но я не совсем уверен).

2. Какой правильный подход для решения этой задачии насколько я могу приблизиться к своим целям в # 4 выше?

3. Любое хорошее прочтение о том, какую проблему я хочу решить?

Спасибо!

PS Если вам любопытно, сценарий использования - это составление списка участников для совещания Тамада ( пример ) (мне лень это делать вручную, и я 'Я хотел бы, чтобы компьютер помог мне в этой задаче хотя бы частично).

Answer 1

Механизм правил, такой как Drools Expert или Пролог подходит для определения ограничений (= функция оценки).Однако это ужасно, когда находит лучшее решение.

Поскольку ваша проблема, вероятно, NP complete (особенно если собрания нужно поместить в временной интервал и / иличеловек не может посещать 2 собрания одновременно), вам необходимо использовать алгоритм оптимизации планирования, например, эвристику строительства и метаэвристику.Взгляните на пример курса учебного плана в Drools Planner (Java, открытый исходный код, ASL).

Answer 2

С моей точки зрения, язык, на котором вы собираетесь программировать, на самом деле не имеет большого значения: для простых задач использование языка - это скорее личное предпочтение, а не точная наука.Если вы любите / хотите изучать Python, используйте это.Если вы «чувствуете себя» как Пролог сегодня, используйте это.

Что будет иметь значение при вашем выборе, хотя это то, как вы хотите сохранить и представить свои данные.Из вашего вопроса можно сказать, что вам нужно следующее:

• База данных (или, по крайней мере, постоянный ресурс) для хранения доступных участников и ролей, прошлых и будущих собраний, где хранятся роли для каждогоучастник и способ планирования доступности.
• Какой-то способ представления ваших данных (командная строка, графический интерфейс или веб-сайт).
• Некоторая бизнес-логика, описывающая способ назначения ролей, критерии дляпосещаемость и прочее.

Для большинства из них вы захотите использовать сторонние компоненты, так как ваше время будет потрачено на добавленную стоимость вашего продукта;Создание блестящего инструментария ORM или GUI не ваша цель в этом.Поэтому язык программирования, который вы выберете, должен иметь надлежащую поддержку для этих элементов (особенно первых двух).Я не могу сказать это для Пролога, но Python позволит вам полностью охватить эти области.Я думаю, что это выходит за рамки этого вопроса, предлагая конкретные наборы инструментов, поэтому я оставлю это пока на этом.

После этого шага вы анализируете свою проблему, которую, кажется, уже достаточно хорошо сделали.,Итак, начните реализовывать это.Чтобы иметь возможность проверить ваши конкретные варианты использования, похоже, что вы могли бы извлечь выгоду из некоторого Test или Behavior Driven Design, так что вы можете прочитать об этом.

Для изучения языка просто найдите StackOverflow для "[language] tutorial ": уже есть множество ответов, связанных с очень хорошими ресурсами для начала работы с любым языком, который вы выберете.

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

Answer 3

Это звучит как проблема оптимизации, и я согласен с Джеффри, что это будет проблема NP Complete. Недавно я разработал алгоритм планирования для университета, который выполняет планирование выпускных экзаменов. Для решения этой проблемы я использовал генетический алгоритм с эвристикой, специфичной для предметной области. Моя реализация была выполнена хорошо с количеством студентов 3000+ и числом курсов 500, для поиска почти оптимального решения потребовалось около 2 часов.

Answer 4

Я согласен с людьми, которые предлагают Пролог для этой задачи; Я бы предложил посмотреть в ECLiPSe (это, помимо того, что реализация Пролога, программирование ограничений язык, который имеет более мощные возможности решения проблем, чем просто пролог). У ECLiPSe есть очень хорошее введение, много примеров и очень по существу, с бесплатным pdf, написанным Антони Нидерлински:

http://www.anclp.pl/

Среди примеров на сайте ECLiPSe я обнаружил следующее, которое представляется уместным: http://eclipseclp.org/examples/roster.ecl.txt.

ECLiPSe тщательно документирован и, согласно этой документации, также может быть интегрирован с C ++ / Java.

Answer 5

1. Несмотря на то, что я фанат Python, я бы вряд ли предложил Prolog для этой задачи.Я знаком с Прологом, и это определенно лучше решено с Прологом.Но это зависит от того, как вы будете использовать эту программу.Ваш выбор - решите, проще ли вам установить Python или Prolog (если вы просто запускаете его на своем локальном ПК, это не имеет большого значения, я думаю), или на других ваших требованиях.

2. С Прологом все просто, если вы знаете о Прологе.Я думаю, что после того, как вы изучите Пролог, вы можете решить его, не задумываясь, без особых проблем (если вы действительно поняли Пролог!).Я бы предложил использовать SWI-Prolog, это одна из самых распространенных реализаций Prolog.Также есть хороший учебник: http://www.learnprolognow.org/

Мне кажется, но я не уверен на 100%, что вы еще не знакомы с Прологом.Сначала вам нужно время, чтобы выучить пролог, поэтому это также зависит от того, насколько быстро вам нужна программа.Насколько я помню, пройти курс обучения можно менее чем за месяц.Конечно, это вряд ли зависит от того, сколько времени вы вкладываете в день - вы можете сделать это за меньшее или даже большее время.

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