編輯:下面是一個使用高改進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