Это оптимальный график задачи NPC? - PullRequest
Новая
       37

Это оптимальный график задачи NPC?

2 голосов
/ 19 августа 2010

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

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

(Если существует конфликт времени и учитель математики не может присутствовать на конференции, родитель будет встречаться только с учителем английского языка)

Я не знаю много о проблемах типа NP, но когда я слышу слова "оптимальный" и "график" вместе, я начинаю удивляться ...

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

  • 500 родителей
  • 15 учителей английского
  • 5 учителей математики
  • 25 дат, чтобы выбрать из

Может ли это быть правильно решено за несколько секунд, минут или часов на компьютере вашей бабушки?

1 Ответ

0 голосов
/ 20 августа 2010

Ну, у меня есть частичный ответ на ваш вопрос и симуляция, которая позволяет мне пробовать разные сценарии. Вот мои рабочие (но изменчивые) предположения:

  • Параметры указаны в списке
  • Выбор времени сеанса родителями осуществляется по степенному закону ( Распределение по Бенфорду), поскольку это моделирует ожидаемую неравномерность предпочтений
  • В зависимости от пробега было ~ 20 родителей, которые были «непримиримыми» и могли прийти только на один сеанс.
  • У каждого учителя английского языка есть один и только один соответствующий учитель математики, поскольку их соотношение считается высоким, но я не знаю, насколько оно высоко. Код может обрабатывать любой коэффициент корреляции от 0 до 1.
  • Весь шебанг от создания правдоподобных смоделированных родителей («кузнец» .. «аткинс»), учителей, выбора времени и удовлетворительных результатов занял 300 миллисекунд на машине среднего класса (5300 BogoMIPS ).

Мои оптимизации второго порядка даже не вступили в силу, так как первый проход позволял каждому первому выбору родителей принять максимум 11 родителей за один сеанс. Этот результат был неоптимальным для учителей, которые должны были посещать около половины временных интервалов со средней родительской группой ~ 3.

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

...