Comment trouver le chemin le plus court entre 100 cibles mobiles? (Démo en direct incluse.)

Contexte

Cette image illustre le problème:

Je peux contrôler le cercle rouge. Les cibles sont les triangles bleus. Les flèches noires indiquent la direction dans laquelle les cibles se déplaceront.

Je souhaite collecter toutes les cibles en un minimum d'étapes.

À chaque tour, je dois faire un pas vers la gauche / droite / vers le haut ou vers le bas.

À chaque tour, les cibles se déplaceront également d'un pas selon les directions indiquées sur le tableau.

Démo

J'ai mis en place une démo jouable du problème ici sur Google appengine .

Je serais très intéressé si quelqu'un pouvait battre le score cible car cela montrerait que mon algorithme actuel est sous-optimal. (Un message de félicitations devrait être imprimé si vous gérez cela!)

Problème

Mon algorithme actuel évolue très mal avec le nombre de cibles. Le temps augmente de façon exponentielle et pour 16 poissons, il est déjà de plusieurs secondes.

Je voudrais calculer la réponse pour des tailles de carte de 32 * 32 et avec 100 cibles mobiles.

Question

Qu'est-ce qu'un algorithme efficace (idéalement en Javascript) pour calculer le nombre minimum d'étapes pour collecter toutes les cibles?

Ce que j'ai essayé

Mon approche actuelle est basée sur la mémoisation mais elle est très lente et je ne sais pas si elle générera toujours la meilleure solution.

Je résous le sous-problème de "quel est le nombre minimum d'étapes pour collecter un ensemble donné de cibles et aboutir à une cible particulière?".

Le sous-problème est résolu de manière récursive en examinant chaque choix de la cible précédente à avoir visité. Je suppose qu'il est toujours optimal de collecter le sous-ensemble précédent de cibles aussi rapidement que possible, puis de passer de la position où vous vous êtes retrouvé à la cible actuelle le plus rapidement possible (bien que je ne sache pas si c'est une hypothèse valable).

Il en résulte n * 2 ^ n états à calculer qui croît très rapidement.

Le code actuel est indiqué ci-dessous:

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

Ce que j'ai considéré

Certaines options sur lesquelles je me suis interrogé sont:

1. Mise en cache des résultats intermédiaires. Le calcul de la distance répète de nombreuses simulations et les résultats intermédiaires peuvent être mis en cache.
   Cependant, je ne pense pas que cela l'empêcherait d'avoir une complexité exponentielle.

2. Un algorithme de recherche A * bien que je ne sache pas ce que serait une heuristique admissible appropriée et quelle serait son efficacité dans la pratique.

3. Enquêter sur de bons algorithmes pour le problème du voyageur de commerce et voir s'ils s'appliquent à ce problème.

4. Essayer de prouver que le problème est NP-difficile et donc déraisonnable de chercher une réponse optimale pour cela.

Avez-vous recherché la littérature? J'ai trouvé ces papiers qui semblent analyser votre problème:

• "Suivi des cibles mobiles et problème du voyageur de commerce non stationnaire": http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.85.9940

• «Le problème du voyageur de commerce à cible mobile»: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.57.6403

MISE À JOUR 1:

Les deux articles ci-dessus semblent se concentrer sur le mouvement linéaire pour la métrique euclidienne.

Méthode gourmande

Une approche suggérée dans les commentaires consiste à aller d'abord vers la cible la plus proche.

J'ai mis en place une version de la démo qui inclut le coût calculé via cette méthode gourmande ici .

Le code est:

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

Pour 10 cibles, c'est environ le double de la distance optimale, mais parfois beaucoup plus (par exemple * 4) et parfois même atteint l'optimum.

Cette approche est très efficace et je peux donc me permettre quelques cycles pour améliorer la réponse.

Ensuite, j'envisage d'utiliser des méthodes de colonie de fourmis pour voir si elles peuvent explorer efficacement l'espace de solution.

Méthode de la colonie de fourmis

Une méthode de colonie de fourmis semble fonctionner remarquablement bien pour ce problème. Le lien dans cette réponse compare maintenant les résultats lors de l'utilisation de la méthode avide et de la colonie de fourmis.

L'idée est que les fourmis choisissent leur route de manière probabiliste en fonction du niveau actuel de phéromones. Tous les 10 essais, nous déposons des phéromones supplémentaires le long de la piste la plus courte trouvée.

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

Résultats

Cette méthode de colonie de fourmis utilisant 100 répétitions de 10 fourmis est toujours très rapide (37ms pour 16 cibles contre 3700ms pour la recherche exhaustive) et semble très précise.

Le tableau ci-dessous présente les résultats de 10 essais utilisant 16 cibles:

   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

La méthode fourmi semble nettement meilleure que gourmande et souvent très proche de l'optimum.

Le problème peut être représenté en termes de problème de voyageur de commerce généralisé, puis converti en problème de voyageur de commerce conventionnel. C'est un problème bien étudié. Il est possible que les solutions les plus efficaces au problème du PO ne soient pas plus efficaces que les solutions au TSP, mais en aucun cas certaines (je ne parviens probablement pas à tirer parti de certains aspects de la structure du problème du PO qui permettraient une solution plus rapide , comme sa nature cyclique). Quoi qu'il en soit, c'est un bon point de départ.

