Jak znaleźć najkrótszą drogę między 100 ruchomymi celami? (Zawiera demo na żywo).

89

tło

Ten obraz ilustruje problem: square_grid_with_arrows_giving_directions

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:

  1. 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ść.

  2. Algorytm wyszukiwania A *, chociaż nie jest dla mnie jasne, jaka byłaby odpowiednia dopuszczalna heurystyka i jak skuteczne byłoby to w praktyce.

  3. Zbadanie dobrych algorytmów dla problemu komiwojażera i zobacz, czy mają zastosowanie do tego problemu.

  4. Próba udowodnienia, że ​​problem jest NP-trudny, a zatem nieuzasadnione poszukiwanie optymalnej odpowiedzi.

javascript algorithm graph-theory Peter de Rivaz
źródło
1
Wybrałbym # 4, a następnie # 3: Przy wystarczająco dużych deskach całkiem dobrze naśladuje TSP.
John Dvorak
2
O ile wiem, TSP jest NP-twardy z metryką euklidesową, a także metryką manhattańską (kwadratowa siatka).
John Dvorak
1
Jeśli zrobisz to przez proste przeszukiwanie drzewa, tak, będzie to wykładnicze. Jeśli jednak na każdym kroku znajdziesz przyzwoitą heurystykę, może nie być ona optymalna, ale może być bardzo dobra. Jedną z możliwych heurystów byłoby przyjrzenie się obecnemu zestawowi ryb, do którego można dotrzeć najszybciej? Druga może być heurystyka, do których 2 ryb mogę dotrzeć najszybciej?
Mike Dunlavey
2
@MikeDunlavey, który odpowiadałby zachłannemu algorytmowi TSP i sprawdza się bardzo dobrze w praktyce. Wybranie najbliższej ryby wydaje się dobrym pomysłem
John Dvorak
1
+1 za jedno z najlepszych pytań, jakie ostatnio widziałem, zarówno dotyczące treści, jak i struktury.
surfitscrollit

Odpowiedzi:

24

Przeszukałeś literaturę? Znalazłem te dokumenty, które wydają się analizować twój problem:

AKTUALIZACJA 1:

Wydaje się, że powyższe dwa artykuły koncentrują się na ruchu liniowym miernika euklidesowego.

uldall
źródło
Dzięki - nie widziałem tych dokumentów, ale wyglądają na bardzo istotne. Zobaczę, czy uda mi się dostosować algorytm genetyczny do pracy w moim przypadku i porównać go z wynikami z metody brutalnej siły.
Peter de Rivaz,
13

Chciwa metoda

Jedno podejście sugerowane w komentarzach polega na tym, aby najpierw przejść do najbliższego celu.

Opublikowałem wersję demo, która zawiera koszt obliczony tutaj tą zachłanną metodą .

Kod to:

function greedyMethod(start_x,start_y) {
  var still_to_visit = (1<<pts.length)-1;
  var pt=[start_x,start_y];
  var s=0;
  while (still_to_visit) {
    var besti=-1;
    var bestc=0;
    for(i=0;i<pts.length;i++) {
      var bit = 1<<i;
      if (still_to_visit&bit) {
        c = fastest_route(pt,getPt(i,s));
        if (besti<0 || c<bestc) {
          besti = i;
          bestc = c;
        }
      }
    }
    s+=c;
    still_to_visit -= 1<<besti;
    pt=getPt(besti,s);
  }
  return s;
}

Dla 10 celów jest to około dwa razy większa odległość od optymalnej, ale czasami znacznie większa (np. * 4), a czasami nawet osiąga optymalną.

To podejście jest bardzo wydajne, więc mogę pozwolić sobie na kilka cykli, aby poprawić odpowiedź.

Następnie rozważam użycie metod kolonii mrówek, aby sprawdzić, czy mogą skutecznie zbadać przestrzeń rozwiązania.

Metoda kolonii mrówek

Ant metoda kolonia wydaje się działać dobrze niezwykłą dla tego problemu. Odnośnik w tej odpowiedzi porównuje teraz wyniki przy użyciu metody chciwej i kolonii mrówek.

Chodzi o to, że mrówki wybierają swoją trasę prawdopodobnie w oparciu o aktualny poziom feromonu. Po każdych 10 próbach umieszczamy dodatkowe feromony wzdłuż najkrótszej ścieżki, którą znaleźli.

