Если у вас нет бесконечного количества агентов, чтобы совместимый агент был доступен, как только будут выполнены все предшествующие задачи, это проблема NP-сложная.
<бесстыдная вилка>
Очень похожая проблема есть в моей книге " Алгоритмы для интервью "
</ бесстыдная вилка>
Вот проблема и решение из книги:
Нам нужно запланировать N лекций в M классных комнатах. Некоторые из этих лекций являются необходимыми условиями для других. Как бы вы выбрали, когда и где проводить лекции, чтобы как можно быстрее закончить все лекции?
Решение:
Нам дают набор из лекций продолжительностью N единиц и M классных комнат. Лекции могут проводиться одновременно, если нет необходимости проводить две лекции в одной и той же классной комнате в одно и то же время и соблюдаются все ограничения приоритета.
Известно, что проблема планирования этих лекций с целью минимизации времени, необходимого для их завершения, является NP-полной.
Эта проблема естественно моделируется с помощью графиков. Мы моделируем лекции как вершины с ребром от вершины u до вершины v, если u является необходимым условием для v. Очевидно, что граф должен быть ациклическим, чтобы выполнялись ограничения предшествования.
Если есть только одна аудитория, мы можем просто провести лекции в топологическом порядке и завершить N лекций в N раз (при условии, что каждая лекция имеет единичную продолжительность).
Мы можем разработать эвристику, соблюдая следующее: в любое время есть набор лекций, чьи ограничения приоритета были выполнены. Если этот набор меньше, чем M, мы можем запланировать все из них; в противном случае нам нужно выбрать подмножество для планирования.
Выбор подмножества может быть основан на нескольких метриках:
- Ранжирование лекций в зависимости от длины самой длинной цепочки зависимостей, в которой они находятся в начале.
- Ранжирование лекций в зависимости от количества лекций, для которых они являются непосредственными предпосылками.
- Ранжирование лекций по общему количеству лекций, для которых они являются прямыми или косвенными предпосылками.
Мы также можем использовать комбинации этих критериев для заказа лекций, которые в настоящее время планируются.
Например, для каждой вершины мы определяем ее критичность как длину самого длинного пути от нее до приемника. Мы планируем лекции, обрабатывая вершины в топологическом порядке. В любой точке нашего алгоритма у нас есть набор лекций-кандидатов - это лекции, предварительные условия которых уже запланированы.
Если набор кандидатов меньше, чем размер M, мы планируем все лекции; в противном случае мы выбираем М наиболее важных лекций и планируем их - идея в том, что они должны быть запланированы раньше, поскольку они находятся в начале более длинных цепочек зависимостей.
Критерий является эвристическим и может не привести к оптимальным графикам - этого следует ожидать, так как проблема является NP-полной. Можно использовать другую эвристику, например, мы можем использовать количество лекций, которые зависят от лекции L, в качестве критичности лекции L или некоторой комбинации критерия.