De C. Noon & J.Bean, Une transformation efficace du problème généralisé du voyageur de commerce :

Le problème généralisé du voyageur de commerce (GTSP) est un modèle utile pour les problèmes impliquant des décisions de sélection et de séquence. La version asymétrique du problème est définie sur un graphe orienté aux nœuds N, reliant les arcs A et un vecteur de coûts d'arc correspondant c. Les nœuds sont prégroupés en m ensembles de nœuds exhaustifs et mutuellement exclusifs. Les arcs de connexion sont définis uniquement entre des nœuds appartenant à des ensembles différents, c'est-à-dire qu'il n'y a pas d'arcs intraset. Chaque arc défini a un coût non négatif correspondant. Le GTSP peut être énoncé comme le problème de trouver un cycle m-arc de coût minimum qui inclut exactement un nœud de chaque ensemble de nœuds .

Pour le problème du PO:

• Chaque membre de Nest l'emplacement d'un poisson particulier à un moment donné. Représentez-le comme (x, y, t), où (x, y)est une coordonnée de grille, et test le moment auquel le poisson sera à cette coordonnée. Pour le poisson le plus à gauche dans l'exemple du PO, les premiers (basés sur 1) sont: (3, 9, 1), (4, 9, 2), (5, 9, 3)lorsque le poisson se déplace vers la droite.
• Pour tout membre de N fish(n_i)retournons l'ID du poisson représenté par le nœud. Pour deux membres quelconques de N, nous pouvons calculer manhattan(n_i, n_j)la distance de Manhattan entre les deux nœuds et time(n_i, n_j) le décalage temporel entre les nœuds.
• Le nombre de sous-ensembles disjoints m est égal au nombre de poissons. Le sous S_i- ensemble disjoint comprendra uniquement les nœuds pour lesquels fish(n) == i.
• Si pour deux nœuds iet j fish(n_i) != fish(n_j)alors il y a un arc entre iet j.
• Le coût entre le nœud i et le nœud j est time(n_i, n_j), ou indéfini si time(n_i, n_j) < distance(n_i, n_j)(c'est-à-dire que l'emplacement ne peut pas être atteint avant que le poisson y arrive, peut-être parce qu'il est en arrière dans le temps). Les arcs de ce dernier type peuvent être supprimés.
• Un nœud supplémentaire devra être ajouté représentant l'emplacement du joueur avec des arcs et des coûts pour tous les autres nœuds.

La résolution de ce problème résulterait alors en une seule visite à chaque sous-ensemble de nœuds (c'est-à-dire que chaque poisson est obtenu une fois) pour un chemin avec un coût minimal (c'est-à-dire un temps minimal pour tous les poissons à obtenir).

L'article poursuit en décrivant comment la formulation ci-dessus peut être transformée en un problème de voyageur de commerce traditionnel et ensuite résolue ou rapprochée avec des techniques existantes. Je n'ai pas lu les détails, mais un autre article qui fait cela d'une manière qu'il proclame efficace est celui-ci .

Il y a des problèmes évidents de complexité. En particulier, l'espace des nœuds est infini! Cela peut être atténué en ne générant que des nœuds jusqu'à un certain horizon temporel. Si test le nombre de pas de temps pour générer des nœuds et fest le nombre de poissons, alors la taille de l'espace de nœuds sera t * f. Un nœud à la fois jaura au plus des (f - 1) * (t - j)arcs sortants (car il ne peut pas remonter dans le temps ou vers son propre sous-ensemble). Le nombre total d'arcs sera de l'ordre des t^2 * f^2arcs. La structure en arc peut probablement être rangée, pour profiter du fait que les trajectoires des poissons sont finalement cycliques. Les poissons répéteront leur configuration une fois à chaque plus petit dénominateur commun de leurs longueurs de cycle, donc peut-être ce fait peut être utilisé.

Je ne connais pas assez le TSP pour dire si cela est faisable ou non, et je ne pense pas que cela signifie que le problème affiché est nécessairement NP-difficile ... mais c'est une approche pour trouver une solution optimale ou limitée .

Je pense qu'une autre approche serait:

• calculer le chemin des cibles - prédictif.
• que d'utiliser des diagrammes de Voronoi

Citer wikipedia:

En mathématiques, un diagramme de Voronoi est un moyen de diviser l'espace en un certain nombre de régions. Un ensemble de points (appelés graines, sites ou générateurs) est spécifié à l'avance et pour chaque graine, il y aura une région correspondante composée de tous les points plus proches de cette graine que de tout autre.

Ainsi, vous choisissez une cible, suivez son chemin pendant certaines étapes et définissez un point de départ là-bas. Faites-le également avec toutes les autres cibles et vous obtenez un diagramme voroni. Selon la zone dans laquelle vous vous trouvez, vous vous déplacez vers le point de départ de celui-ci. Viola, tu as le premier poisson. Maintenant, répétez cette étape jusqu'à ce que vous les ayez tous vaincus.