编辑:下面是一个使用高改进Dijkstra算法的妥善解决办法:
Dijkstra算法是用于找到最短路径,给定一个映射(一个Graph Abstract),它是一系列节点(通常是位置,但是对于这个例子,假设它们是Actions),它们通过弧相互连接(在这种情况下,而不是距离,每个弧将有一个'值')
这里是本质上的结构。
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
}
End edit。
我对这个问题有点困惑,但...
如果你的动作数量有限,仅此而已,那么总是挑最值的动作,除非冷却时间也没有还没有见过。
听起来像是你想这样的事情(在伪代码):
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?
}
}
最多可以有多少种不同类型的动作? – aram90 2013-03-21 21:01:29
实际上不会超过12. – user2196830 2013-03-21 21:13:06