Wie finde ich den kürzesten Weg zwischen 100 sich bewegenden Zielen? (Live-Demo enthalten.)

Hintergrund

Dieses Bild zeigt das Problem:

Ich kann den roten Kreis kontrollieren. Die Ziele sind die blauen Dreiecke. Die schwarzen Pfeile geben die Richtung an, in die sich die Ziele bewegen.

Ich möchte alle Ziele in der Mindestanzahl von Schritten sammeln.

In jeder Runde muss ich 1 Schritt nach links / rechts / oben oder unten bewegen.

In jeder Runde bewegen sich die Ziele auch 1 Schritt gemäß den Anweisungen auf dem Brett.

Demo

Ich habe hier auf Google Appengine eine spielbare Demo des Problems veröffentlicht .

Ich wäre sehr interessiert, wenn jemand die Zielpunktzahl übertreffen könnte, da dies zeigen würde, dass mein aktueller Algorithmus nicht optimal ist. (Eine Glückwunschbotschaft sollte gedruckt werden, wenn Sie dies schaffen!)

Problem

Mein aktueller Algorithmus skaliert sehr schlecht mit der Anzahl der Ziele. Die Zeit steigt exponentiell und für 16 Fische sind es bereits einige Sekunden.

Ich möchte die Antwort für Brettgrößen von 32 * 32 und mit 100 sich bewegenden Zielen berechnen.

Frage

Was ist ein effizienter Algorithmus (idealerweise in Javascript) zur Berechnung der Mindestanzahl von Schritten zum Sammeln aller Ziele?

Was ich versucht habe

Mein aktueller Ansatz basiert auf Memoisierung, ist aber sehr langsam und ich weiß nicht, ob er immer die beste Lösung liefert.

Ich löse das Teilproblem "Was ist die Mindestanzahl von Schritten, um einen bestimmten Satz von Zielen zu sammeln und an einem bestimmten Ziel zu landen?".

Das Teilproblem wird rekursiv gelöst, indem jede Auswahl für das zuvor besuchte Ziel untersucht wird. Ich gehe davon aus, dass es immer optimal ist, die vorherige Teilmenge von Zielen so schnell wie möglich zu erfassen und dann so schnell wie möglich von der Position, an der Sie gelandet sind, zum aktuellen Ziel zu wechseln (obwohl ich nicht weiß, ob dies eine gültige Annahme ist).

Dies führt dazu, dass n * 2 ^ n Zustände berechnet werden, die sehr schnell wachsen.

Der aktuelle Code wird unten angezeigt:

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

Was ich bedacht habe

Einige Optionen, über die ich mich gewundert habe, sind:

1. Zwischenspeichern von Zwischenergebnissen. Die Entfernungsberechnung wiederholt viele Simulationen und Zwischenergebnisse können zwischengespeichert werden.
   Ich denke jedoch nicht, dass dies eine exponentielle Komplexität verhindern würde.

2. Ein A * -Suchalgorithmus, obwohl mir nicht klar ist, was eine angemessene zulässige Heuristik wäre und wie effektiv dies in der Praxis wäre.

3. Untersuchen Sie gute Algorithmen für das Problem des Handlungsreisenden und prüfen Sie, ob sie auf dieses Problem zutreffen.

4. Der Versuch zu beweisen, dass das Problem NP-schwer und daher unvernünftig ist, eine optimale Antwort darauf zu suchen.

Haben Sie die Literatur durchsucht? Ich habe diese Papiere gefunden, die Ihr Problem zu analysieren scheinen:

• "Verfolgung beweglicher Ziele und des Problems des instationären Handelsreisenden": http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.85.9940

• "Das Problem des Handlungsreisenden mit beweglichen Zielen": http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.57.6403

UPDATE 1:

Die beiden obigen Arbeiten scheinen sich auf die lineare Bewegung für die euklidische Metrik zu konzentrieren.

Gierige Methode

Ein in den Kommentaren vorgeschlagener Ansatz besteht darin, zuerst zum nächstgelegenen Ziel zu gelangen.

