Эффективный алгоритм учета времени

Question

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

Например, ввод может быть:
4-6 вечера, сайт A
1-2 вечера, сайт B
9-11 утра и 2-4 вечера сайт A

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

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

Редактировать 2: Чтобы уточнить, на выходе должен быть график с распределением людей таким образом, чтобы промежутки (случаи, когда никто не работал) были как можно меньше.

Answer 1

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

• Определите гранулярность вашей проблемы. Например. если это для школьного расписания, ваша гранулярность может составлять 1 час.
• Создание экземпляров для каждого временного интервала, деленного на гранулярность. Таким образом, для сайта B будет один экземпляр (1-2 вечера), для размера A будет много экземпляров (4-5 часов вечера, 5-6 часов вечера, 9-10 часов утра, 10-11 часов утра, ...).
• Создайте экземпляры для всех лиц, которых вы хотите назначить
• Затем итеративно назначьте человека на свободный временной интервал, принимая во внимание все ваши ограничения (например, отпуск, перерыв на обед, возможность делать только одну вещь за раз, максимальное количество людей на сайт, ...) до :
  • у вас есть правильное решение (хорошо, распечатайте его и выйдите из приложения)
  • Вы попадаете в ситуацию, когда вам все еще нужно разместить людей, но больше нет действительного интервала времени. Затем вернитесь назад (отмените последнее действие и попытайтесь найти для него альтернативу).

Если ваша проблема не слишком велика, вы можете найти решение в разумные сроки.

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

например. инструмент ECLIPSe - это среда программирования ограничений с открытым исходным кодом. Вы можете найти несколько примеров на http://eclipseclp.org/examples/index.html. Один хороший пример, который вы можете найти, это проблема SEND + MORE = MONEY. В этой задаче у вас есть следующее уравнение:

    S E N D
+   M O R E
-----------
= M O N E Y

Замените каждую букву цифрой, чтобы сумма была правильной. Это также показывает, что, хотя вы можете решить эту грубую силу, есть более разумные способы решения этой проблемы (см. http://eclipseclp.org/examples/sendmore.pl.txt).