tło
Ten obraz ilustruje problem:
Mogę kontrolować czerwone kółko. Cele to niebieskie trójkąty. Czarne strzałki wskazują kierunek, w którym będą się poruszać cele.
Chcę zebrać wszystkie cele w minimalnej liczbie kroków.
W każdej turze muszę przejść o 1 krok w lewo / w prawo / w górę lub w dół.
W każdej turze cele będą również przesuwać się o 1 stopień zgodnie ze wskazówkami pokazanymi na planszy.
Próbny
Umieściłem grywalną wersję demonstracyjną problemu tutaj w Google Appengine .
Byłbym bardzo zainteresowany, gdyby ktokolwiek mógł pokonać docelowy wynik, ponieważ pokazałoby to, że mój obecny algorytm jest nieoptymalny. (Wiadomość z gratulacjami powinna zostać wydrukowana, jeśli Ci się uda!)
Problem
Mój obecny algorytm bardzo źle skaluje się z liczbą celów. Czas rośnie wykładniczo i dla 16 ryb to już kilka sekund.
Chciałbym obliczyć odpowiedź dla planszy o rozmiarach 32 * 32 i 100 ruchomych celów.
Pytanie
Jaki jest wydajny algorytm (najlepiej w JavaScript) do obliczania minimalnej liczby kroków, aby zebrać wszystkie cele?
Co próbowałem
Moje obecne podejście opiera się na memoizowaniu, ale jest bardzo powolne i nie wiem, czy zawsze wygeneruje najlepsze rozwiązanie.
Rozwiązuję podproblem „jaka jest minimalna liczba kroków, aby zebrać dany zestaw celów i skończyć na określonym celu?”.
Podproblem jest rozwiązywany rekurencyjnie, sprawdzając każdy wybór pod kątem odwiedzenia poprzedniego celu. Zakładam, że zawsze optymalnie jest zebrać poprzedni podzbiór celów tak szybko, jak to możliwe, a następnie jak najszybciej przejść z pozycji, w której skończyłeś, do obecnego celu (chociaż nie wiem, czy jest to prawidłowe założenie).
Powoduje to obliczenie n * 2 ^ n stanów, które rosną bardzo szybko.
Aktualny kod pokazano poniżej:
var DX=[1,0,-1,0];
var DY=[0,1,0,-1];
// Return the location of the given fish at time t
function getPt(fish,t) {
var i;
var x=pts[fish][0];
var y=pts[fish][1];
for(i=0;i<t;i++) {
var b=board[x][y];
x+=DX[b];
y+=DY[b];
}
return [x,y];
}
// Return the number of steps to track down the given fish
// Work by iterating and selecting first time when Manhattan distance matches time
function fastest_route(peng,dest) {
var myx=peng[0];
var myy=peng[1];
var x=dest[0];
var y=dest[1];
var t=0;
while ((Math.abs(x-myx)+Math.abs(y-myy))!=t) {
var b=board[x][y];
x+=DX[b];
y+=DY[b];
t+=1;
}
return t;
}
// Try to compute the shortest path to reach each fish and a certain subset of the others
// key is current fish followed by N bits of bitmask
// value is shortest time
function computeTarget(start_x,start_y) {
cache={};
// Compute the shortest steps to have visited all fish in bitmask
// and with the last visit being to the fish with index equal to last
function go(bitmask,last) {
var i;
var best=100000000;
var key=(last<<num_fish)+bitmask;
if (key in cache) {
return cache[key];
}
// Consider all previous positions
bitmask -= 1<<last;
if (bitmask==0) {
best = fastest_route([start_x,start_y],pts[last]);
} else {
for(i=0;i<pts.length;i++) {
var bit = 1<<i;
if (bitmask&bit) {
var s = go(bitmask,i); // least cost if our previous fish was i
s+=fastest_route(getPt(i,s),getPt(last,s));
if (s<best) best=s;
}
}
}
cache[key]=best;
return best;
}
var t = 100000000;
for(var i=0;i<pts.length;i++) {
t = Math.min(t,go((1<<pts.length)-1,i));
}
return t;
}
Co myślałem
Niektóre opcje, nad którymi się zastanawiałem, to:
Buforowanie wyników pośrednich. Obliczanie odległości powtarza wiele symulacji, a wyniki pośrednie mogą zostać zapisane w pamięci podręcznej.
Jednak nie sądzę, żeby to powstrzymało wykładniczą złożoność.Algorytm wyszukiwania A *, chociaż nie jest dla mnie jasne, jaka byłaby odpowiednia dopuszczalna heurystyka i jak skuteczne byłoby to w praktyce.
Zbadanie dobrych algorytmów dla problemu komiwojażera i zobacz, czy mają zastosowanie do tego problemu.
Próba udowodnienia, że problem jest NP-trudny, a zatem nieuzasadnione poszukiwanie optymalnej odpowiedzi.