function antMethod(start_x,start_y) {
  // First establish a baseline based on greedy
  var L = greedyMethod(start_x,start_y);
  var n = pts.length;
  var m = 10; // number of ants
  var numrepeats = 100;
  var alpha = 0.1;
  var q = 0.9;
  var t0 = 1/(n*L);

  pheromone=new Array(n+1); // entry n used for starting position
  for(i=0;i<=n;i++) {
    pheromone[i] = new Array(n);
    for(j=0;j<n;j++)
      pheromone[i][j] = t0; 
  }

  h = new Array(n);
  overallBest=10000000;
  for(repeat=0;repeat<numrepeats;repeat++) {
    for(ant=0;ant<m;ant++) {
      route = new Array(n);
      var still_to_visit = (1<<n)-1;
      var pt=[start_x,start_y];
      var s=0;
      var last=n;
      var step=0;
      while (still_to_visit) {
        var besti=-1;
        var bestc=0;
        var totalh=0;
        for(i=0;i<pts.length;i++) {
          var bit = 1<<i;
          if (still_to_visit&bit) {
            c = pheromone[last][i]/(1+fastest_route(pt,getPt(i,s)));
            h[i] = c;
            totalh += h[i];
            if (besti<0 || c>bestc) {
              besti = i;
              bestc = c;
            }
          }
        }
        if (Math.random()>0.9) {
          thresh = totalh*Math.random();
          for(i=0;i<pts.length;i++) {
            var bit = 1<<i;
            if (still_to_visit&bit) {
              thresh -= h[i];
              if (thresh<0) {
                besti=i;
                break;
              }
            }
          }
        }
        s += fastest_route(pt,getPt(besti,s));
        still_to_visit -= 1<<besti;
        pt=getPt(besti,s);
        route[step]=besti;
        step++;
        pheromone[last][besti] = (1-alpha) * pheromone[last][besti] + alpha*t0;
        last = besti;
      }
      if (ant==0 || s<bestantscore) {
        bestroute=route;
        bestantscore = s;
      }
    }
    last = n;
    var d = 1/(1+bestantscore);
    for(i=0;i<n;i++) {
      var besti = bestroute[i];
      pheromone[last][besti] = (1-alpha) * pheromone[last][besti] + alpha*d;
      last = besti;
    }
    overallBest = Math.min(overallBest,bestantscore);
  }
  return overallBest;
}

Wyniki

Ta metoda kolonii mrówek przy użyciu 100 powtórzeń 10 mrówek jest nadal bardzo szybka (37 ms dla 16 celów w porównaniu z 3700 ms dla wyczerpującego wyszukiwania) i wydaje się bardzo dokładna.

Poniższa tabela przedstawia wyniki dla 10 prób z 16 celami:

   Greedy   Ant     Optimal
   46       29      29
   91       38      37
  103       30      30
   86       29      29
   75       26      22
  182       38      36
  120       31      28
  106       38      30
   93       30      30
  129       39      38

Metoda mrówek wydaje się znacznie lepsza niż chciwa i często bardzo bliska optymalnej.

Peter de Rivaz
źródło
Ładny. Być może nie uzyskasz jeszcze optymalnych wyników z wyczerpujących poszukiwań (lub prawdopodobnie nigdy ze względu na ich trudność!), Ale byłoby interesujące zobaczyć, jak kolonia mrówek skaluje się z rozmiarem planszy (32x32) przy tej samej liczbie celów.
timxyz
8

Problem można przedstawić za pomocą uogólnionego problemu komiwojażera, a następnie przekształcić go w typowy problem komiwojażera. To dobrze zbadany problem. Możliwe, że najbardziej efektywne rozwiązania problemu PO nie są bardziej wydajne niż rozwiązania TSP, ale w żadnym wypadku nie są pewne (prawdopodobnie nie wykorzystuję niektórych aspektów struktury problemu PO, które pozwoliłyby na szybsze rozwiązanie , np. cykliczność). Tak czy inaczej, jest to dobry punkt wyjścia.

Od C. Noon i J. Bean, Efektywna transformacja uogólnionego problemu komiwojażera :

Ogólny problem komiwojażera (GTSP) jest użytecznym modelem dla problemów związanych z decyzji wyboru i kolejności. Asymetryczna wersja problemu jest określona na wykresie skierowanym z węzłami N, łączącymi łuki A i wektorem odpowiadających im kosztów łuku c. Węzły są wstępnie zgrupowane w m wzajemnie wykluczających się i wyczerpujących zestawów. Łuki łączące są definiowane tylko między węzłami należącymi do różnych zestawów, to znaczy nie ma łuków intrasetowych. Każdy zdefiniowany łuk ma odpowiadający mu koszt nieujemny. GTSP można określić jako problem znalezienia minimalnego kosztu cyklu m-arc, który obejmuje dokładnie jeden węzeł z każdego zestawu węzłów .

