Algorithm for optimally choosing actions to perform a task
- by Jules
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> dependencies; }
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" and "Get cement", etcetera.
The total time is the sum of all the times of the actions required to perform. 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)
