Algorithm for optimizing the order of actions with cooldowns

Question

I can choose from a list of "actions" to perform one once a second. Each action on the list has a numerical value representing how much it's worth, and also a value representing its "cooldown" -- the number of seconds I have to wait before using that action again. The list might look something like this:

• Action A has a value of 1 and a cooldown of 2 seconds
• Action B has a value of 1.5 and a cooldown of 3 seconds
• Action C has a value of 2 and a cooldown of 5 seconds
• Action D has a value of 3 and a cooldown of 10 seconds

So in this situation, the order ABA would have a total value of (1+1.5+1) = 3.5, and it would be acceptable because the first use of A happens at 1 second and the final use of A happens at 3 seconds, and then difference between those two is greater than or equal to the cooldown of A, 2 seconds. The order AAB would not work because you'd be doing A only a second apart, less than the cooldown.

My problem is trying to optimize the order in which the actions are used, maximizing the total value over a certain number of actions. Obviously the optimal order if you're only using one action would be to do Action D, resulting in a total value of 3. The maximum value from two actions would come from doing CD or DC, resulting in a total value of 5. It gets more complicated when you do 10 or 20 or 100 total actions. I can't find a way to optimize the order of actions without brute forcing it, which gives it complexity exponential on the total number of actions you want to optimize the order for. That becomes impossible past about 15 total.

So, is there any way to find the optimal time with less complexity? Has this problem ever been researched? I imagine there could be some kind of weighted-graph type algorithm that works on this, but I have no idea how it would work, let alone how to implement it.

Sorry if this is confusing -- it's kind of weird conceptually and I couldn't find a better way to frame it.

Answer 1

EDIT: Here is a proper solution using a highly modified Dijkstra's Algorithm:

Dijkstra's algorithm is used to find the shortest path, given a map (of a Graph Abstract), which is a series of Nodes(usually locations, but for this example let's say they are Actions), which are inter-connected by arcs(in this case, instead of distance, each arc will have a 'value')

Here is the structure in essence.

Graph{//in most implementations these are not Arrays, but Maps. Honestly, for your needs you don't a graph, just nodes and arcs... this is just used to keep track of them.
node[] nodes;
arc[] arcs;
}
Node{//this represents an action
arc[] options;//for this implementation, this will always be a list of all possible Actions to use.
float value;//Action value
}
Arc{
node start;//the last action used
node end;//the action after that
dist=1;//1 second
}

We can use this datatype to make a map of all of the viable options to take to get the optimal solution, based on looking at the end-total of each path. Therefore, the more seconds ahead you look for a pattern, the more likely you are to find a very-optimal path.

Every segment of a road on the map has a distance, which represents it's value, and every stop on the road is a one-second mark, since that is the time to make the decision of where to go (what action to execute) next. For simplicity's sake, let's say that A and B are the only viable options. na means no action, because no actions are avaliable. If you are travelling for 4 seconds(the higher the amount, the better the results) your choices are...

A->na->A->na->A
B->na->na->B->na
A->B->A->na->B
B->A->na->B->A
...

there are more too, but I already know that the optimal path is B->A->na->B->A, because it's value is the highest. So, the established best-pattern for handling this combination of actions is (at least after analyzing it for 4 seconds) B->A->na->B->A This will actually be quite an easy recursive algorithm.

    /*
     cur is the current action that you are at, it is a Node. In this example, every other action is seen as a viable option, so it's as if every 'place' on the map has a path going to every other path.
     numLeft is the amount of seconds left to run the simulation. The higher the initial value, the more desirable the results.

This won't work as written, but will give you a good idea of how the algorithm works.
*/
function getOptimal(cur,numLeft,path){
  if(numLeft==0){
    var emptyNode;//let's say, an empty node wiht a value of 0.
    return emptyNode;
  }
  var best=path;
  path.add(cur);
  for(var i=0;i<cur.options.length;i++){
    var opt=cur.options[i];//this is a COPY
    if(opt.timeCooled<opt.cooldown){
      continue;
    }
    for(var i2=0;i2<opt.length;i2++){
      opt[i2].timeCooled+=1;//everything below this in the loop is as if it is one second ahead
    }
    var potential=getOptimal(opt[i],numLeft-1,best);
    if(getTotal(potential)>getTotal(cur)){best.add(potential);}//if it makes it better, use it! getTotal will sum up the values of an array of nodes(actions)
  }
  return best;
}
function getOptimalExample(){
  log(getOptimal(someNode,4,someEmptyArrayOfNodes));//someNode will be A or B
}

End edit.

I'm a bit confused on the question but...

If you have a limited amount of actions, and that's it, then always pick the action with the most value, unless the cooldown hasn't been met yet.

Sounds like you want something like this (in pseudocode):

function getOptimal(){
var a=[A,B,C,D];//A,B,C, and D are actions
a.sort()//(just pseudocode. Sort the array items by how much value they have.)
var theBest=null;
for(var i=0;i<a.length;++i){//find which action is the most valuable
     if(a[i].timeSinceLastUsed<a[i].cooldown){
        theBest=a[i];
        for(...){//now just loop through, and add time to each OTHER Action for their timeSinceLastUsed...
             //...
         }//That way, some previously used, but more valuable actions will be freed up again.
        break;
    }//because a is worth the most, and you can use it now, so why not?
}
}

Answer 2

EDIT: After rereading your problem a bit more, I see that the weighted scheduling algorithm would need to be tweaked to fit your problem statement; in our case we only want to take those overlapping actions out of the set that match the class of the action we selected, and those that start at the same point in time. IE if we select a1, we want to remove a2 and b1 from the set but not b2.

This looks very similar to the weighted scheduling problem which is discussed in depth in this pdf. In essence, the weights are your action's values and the intervals are (starttime,starttime+cooldown). The dynamic programming solution can be memoized which makes it run in O(nlogn) time. The only difficult part will be modifying your problem such that it looks like the weighted interval problem which allows us to then utilize the predetermined solution.

Because your intervals don't have set start and end times (IE you can choose when to start a certain action), I'd suggest enumerating all possible start times for all given actions assuming some set time range, then using these static start/end times with the dynamic programming solution. Assuming you can only start an action on a full second, you could run action A for intervals (0-2,1-3,2-4,...), action B for (0-3,1-4,2-5,...), action C for intervals (0-5,1-6,2-7,...) etc. You can then use union the action's sets to get a problem space that looks like the original weighted interval problem:

|---1---2---3---4---5---6---7---| time
|{--a1--}-----------------------| v=1
|---{--a2---}-------------------| v=1
|-------{--a3---}---------------| v=1
|{----b1----}-------------------| v=1.5
|---{----b2-----}---------------| v=1.5
|-------{----b3-----}-----------| v=1.5
|{--------c1--------}-----------| v=2
|---{--------c2---------}-------| v=2
|-------{-------c3----------}---| v=2
etc...