Все ли проблемы планирования NP-Hard?
Я знаю, что есть некоторые проблемы планирования, которые являются NP-сложными /NP-полными... однако, ни одна из них не указана таким образом, чтобы показать, что эта ситуация также является NP.
Если у вас есть набор задач, ограниченный startAfter, startBy и продолжительностью, все они пытаются использовать один ресурс... можете ли вы определить расписание или определить, что его нельзя решить без исчерпывающего поиска?
Если ответ "извините, приятель, но это NP-полная", какую эвристику лучше использовать, и есть ли способы уменьшить время, необходимое для а) разрешения графика и б) для выявления неразрешимой проблемы? график.
Я реализовал (в прологе) базовую цель разрешения конфликтов с помощью рекурсии, которая реализует эвристику "сначала самое маленькое окно". Это на самом деле находит решения довольно быстро, но исключительно медленно находит неверные расписания. Есть ли способ преодолеть это?
Уу за сложные вопросы!
6 ответов
Самая трудная часть большинства задач планирования в реальной жизни - это обрести надежность и полный набор ограничений. Если мы возьмем пример создания расписания университета:
- Профессор А не встанет утром, он во многих комитетах, но никто не расскажет офису расписаний о такого рода ограничениях.
- Департамент 1 нуждается в расписании к началу семестра, однако Департамент 2, который использует те же комнаты, не желает выбирать курсы, которые будут проводиться до тех пор, пока все студенты не приедут
- Так далее
Затем вам нужна система расписания, которая может справиться с изменениями, поэтому, когда в последнюю минуту изменяется одно ограничение, вам не нужно менять полное расписание.
Все вышеперечисленное обычно игнорируется в исследовательских работах о системах планирования. Что касается полноты NP данной задачи планирования, в реальной жизни вам все равно, даже если она не завершена, вы вряд ли сможете даже определить, что такое "лучшее решение", поэтому достаточно хорошее и достаточно хорошее.
См. http://www.asap.cs.nott.ac.uk/watt/resources/university.html для получения списка документов, которые могут помочь вам начать; Есть еще много PHD, которые должны быть в программном обеспечении планирования.
Вы можете использовать динамическое программирование, чтобы решить некоторые из этих вещей. Жадные алгоритмы также приходят на ум. Теория планирования и глубока, и красива, но те два, которые я найду, решат большинство проблем, с которыми я столкнулся. Возможно, мне повезло.
Часто существуют хорошие алгоритмы аппроксимации для NP-сложных / полных задач оптимизации, таких как планирование. Вы можете просмотреть заметки курса Ахмеда Абу Сафия о алгоритмах аппроксимации для составления расписания или различных работ.
В некотором смысле вся криптография с открытым ключом выполняется с "менее сложными" задачами, такими как факторинг частично, потому что сложные задачи NP предлагают слишком много простых случаев. Это та же самая NP-полнота, которая делает их "морально сложными", что также ставит их перед слишком многими легкими проблемами, которые часто попадают в некоторую границу ошибки оптимального.
Существует более глубокая теория твердости аппроксимации, в которой обсуждаются ограничения алгоритмов аппроксимации.
Что вы имеете в виду с startBy?
С startAfter и, если есть только один ресурс, то быстрым решением может быть использование топологической сортировки. Пример алгоритма выполняется за линейное время, но не включает случай ошибки, если график содержит циклы.
Вот тот, который не
Запланируйте набор заданий i= 1,2...n на одном компьютере, каждый из которых занимает время t(i), чтобы среднее время ожидания было минимизировано.
Решение: сортировка по возрастанию t(i). O(n log n)
Хороший список здесь
Рассмотрим проблему планирования в классе P:
Вход: список действий, которые включают время начала и время окончания.
Сортировать по времени окончания.
Выберите первые N элементов в этом отсортированном списке, чтобы найти максимальное количество действий, которые вы можете запланировать в данный момент времени.
Вы можете добавить предупреждения: все действия должны заканчиваться в 17:00, в этом случае, когда вы работаете со списком, остановитесь, как только вы достигнете действия, которое заканчивается после этого времени.