Алгоритм оптимального выбора действий для выполнения задачи

Question

Существует два типа данных: задачи и действия. Выполнение действия требует определенного времени, и набор задач состоит из этого действия. Задача имеет набор действий, и наша задача - выбрать одно из них. Итак:

class Task { Set<Action> choices; }
class Action { float time; Set<Task> dependencies; }

Например, основной задачей может быть «Получить дом». Возможные действия для этого задания: «Купить дом» или «Построить дом». Акция «Построить дом» стоит 10 часов и имеет зависимости «Получить кирпичи» (которая может стоить 6 часов) и «Получить цемент» (которая стоит 9 часов) и так далее.

Общее время - это сумма всех времен, необходимых для выполнения действий (в данном случае 10 + 6 + 9 часов). Мы хотим выбрать такие действия, чтобы общее время было минимальным.

Обратите внимание, что зависимости могут быть ромбовидными. Например, «Получить кирпичи» может потребовать «Получить машину» (для транспортировки кирпичей), а «Получить цемент» также может потребоваться автомобиль. Даже если вы выполняете «Получить кирпичи» и «Получить цемент», вам нужно только сосчитать время, необходимое для получения автомобиля один раз .

Обратите внимание, что зависимости могут быть круглыми. Например, «Деньги» -> «Работа» -> «Автомобиль» -> «Деньги». Для нас это не проблема, мы просто выбираем все «Деньги», «Работа» и «Автомобиль». Общее время - это просто сумма времени этих трех вещей.

Математическое описание:

Пусть actions будут выбранными действиями.

valid(task) = ∃action ∈ task.choices. (action ∈ actions ∧ ∀tasks ∈ action.dependencies. valid(task))
time = sum {action.time | action ∈ actions}
minimize time subject to valid(primaryTask)

Меня интересует не только оптимальное решение, но и приблизительное. Возможно, какое-то динамическое программирование может помочь там? Если задача имеет древовидную структуру, то динамическое программирование может дать оптимальное решение за полиномиальное время, но алмазные структуры, кажется, значительно усложняют проблему. Если у вас есть алгоритм, но он не работает, если есть циклы, опубликуйте его! Я, вероятно, все еще могу многому научиться на этом.

Поля представляют задачи, а кружки - действия (время выполнения действия - в кружке). У действия есть линия к задаче, если эта задача является зависимостью для действия. Вот описание проблемы снова в терминах рисунков: если выбран прямоугольник (= задача), то должен быть выбран один из кругов (= действия) внутри. Если выбран круг, то необходимо выбрать все связанных прямоугольников. Цель состоит в том, чтобы минимизировать сумму чисел в выбранных кругах.

Оптимальным решением в этом случае является выбор действия со временем 2 в верхней задаче и действий со временем 1 в нижней задаче. Общее время составляет 2 + 1 + 1 = 4. В этом случае есть 2 оптимальных решения. Второе решение - выбрать действие со временем 3 в верхней задаче и действие со временем 1 в правой нижней задаче. Общее время снова 3 + 1 = 4. Если в верхнем задании мы выбираем действие со временем 3, нам не нужно выполнять левое нижнее задание, потому что нет никакой границы между действием со временем 3 и левым нижним заданием.

Я прошу прощения за дерьмовый рисунок;) И еще два примера (оптимальное решение для каждого было указано синим, а основная задача была обозначена серым):

Answer 1

Вы можете смоделировать это как график и использовать алгоритм кратчайшего пути , чтобы найти решение. Каждая из Задач будет узлом, а Действия будут ребрами в графе.

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

Если вы рассматриваете задачу как совокупность действий и моделируете узлы как состояния, а действия как переход между этими действиями. Вместо того, чтобы думать о «Получить дом» в качестве основной задачи, рассмотрим «Начало» и «Иметь дом» как 2 узла, а «Получить дом» как переход между ними. Переходное действие «Получить дом» может быть разложено на график, который представляет промежуточные состояния и действия (то есть узлы и ребра). Вы должны быть в состоянии разложить проблему по мере необходимости и рассчитать кратчайший путь из полученного графика.

Answer 2

С риском быть слишком разборчивым, это может показаться классической проблемой Critical Path Method (CPM), а не PERT. PERT предполагает худшее, лучшее и среднее время завершения для каждой задачи, в то время как Жюль указал только один раз для каждой задачи. Тем не менее, вы можете использовать линейное программирование, чтобы найти критический путь и получить самое раннее время начала, самое позднее время окончания и т. Д. Для каждого действия. Вот полезное одностраничное описание подхода.

Answer 3

Возможно, вы ищете алгоритм планирования частичного заказа: http://blackcat.brynmawr.edu/~dkumar/UGAI/planning.html#algorithms

Answer 4

Я думаю, что делал это давным-давно в контексте диаграмм PERT.

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

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

Answer 5

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

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

Затем вернитесь к тем действиям, которые зависят только от задач, которые вы "решили", и рассчитайте их общее время.

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

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

Answer 6

Топологическая сортировка