Algorithm for optimally choosing actions to perform a task

There are two data types: tasks and actions. An action costs a certain time to complete, and a set of tasks this actions consists of. A task has a set of actions, and our job is to choose one of them. So:

class Task { Set<Action> choices; }
class Action { float time; Set<Task> de开发者_StackOverflow中文版pendencies; }

For example the primary task could be "Get a house". The possible actions for this task: "Buy a house" or "Build a house". The action "Build a house" costs 10 hours and has the dependencies "Get bricks" (which may cost 6 hours) and "Get cement" (which costs 9 hours), etcetera.

The total time is the sum of all the times of the actions required to perform (in this case 10+6+9 hours). We want to choose actions such that the total time is minimal.

Note that the dependencies can be diamond shaped. For example "Get bricks" could require "Get a car" (to transport the bricks) and "Get cement" would also require a car. Even if you do "Get bricks" and "Get cement" you only have to count the time it takes to get a car once.

Note also that the dependencies can be circular. For example "Money" -> "Job" -> "Car" -> "Money". This is no problem for us, we simply select all of "Money", "Job" and "Car". The total time is simply the sum of the time of these 3 things.

Mathematical description:

Let actions be the chosen 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)

I'm interested in an optimal solution but also in an approximate solution. Perhaps some kind of dynamic programming can help there? If the problem is tree structured then dynamic programming can give an optimal solution in polynomial time, but diamond structures seem to make the problem much more difficult. If you have an algorithm but it doesn't work if there are cycles, do post it! I can probably still learn a lot from it.

The boxes represent tasks and the circles represent actions (the time to perform the action is in the circle). An action has a line to a task if that task is a dependency for the action. Here's the description of the problem again in terms of pictures: if a rectangle (=task) is chosen, then one of the circles (=actions) inside must be chosen. If a circle is chosen, then all of the connected rectangles must be chosen. The goal is to minimize the sum of the numbers in the chosen circles.

An optimal solution in this case is to choose the action with time 2 in the top task, and the actions with time 1 in the bottom tasks. The total time is 2+1+1=4. In this case there are 2 optimal solutions. The second solution is to choose the action with time 3 in the top task, and the action with time 1 in the bottom right task. The total time is 3+1=4 again. If we choose the action with time 3 in the top task we do not have to perform the left bottom task, because there is no line between the action with time 3 and the left bottom task.

I apologize for the crappy drawing ;) And two more examples (the optimal solution for each has been indicated with blue, and the primary task has been indicated with grey):

---

You could model this as a graph and use a shortest path algorithm to find the solution. Each of the Tasks would be a node and the Actions would be edges in the graph.

In fact it will probably be easier to represent nodes as states and edges as the actions needed to as edges to transition between states.

If you consider a task as simply an aggregate of actions and you model the nodes as states and the actions as transition between those actions. Instead of thinking of "Get a house" as the primary task, consider "Start" and "Have a house" as 2 nodes and "Get a house" as a transition between them. The "Get a house" transition action can be decomposed into a graph that represents the intermediate states and actions (i.e. nodes and edges). You should be able to decompose the problem down as far as necessary and calculate the shortest path from the resulting graph.

---

You may be looking for the Partial Order Planning algorithm: http://blackcat.brynmawr.edu/~dkumar/UGAI/planning.html#algorithms

---

I think I did this ages ago in the context of PERT charts.

How big are these networks, and how frequently do you need to solve them? You don't actually have a performance problem until you see one.

I would use dynamic programming. I wouldn't assume shared subtasks would be a problem until I found out from experience that they were.

---

At risk of being overly picky, this would appear to be a classic Critical Path Method (CPM) problem rather than PERT. PERT assumes a worst, best, and average completion time for each task while Jules has specified only one time for each task. That said, you can use linear programming to find the critical path and produce earliest start times, latest finish times, etc for each activity. Here's a useful one page description of the approach.

---

Topological Sorting

---

I believe that each possible execution path must end with a Task whose set of choices consists entirely of Actions with no dependencies.

If that is true, then you can easily determine the minimal time for each such Task.

Then work backwards to the Actions that only depend upon Tasks that you have "solved", and calculate their total times.

Work backwards through all of the possible paths until you get to the beginning.

The run time should be O(number of nodes in graph), which should be the same run time that it took to generate the graph.