Ich habe eine Version der Demo setzen , die die Kosten über diese gierige Methode berechnet umfasst hier .

Der Code lautet:

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

Für 10 Ziele ist es ungefähr doppelt so groß wie die optimale Entfernung, aber manchmal viel mehr (z. B. * 4) und trifft gelegentlich sogar das Optimum.

Dieser Ansatz ist sehr effizient, so dass ich mir einige Zyklen leisten kann, um die Antwort zu verbessern.

Als nächstes überlege ich, Ameisenkoloniemethoden zu verwenden, um zu sehen, ob sie den Lösungsraum effektiv erkunden können.

Ameisenkolonie-Methode

Eine Ameisenkoloniemethode scheint für dieses Problem bemerkenswert gut zu funktionieren. Der Link in dieser Antwort vergleicht nun die Ergebnisse, wenn sowohl die gierige als auch die Ameisenkolonie-Methode verwendet werden.

Die Idee ist, dass Ameisen ihre Route wahrscheinlich basierend auf dem aktuellen Pheromonspiegel wählen. Nach jeweils 10 Versuchen lagern wir zusätzliches Pheromon auf dem kürzesten Weg ab, den sie gefunden haben.

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

Ergebnisse

Diese Ameisenkoloniemethode mit 100 Wiederholungen von 10 Ameisen ist immer noch sehr schnell (37 ms für 16 Ziele im Vergleich zu 3700 ms für die umfassende Suche) und scheint sehr genau zu sein.

Die folgende Tabelle zeigt die Ergebnisse für 10 Versuche mit 16 Zielen:

   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

Die Ameisenmethode scheint deutlich besser als gierig und oft sehr nahe am Optimum zu sein.

Das Problem kann in Form des allgemeinen Problems des reisenden Verkäufers dargestellt und dann in ein herkömmliches Problem des reisenden Verkäufers umgewandelt werden. Dies ist ein gut untersuchtes Problem. Es ist möglich, dass die effizientesten Lösungen für das OP-Problem nicht effizienter sind als Lösungen für den TSP, aber keineswegs sicher (ich kann wahrscheinlich einige Aspekte der Problemstruktur des OP nicht nutzen, die eine schnellere Lösung ermöglichen würden wie seine zyklische Natur). In jedem Fall ist es ein guter Ausgangspunkt.

Von C. Noon & J.Bean, Eine effiziente Transformation des allgemeinen Problems des reisenden Verkäufers :

Das Generalized Travelling Salesman Problem (GTSP) ist ein nützliches Modell für Probleme bei Auswahl- und Reihenfolgeentscheidungen. Die asymmetrische Version des Problems wird in einem gerichteten Graphen mit Knoten N definiert, der die Bögen A und einen Vektor der entsprechenden Lichtbogenkosten c verbindet. Die Knoten sind in m sich gegenseitig ausschließende und erschöpfende Knotensätze vorgruppiert. Verbindungsbögen werden nur zwischen Knoten definiert, die zu verschiedenen Sätzen gehören, dh es gibt keine Intraset-Bögen. Jeder definierte Bogen hat entsprechende nicht negative Kosten. Der GTSP kann als das Problem angegeben werden, einen m-Bogen-Zyklus mit minimalen Kosten zu finden, der genau einen Knoten von jedem Knotensatz enthält .

Für das Problem des OP:

