Algorithm for optimizing the order of actions with cooldowns

I can select “actions” from the list to execute once per second. Each action in the list has a numerical value representing how much it costs, as well as a value representing its "cooldown" - the number of seconds that I must wait before using this action again. The list might look something like this:

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

Thus, in this situation, the ABA order would have a total value of (1 + 1.5 + 1) = 3.5, and this would be acceptable, since the first use of A occurs after 1 second, and the final use of A occurs at 3 seconds and then the difference between these two values ​​is greater than or equal to A cooldown, 2 seconds. The AAB order will not work, because you will make A for only a second, less than the recovery time.

My problem is trying to optimize the order in which actions are used, maximizing the total value over a certain number of actions. Obviously, the optimal order if you use only one action is to perform action D, resulting in a total value of 3. The maximum value of the two actions will come from CD or DC, resulting in a total value of 5. becomes more complicated when you perform 10 or 20 or 100 complete actions. I can’t find a way to optimize the order of actions without rough work, which makes it exponentially difficult in terms of the total number of actions that you want to optimize for. It becomes impossible in the past around 15.

, ? - ? , - , , , , , .

, - , .

+5
3

EDIT: :

, ( ), ( , , ), ( "" )

.

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
}

, , , , . , , , .

, , ​​ , , ( ).   , A B - . na , . 4 ( , ), ...

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

, , B- > A- > na- > B- > A, . , ( , 4 ) B- > A- > na- > B- > A   .

    /*
     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 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 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
}

.

, ...

, , .

, - ( ):

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?
}
}
+3

EDIT: , ; , , , . IE, a1, a2 b1 , b2.

, "rel=" nofollow" > pdf. , - ( , + ). , O (nlogn) . , , .

(IE , - ), , , / . , , A (0-2,1-3,2-4,...), B (0-3,1-4,2 -5,...), C (0-5,1-6,2-7,...) .. , :

|---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... 
+1

, .

0

All Articles