Algorytm optymalizacji kolejności działań z czasami odnowienia

Question

Mogę wybrać z listy "czynności", aby wykonać jedną raz na sekundę. Każde działanie na liście ma wartość liczbową określającą, ile jest warta, a także wartość reprezentującą jego "czas regeneracji" - liczbę sekund, które muszę poczekać, zanim ponownie wykorzystam tę akcję. Lista może wyglądać tak:

• działanie A ma wartość 1, i odnawianie 2 sekund
• Działanie B ma wartość 1,5 i czas chłodzenia od 3 sekund
• Działanie C ma wartość 2 i ponownego użycia 5 sekund
• Działanie D ma wartość 3, a czas chłodzenia 10 sekund

Tak więc w tej sytuacji, ABA kolejność będzie miał całkowitą wartość (1 + 1,5 + 1) = 3,5, i byłoby to do zaakceptowania, ponieważ pierwszy u se A następuje po 1 sekundzie, a ostateczne użycie A następuje po 3 sekundach, a następnie różnica między tymi dwoma jest większa lub równa odnowie A, 2 sekundy. Rozkaz AAB nie zadziałałby, ponieważ robiłbyś A tylko sekundę od siebie, mniej niż czas odnowienia.

Mój problem polega na próbie optymalizacji kolejności użycia działań, maksymalizując całkowitą wartość w stosunku do określonej liczby czynności. Oczywiście optymalną kolejnością, jeśli używasz tylko jednej akcji, byłoby wykonanie działania D, co daje łączną wartość 3. Maksymalna wartość z dwóch akcji pochodzi z CD lub DC, co daje łączną wartość równą 5. komplikuje się, gdy wykonasz 10 lub 20 lub 100 wszystkich działań. Nie mogę znaleźć sposobu na zoptymalizowanie kolejności działań bez brutalnego wymuszania jej, co daje jej złożoność wykładniczą na całkowitej liczbie działań, które chcesz zoptymalizować. To staje się niemożliwe za około 15 razem.

Czy istnieje sposób na znalezienie optymalnego czasu przy mniejszej złożoności? Czy ten problem został kiedykolwiek zbadany? Wyobrażam sobie, że może istnieć jakiś algorytm typu ważonego wykresu, który pracuje nad tym, ale nie mam pojęcia, jak to zadziała, nie mówiąc już, jak go zaimplementować.

Przepraszam, jeśli to jest mylące - jest to dość dziwaczne koncepcyjnie i nie mogłem znaleźć lepszego sposobu na jego oprawienie.

Answer 1

EDYCJA: Po ponownym przeczytaniu twojego problemu, widzę, że ważony algorytm planowania musiałby zostać zmodyfikowany, aby pasował do twojego problemu; w naszym przypadku chcemy tylko wziąć te zachodzące na siebie działania poza zestaw, które pasują do klasy wybranej przez nas akcji i tych, które zaczynają się w tym samym momencie. IE, jeśli wybierzemy a1, chcemy usunąć z zestawu a2 i b1, ale nie b2.

Wygląda to bardzo podobnie do ważonego problemu z harmonogramem, który omówiono szczegółowo w części in this pdf. W istocie ciężary są wartościami waszej akcji, a przedziały to (czas rozpoczęcia, czas rozpoczęcia + czas odnowienia). Dynamiczne rozwiązanie programistyczne można zapamiętać, co sprawia, że ​​działa on w czasie O (nlogn). Jedyną trudną częścią będzie modyfikowanie twojego problemu tak, aby wyglądał jak problem z ważonym interwałem, który pozwala nam wykorzystać to z góry określone rozwiązanie.

Ponieważ twoje interwały nie mają ustawionego czasu rozpoczęcia i zakończenia (IE możesz wybrać, kiedy rozpocząć określoną akcję), sugerowałbym wyliczenie wszystkich możliwych czasów rozpoczęcia dla wszystkich podjętych działań przy założonym pewnym zakresie czasu, a następnie użycie te statyczne czasy rozpoczęcia/zakończenia dzięki dynamicznemu rozwiązaniu programistycznemu. Zakładając, że możesz rozpocząć akcję tylko na pełnej sekundzie, możesz wykonać akcję A dla przedziałów (0-2,1-3,2-4, ...), akcji B dla (0-3,1-4,2) -5, ...), akcja C dla przedziałów (0-5,1-6,2-7, ...) itp.Następnie można użyć unii ustawia akcję, aby uzyskać przestrzeń problemu, który wygląda jak oryginalny ważona interwału problemu:

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

Answer 2

EDIT: Tutaj jest właściwe rozwiązanie przy użyciu wysoce zmodyfikowaną Algorytm Dijkstry:

Algorytm Dijkstry jest używane do znalezienia najkrótszej ścieżki, biorąc pod uwagę mapę (z Graph Abstract), która jest serią Nodes (zazwyczaj lokalizacje, ale dla tego przykładu powiedzmy, że są Actions), które są połączone ze sobą za pomocą łuków (w tym przypadku zamiast odległości, każdy łuk będzie miał "wartość")

Oto struktura w istocie.

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 
} 

Możemy użyć tego typu danych do tworzenia mapy wszystkich żywych opcji podjąć, aby uzyskać optymalne rozwiązanie, na podstawie patrząc na koniec sumie każdej ścieżki. Dlatego im więcej sekund szukacie wzoru, tym bardziej prawdopodobne jest znalezienie bardzo optymalnej ścieżki.

Każdy odcinek drogi na mapie ma odległość, która reprezentuje jego wartość, a każdy postój na drodze jest jednotosekundowy, ponieważ jest to czas, aby podjąć decyzję, dokąd się udać (jakie działanie wykonać). Dla uproszczenia załóżmy, że A i B są jedynymi realnymi opcjami. na oznacza brak działania, ponieważ żadne czynności nie są dostępne. Jeśli podróżujesz do 4 sekund (im wyższa wartość, tym lepsze wyniki) Twoje wybory są ...

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

istnieje więcej też, ale już wiem, że optymalna ścieżka jest B-> A -> na-> B-> A, ponieważ jego wartość jest najwyższa. Tak więc ustalony najlepszy wzorzec do radzenia sobie z tą kombinacją działań jest (przynajmniej po analizie go przez 4 sekundy). B-> A-> na-> B-> A To rzeczywiście będzie dość łatwy algorytm rekursywny.

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

Zakończ edycję.

Jestem nieco mylić w tej kwestii, ale ...

Jeśli masz ograniczoną ilość działań, i to wszystko, a potem zawsze wybrać działanie z największą wartość, chyba że nie ma cooldown już się spotkałem.

Brzmi jak chcesz coś takiego (w Pseudokod):

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

Answer 3

zawsze wybierać dostępne akcja warta najwięcej punktów.