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

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

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

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

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

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

Обратите внимание также, что зависимости могут быть круговыми. Например, "Деньги"-> "Задание"-> "Автомобиль"-> "Деньги". Это не проблема для нас, мы просто выбираем все "Деньги", "Задание" и "Автомобиль". Общее время является просто суммой времени этих 3 вещей.

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

Позволить 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)

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

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

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

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