W przypadku problemu PO:

  • Każdy członek Nto lokalizacja określonej ryby w określonym czasie. Przedstaw to jako (x, y, t), gdzie (x, y)jest współrzędną siatki i tjest to czas, w którym ryba będzie na tej współrzędnej. W przypadku ryby znajdującej się najbardziej po lewej stronie w przykładzie OP pierwsze z nich (od 1) to: (3, 9, 1), (4, 9, 2), (5, 9, 3)gdy ryba porusza się w prawo.
  • Dla każdego członka N zwróćmy fish(n_i)identyfikator ryby reprezentowanej przez węzeł. Dla dowolnych dwóch członków N możemy obliczyć manhattan(n_i, n_j)odległość manhattanu między dwoma węzłami oraz time(n_i, n_j) przesunięcie czasu między węzłami.
  • Liczba rozłącznych podzbiorów m jest równa liczbie ryb. Rozłączny podzbiór S_ibędzie się składał tylko z węzłów, dla których fish(n) == i.
  • Jeśli dla dwóch węzłów, ia j fish(n_i) != fish(n_j)następnie istnieje łuk między ia j.
  • Koszt między węzłem i a węzłem j jest time(n_i, n_j)lub jest niezdefiniowany, jeśli time(n_i, n_j) < distance(n_i, n_j)(tj. Lokalizacja nie może zostać osiągnięta, zanim ryba tam dotrze, być może dlatego, że jest cofnięta w czasie). Łuki tego ostatniego typu można usunąć.
  • Konieczne będzie dodanie dodatkowego węzła reprezentującego lokalizację gracza wraz z łukami i kosztami dla wszystkich innych węzłów.

Rozwiązanie tego problemu skutkowałoby wówczas pojedynczą wizytą w każdym podzbiorze węzłów (tj. Każda ryba jest pozyskiwana raz) dla ścieżki przy minimalnym koszcie (tj. Minimalnym czasie do uzyskania wszystkich ryb).

W dalszej części artykułu opisano, jak powyższe sformułowanie można przekształcić w tradycyjny Problem komiwojażera, a następnie rozwiązać lub przybliżyć istniejące techniki. Nie przeczytałem szczegółów, ale inny artykuł, który robi to w sposób, który głosi, że jest skuteczny, to ten .

Istnieją oczywiste problemy ze złożonością. W szczególności przestrzeń węzłów jest nieskończona! Można to złagodzić, generując węzły tylko do określonego horyzontu czasowego. Jeśli tjest to liczba kroków czasowych do wygenerowania węzłów i fliczba ryb, to będzie to rozmiar przestrzeni węzłów t * f. Węzeł w danym momencie jbędzie miał co najwyżej (f - 1) * (t - j)łuki wychodzące (ponieważ nie może cofnąć się w czasie ani do własnego podzbioru). Całkowita liczba łuków będzie w kolejności t^2 * f^2łuków. Konstrukcję łukową można prawdopodobnie uporządkować, aby wykorzystać fakt, że ścieżki rybne są ostatecznie cykliczne. Ryby powtórzą swoją konfigurację raz w każdym najmniejszym wspólnym mianowniku długości ich cyklu, więc być może można ten fakt wykorzystać.

Nie wiem wystarczająco dużo o TSP, aby powiedzieć, czy jest to wykonalne, czy nie, i nie sądzę, że oznacza to, że opublikowany problem jest koniecznie NP-trudny ... ale jest to jedno podejście do znalezienia optymalnego lub ograniczonego rozwiązania .

timxyz
źródło
Dzięki, to jest dla mnie nowe i bardzo interesujące. Myślę, że powinienem móc wykorzystać tę transformację w połączeniu z algorytmem Christofidesa, aby skutecznie znaleźć rozwiązanie przy współczynniku przybliżenia 3/2 optymalnego. Jeśli sprawię, że zadziała, dodam utworzone trasy do strony demonstracyjnej.
Peter de Rivaz
Ach, myślę, że jest problem z moim planem polegający na tym, że chociaż moim pierwotnym problemem jest kompletny wykres spełniający odpowiednią nierówność metryki, opisana transformacja skutkuje niepełnym wykresem, więc algorytm Christofidesa już nie ma zastosowania. Mimo wszystko dzięki za ciekawą perspektywę.
Peter de Rivaz,
Tak, zapomniałem wspomnieć, że nierówności trójkątów już nie istnieją. Jest to jednak dobry punkt wyjścia dla rozwiązań heurystycznych i bardziej ogólnych przybliżeń.
timxyz
1

Myślę, że innym podejściem byłoby:

Cytuj wikipedię:

W matematyce diagram Woronoja jest sposobem na podzielenie przestrzeni na kilka regionów. Zbiór punktów (zwanych nasionami, miejscami lub generatorami) jest określony wcześniej i dla każdego ziarna będzie odpowiadał region składający się ze wszystkich punktów bliżej tego ziarna niż jakiegokolwiek innego.

Więc wybierasz cel, podążaj jego ścieżką przez kilka kroków i ustawiasz tam punkt początkowy. Zrób to również ze wszystkimi innymi celami, a otrzymasz diagram voroni. W zależności od tego, w którym obszarze się znajdujesz, przenosisz się do jego punktu początkowego. Viola, masz pierwszą rybę. Teraz powtarzaj ten krok, aż wyłowisz je wszystkie.

Jürgen Stürmer
źródło