优化带有冷却时间的 Action 顺序的算法

Question

我可以从“ Action ”列表中选择每秒执行一次。列表中的每个 Action 都有一个数值表示它的值(value)，还有一个值表示它的“冷却时间”——再次使用该 Action 之前我必须等待的秒数。该列表可能看起来像这样:

• Action A 的值为 1，冷却时间为 2 秒
• Action B 的值为 1.5，冷却时间为 3 秒
• Action C 的值为 2，冷却时间为 5 秒
• 行动 D 的值为 3，冷却时间为 10 秒

所以在这种情况下，顺序 ABA 的总值为 (1+1.5+1) = 3.5，这是可以接受的，因为第一次使用 A 发生在 1 秒，最后一次使用 A 发生在3秒，然后两者之差大于等于A的冷却时间，2秒。 AAB 的顺序将不起作用，因为你只间隔一秒执行 A，少于冷却时间。

我的问题是尝试优化操作的使用顺序，使一定数量的操作的总值(value)最大化。显然，如果您只使用一个 Action ，则最佳顺序是执行 Action D，总值(value)为 3。两个 Action 的最大值来自于执行 CD 或 DC，总值(value)为 5。它当您总共执行 10 次、20 次或 100 次操作时，情况会变得更加复杂。我无法找到一种方法来优化操作顺序而不强制执行它，这使得它的复杂性与您要优化顺序的操作总数成指数关系。总共超过 15 个就变得不可能了。

那么，有没有什么方法可以更简单地找到最佳时间呢？有研究过这个问题吗？我想可能有某种加权图类型的算法可以解决这个问题，但我不知道它是如何工作的，更不用说如何实现它了。

很抱歉，如果这让人感到困惑——这在概念上有点奇怪，我找不到更好的方式来构建它。

Answer 1

编辑:这是使用经过高度修改的 Dijkstra 算法的正确解决方案:

Dijkstra 算法用于找到最短路径，给定一个 map (图摘要)，它是一系列节点(通常是位置，但对于这个例子，我们假设它们是 Action )，它们通过以下方式相互连接弧(在这种情况下，每条弧都有一个“值”，而不是距离)

这是本质上的结构。

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
}

我们可以使用此数据类型制作所有可行选项的 map ，以便根据查看每条路径的最终总数来获得最佳解决方案。因此，您寻找模式的时间越长，找到最佳路径的可能性就越大。

map 上道路的每一段都有一个距离，代表它的值(value)，道路上的每一站都是一秒钟的标记，因为那是决定去哪里的时间(采取什么行动执行)下一步。 为简单起见，假设 A 和 B 是唯一可行的选项。na 表示无 Action ，因为没有可用的 Action 。如果你旅行了 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，因为它的值(value)是最高的。因此，处理这种 Action 组合的最佳模式是(至少在分析了 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'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
}

结束编辑。

我对这个问题有点困惑，但是......

如果您的 Action 数量有限，仅此而已，那么请始终选择具有最大值(value)的 Action ，除非尚未达到冷却时间。

听起来你想要这样的东西(伪代码):

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