Javascript Girl
  1. Javascript Girl
  3. Comment puis-je trouver le chemin le plus court entre 100 cibles mobiles? (Démo en direct incluse.)
Intereting Posts
Peut-on se référer à des variables JavaScript dans les pages Web dans une session de navigateur? Regex qui accepte les alphanumériques seulement, à l'exception d'un trait d'union au milieu Comment créer un code intégré pour d'autres sites Comment créer et déployer une application Samsung SmartTV sans IDE (p. Ex., Sur Linux) Comment incrémenter une chaîne numérique par +1 avec Javascript / jQuery Comment obtenir un index d'éléments dynamiquement classés avec jQuery Premier filtre filtre global sans les filtres de colonne L'espace réservé fonctionne pour le texte mais pas la boîte de mot de passe dans IE / Firefox en utilisant ce javascript Quel type d'erreur de réseau est rencontré Chrome lorsque 'Status = (failed)' et 'Type = undefined' Les graphiques NG2 ne peuvent pas se lier à 'jeux de données' car ce n'est pas une propriété connue de 'canvas' Pourquoi ne sera pas .getPropertyValue () renvoyer une valeur pour la propriété "borderRadius"? Comment implémenter la barre de progression du téléchargement de fichiers sur le Web? Supprimez les virgules de démarrage et de fin de variable dans javascript Mapping deux (ou plus) tableaux en un avec underscore.js Définir l'élément actuel dans la boucle du gestionnaire d'événements onclick

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

Contexte

Cette image illustre le problème: Square_grid_with_arrows_giving_directions

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

Je veux collecter toutes les cibles dans le nombre minimum d'étapes.

À chaque tour, je dois déplacer 1 étape soit à gauche, soit à droite, en haut ou en bas.

Chaque tour, les cibles se déplacent également 1 étape selon les instructions indiquées sur le tableau.

Démonstration

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

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

Problème

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

Je voudrais calculer la réponse pour les tailles 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ésolve le sous-problème de «quel est le nombre minimal de étapes pour collecter un ensemble donné de cibles et finir à une cible particulière?».

Le sous-problème est résolu récursivement en examinant chaque choix pour la cible précédente à avoir visité. Je suppose qu'il est toujours optimal de collecter le sous-ensemble de cibles précédent le plus rapidement possible, puis de passer de la position que vous avez terminée à la cible actuelle le plus rapidement possible (même si je ne sais pas s'il s'agit d'une hypothèse valide).

Cela donne lieu à des états n * 2 ^ n qui se développent très rapidement.

Le code actuel est présenté 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é

Quelques options dont je me suis demandé sont:

  1. Mise en cache des résultats intermédiaires. Le calcul de la distance répète beaucoup de simulation 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 qu'il ne soit pas clair pour moi quelle serait une heuristique admissible appropriée et quelle serait l'efficacité de cette pratique.

  3. Étudier de bons algorithmes pour le problème du vendeur ambulant et voir s'ils s'appliquent à ce problème.

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

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

MISE À JOUR 1:

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

Méthode avide

Une approche suggérée dans les commentaires est d'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é par 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, il est environ le double de la distance optimale, mais parfois beaucoup plus (par ex. * 4) et parfois même atteint l'optimum.

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

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

Méthode de la colonie des fourmis

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

L'idée est que les fourmis choisissent leur parcours de manière probabiliste en fonction du niveau actuel de phéromone. Après chaque 10 essais, nous déposons une phéromone supplémentaire le long de la piste la plus courte qu'ils ont 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 encore très rapide (37 ms pour 16 cibles par rapport à 3700 ms pour la recherche exhaustive) et semble très précis.

Le tableau ci-dessous présente les résultats pour 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 des fourmis semble nettement meilleure que la gourmandise et souvent très proche de l'optimum.

Le problème peut être représenté en termes de problème de vendeur de voyage généralisé, puis converti en un problème de vendeur ambulant conventionnel. C'est un problème bien étudié. Il est possible que les solutions les plus efficaces au problème de l'OP ne soient pas plus efficaces que les solutions au TSP, mais pas certain (je ne peux probablement pas tirer parti de certains aspects de la structure du problème de l'OP qui permettraient une solution plus rapide , Comme son caractère 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 du vendeur ambulant généralisé :

Le problème du vendeur de voyage généralisé (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 dirigé avec les nœuds N, les arcs de connexion A et un vecteur des coûts d'arc correspondants c. Les noeuds sont prégroupés dans des nodesets mutuellement exclusifs et exhaustifs. Les arcs de connexion sont définis uniquement entre les noeuds 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 déclaré comme le problème de trouver un cycle de m-arc à coût minimal qui comprend exactement un noeud de chaque nodeset .

Pour le problème de l'OP:

  • Chaque membre de N est un lieu de pêche particulier à un moment donné. Représentez ceci comme (x, y, t) , où (x, y) est une coordonnée de grille, et t est l'heure à laquelle le poisson sera à cette coordonnée. Pour le poisson le plus à gauche dans l'exemple de l'OP, les premiers de ces (1 basés) sont: (3, 9, 1), (4, 9, 2), (5, 9, 3) lorsque le poisson se déplace à droite.
  • Pour tout membre de N, laisser fish(n_i) renvoyer l'ID du poisson représenté par le noeud. Pour tous les deux membres de N, nous pouvons calculer manhattan(n_i, n_j) pour la distance de manhattan entre les deux noeuds et l' time(n_i, n_j ) pour le décalage temporel entre les nœuds.
  • Le nombre de sous-ensembles disjoints m est égal au nombre de poissons. Le sous-ensemble disjoint S_i ne sera composé que des nœuds pour lesquels le fish(n) == i .
  • Si pour deux nœuds i et j fish(n_i) != fish(n_j) il y a un arc entre i et j .
  • Le coût entre le nœud i et le nœud j est le time(n_i, n_j) ou indéfini si le 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 n'y arrive, peut-être parce qu'il Est en retrait dans le temps). Les arcs de ce dernier type peuvent être enlevé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 entraînerait alors une seule visite dans chaque sous-ensemble de noeuds (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).

Le document poursuit en décrivant comment la formulation ci-dessus peut être transformée en un problème traditionnel de Traveling Salesman et ensuite résolue ou approchée avec les techniques existantes. Je n'ai pas lu les détails, mais un autre document qui fait cela d'une manière proclamée efficace est celui-ci .

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

Je ne sais pas assez sur le TSP pour dire si cela est faisable ou non, et je ne pense pas que le problème posté soit nécessairement NP-dur … mais c'est une approche pour trouver une solution optimale ou délimitée .

Je pense qu'un autre approch serait:

  • Calculez le chemin des cibles – prédictif.
  • Que d' utiliser les diagrammes de Voronoi

Quote wikipedia:

En mathématiques, un diagramme de Voronoi est une façon de diviser l'espace en plusieurs régions. Un ensemble de points (appelés graines, sites ou générateurs) est spécifié au préalable et, pour chaque graine, il y aura une région correspondante composée de tous les points plus proches de cette semence que de toute autre.

Donc, vous choisissez une cible, suivez le chemin pour certaines étapes et définissez un point de prélèvement là-bas. Faites cela avec toutes les autres cibles ainsi que vous obtenez un schéma voroni. Selon votre région, vous vous déplacez vers le point de départ. Viola, vous avez obtenu le premier poisson. Maintenant, répétez cette étape jusqu'à ce que vous les achetiez tous.