编辑:这是使用高度修改的 Dijkstra 算法的正确解决方案:
Dijkstra 算法用于找到最短路径,给定一个(Graph Abstract 的)地图,它是一系列节点(通常是位置,但对于这个例子,假设它们是动作),它们通过弧相互连接(在在这种情况下,每条弧线将有一个“值”而不是距离)
这是本质上的结构。
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'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
}
结束编辑。
我对这个问题有点困惑,但是......
如果您的行动数量有限,仅此而已,那么请始终选择价值最高的行动,除非尚未达到冷却时间。
听起来你想要这样的东西(在伪代码中):
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?
}
}