• Jedes Mitglied von Nist der Standort eines bestimmten Fisches zu einer bestimmten Zeit. Stellen Sie dies als dar (x, y, t), wo (x, y)sich eine Gitterkoordinate befindet und tzu welcher Zeit sich der Fisch an dieser Koordinate befindet. Für die Fische ganz links im Beispiel des OP sind die ersten davon (1-basiert):(3, 9, 1), (4, 9, 2), (5, 9, 3) Fisch nach rechts bewegt.
• Geben Sie für jedes Mitglied von N fish(n_i)die ID des durch den Knoten dargestellten Fisches zurück. Für zwei beliebige Mitglieder von N können wir manhattan(n_i, n_j)den Manhattan-Abstand zwischen den beiden Knoten berechnen undtime(n_i, n_j ) den Zeitversatz zwischen den Knoten .
• Die Anzahl der disjunkten Teilmengen m entspricht der Anzahl der Fische. Die disjunkte Teilmenge S_ibesteht nur aus den Knoten, für diefish(n) == i .
• Wenn für zwei Knoten iund j fish(n_i) != fish(n_j)dann gibt es einen Bogen zwischen iundj .
• Die Kosten zwischen Knoten i und Knoten j sind time(n_i, n_j)oder undefiniert, wenn time(n_i, n_j) < distance(n_i, n_j)(dh der Ort kann nicht erreicht werden, bevor der Fisch dort ankommt, möglicherweise weil er zeitlich rückwärts ist). Bögen dieses letzteren Typs können entfernt werden.
• Es muss ein zusätzlicher Knoten hinzugefügt werden, der den Standort des Spielers mit Bögen und Kosten für alle anderen Knoten darstellt.

Das Lösen dieses Problems würde dann zu einem einzelnen Besuch jeder Knotenuntermenge (dh jeder Fisch wird einmal erhalten) für einen Pfad mit minimalen Kosten (dh minimaler Zeit für das Erhalten aller Fische) führen.

In dem Artikel wird weiter beschrieben, wie die obige Formulierung in ein traditionelles Problem des Handlungsreisenden umgewandelt und anschließend mit vorhandenen Techniken gelöst oder angenähert werden kann. Ich habe die Details nicht durchgelesen, aber ein anderes Papier, das dies auf eine Weise tut, die es für effizient erklärt, ist dieses .

Es gibt offensichtliche Probleme mit der Komplexität. Insbesondere ist der Knotenraum unendlich! Dies kann gemildert werden, indem nur Knoten bis zu einem bestimmten Zeithorizont generiert werden. Wenn tdie Anzahl der Zeitschritte, für die Knoten generiert werden sollen, und fdie Anzahl der Fische die Größe des Knotenraums ist t * f. Ein Knoten hat zur Zeit jhöchstens (f - 1) * (t - j)ausgehende Bögen (da er sich nicht in der Zeit oder zu seiner eigenen Teilmenge zurückbewegen kann). Die Gesamtzahl der Bögen liegt in der Reihenfolge der t^2 * f^2Bögen. Die Bogenstruktur kann wahrscheinlich aufgeräumt werden, um die Tatsache auszunutzen, dass die Fischpfade schließlich zyklisch sind. Die Fische wiederholen ihre Konfiguration einmal pro kleinstem gemeinsamen Nenner ihrer Zykluslängen, so dass diese Tatsache möglicherweise genutzt werden kann.

Ich weiß nicht genug über den TSP, um zu sagen, ob dies machbar ist oder nicht, und ich denke nicht, dass das veröffentlichte Problem notwendigerweise NP-schwer ist ... aber es ist ein Ansatz, um eine optimale oder begrenzte Lösung zu finden .

Ich denke, ein anderer Ansatz wäre:

• Berechnen Sie den Pfad der Ziele - vorausschauend.
• als Voronoi-Diagramme verwenden

Zitat Wikipedia:

In der Mathematik ist ein Voronoi-Diagramm eine Möglichkeit, den Raum in mehrere Regionen zu unterteilen. Eine Reihe von Punkten (Samen, Standorte oder Generatoren genannt) wird zuvor festgelegt, und für jeden Samen gibt es eine entsprechende Region, die aus allen Punkten besteht, die näher an diesem Samen liegen als an jedem anderen.

Sie wählen also ein Ziel aus, folgen dem Pfad für einige Schritte und legen dort einen Startpunkt fest. Wenn Sie dies auch mit allen anderen Zielen tun, erhalten Sie ein Voroni-Diagramm. Je nachdem, in welchem ​​Bereich Sie sich befinden, bewegen Sie sich zum Ausgangspunkt. Viola, du hast den ersten Fisch. Wiederholen Sie diesen Schritt, bis Sie alle gefunden haben.