Algorithme pour trouver deux points les plus éloignés l'un de l'autre
Im cherche un algorithme à utiliser dans un jeu de course Im making. La Carte / Niveau / piste est générée au hasard donc je dois trouver deux emplacements, start et goal, qui fait usage de la plus grande partie de la carte.
- l'algorithme doit fonctionner à l'intérieur d'un espace bidimensionnel
- de chaque point, on ne peut traverser au point suivant que dans quatre directions; haut, bas, gauche, droite Les Points
- ne peuvent être bloqués ou non bloqués, seuls les points non bloqués peuvent être traversés
en ce qui concerne le calcul de la distance, il ne devrait pas être le "chemin de l'oiseau" en l'absence d'un meilleur mot. Le chemin entre A et B devrait être plus long s'il y a un mur (ou une autre zone de blocage) entre eux.
Je ne sais pas par où commencer, les commentaires sont les bienvenus et les solutions proposées sont préférées en pseudo-code.
Edit: Right. Après avoir regardé à travers code de gs je lui ai donné une autre chance. Au lieu de python, je l'ai écrit en C++. Mais encore, même après avoir lu sur algorithme de Dijkstras , le floodfill et Hosam Alys solution , Je ne détecte aucune différence cruciale. Mon code fonctionne toujours, mais pas aussi vite que tu fais courir le tien. La source complète est sur pastie . La seule interesting lines (I guess) est la variante Dijkstra elle-même sur les lignes 78-118.
Mais la vitesse n'est pas le problème ici. J'apprécierais vraiment de l'aide si quelqu'un serait assez aimable pour montrer les différences dans les algorithmes.
- dans L'algorithme de Hosam Alys, est la seule différence qu'il scanne depuis les bordures au lieu de chaque noeud?
- à Dijkstras vous gardez la trace et écraser la distance marché, mais pas dans remplir, mais des thats à son sujet?
9 réponses
en supposant que la carte est rectangulaire, vous pouvez faire une boucle au-dessus de tous les points limites, et commencer un remplissage d'inondation pour trouver le point le plus éloigné du point de départ:
bestSolution = { start: (0,0), end: (0,0), distance: 0 };
for each point p on the border
flood-fill all points in the map to find the most distant point
if newDistance > bestSolution.distance
bestSolution = { p, distantP, newDistance }
end if
end loop
je suppose que c'est dans O(n^2) . Si Je ne me trompe pas, c'est (L+W) * 2 * (L*W) * 4 , où L est la longueur et W est la largeur de la carte, (L+W) * 2 représente le nombre de points frontaliers sur le périmètre, (L*W) est le nombre de points, et 4 est l'hypothèse que le remplissage par inondation accéderait à un point un maximum de 4 fois (de toutes les directions). Comme n équivaut au nombre de points, cela équivaut à (L + W) * 8 * n , ce qui devrait être mieux que O(n 2 ) . (Si la carte est carrée, l'ordre serait O(16n 1.5 ) .)
mise à Jour: que par les commentaires, puisque la carte est plus d'un maze (que celui avec des obstacles simples comme je pensais initialement), vous pourriez faire la même logique ci-dessus, mais en vérifiant tous les points de la carte (par opposition aux points sur la frontière seulement). Ceci devrait être dans l'ordre de O(4n 2 ) , ce qui est encore mieux que F-W et Dijkstra.
Note: remplissage par inondation est plus approprié pour ce problème, puisque tous les sommets sont directement connecté par le biais de seulement 4 frontières. Une première traversée en largeur de la carte peut donner des résultats relativement rapides (en seulement O(n) ). Je suppose que chaque point peut être vérifié dans le remplissage d'inondation de chacun de ses 4 voisins, donc le coefficient dans les formules ci-dessus.
mise à jour 2: je suis reconnaissant pour tous les commentaires positifs que j'ai reçus au sujet de cet algorithme. Un merci spécial à @Georg pour sa revue .
P. S. toute observation ou correction est la bienvenue.
suite à la question sur Floyd-Warshall ou le simple algorithme de Hosam Aly :
j'ai créé un programme de test qui peut utiliser les deux méthodes. Ce sont les fichiers:
dans tous les cas d'essai Floyd-Warshall était par un grand magnitude plus lente, probablement en raison de la quantité très limitée de bords qui aident cet algorithme pour atteindre cet objectif.
C'étaient les temps, chaque fois le champ était quadruplé et 3 Champs sur 10 étaient un obstacle.
Size Hosam Aly Floyd-Warshall (10x10) 0m0.002s 0m0.007s (20x20) 0m0.009s 0m0.307s (40x40) 0m0.166s 0m22.052s (80x80) 0m2.753s - (160x160) 0m48.028s -
le temps de Hosam Aly semble être quadratique, donc je recommande d'utiliser cet algorithme. La consommation de mémoire de Floyd-Warshall est également n 2 , clairement plus que nécessaire. Si vous avez si vous avez une idée de la lenteur de Floyd-Warshall, veuillez laisser un commentaire ou éditer ce billet.
PS: je n'ai pas écrit C ou C++ depuis longtemps, j'espère que je n'ai pas fait trop d'erreurs.
j'ai supprimé mon billet original recommandant L'algorithme de Floyd-Warshall. : (
gs a fait un benchmark réaliste et devinez quoi, F-W est sensiblement plus lent que L'algorithme" flood fill " de Hosam Aly pour des tailles de carte typiques! Donc, même si F-W est un algorithme cool et beaucoup plus rapide que Dijkstra pour les graphes denses, Je ne peux plus le recommander pour le problème de L'OP, qui implique des graphes très clairsemés (chaque vertex a seulement 4 arêtes).
pour le dossier:
- une implémentation efficace de l'algorithme de Dijkstra prend du temps O(Elog V) pour un graphe avec des arêtes E et des sommets V.
- Hosam Aly " flood fill "est un , qui est O(V). Ceci peut être considéré comme un cas particulier de L'algorithme de Dijkstra dans lequel aucun vertex ne peut avoir son estimation de distance révisée.
- l'algorithme Floyd-Warshall prend du temps O(v^3), est très facile à coder, et est toujours le plus rapide pour les graphes denses (ces graphes où les sommets sont typiquement connectés à beaucoup d'autres sommets). Mais c'est pas le bon choix pour la tâche de L'OP, qui implique des graphiques très clairsemés.
il semble que ce que vous voulez est les points de fin séparés par le diamètre du graphe . Une approximation assez bonne et facile à calculer est de choisir un point aléatoire, trouver le point le plus éloigné de cela, et puis trouver le point le plus éloigné de là. Ces deux derniers points doivent être proches de la séparation maximale.
pour un labyrinthe rectangulaire, cela signifie que deux remplissages de crue devrait vous obtenir une assez bonne paire de points de départ et de fin.
Raimund Seidel donne une méthode simple utilisant la multiplication de matrice pour calculer la matrice de distance de toutes les paires sur un graphe non pondéré, non dirigé (qui est exactement ce que vous voulez) dans la première section de son papier sur le problème de tous les couples-chemin le plus court dans les graphiques non pondéré non corrigé [pdf] .
l'entrée est la matrice de contiguïté et la sortie est la matrice de distance la plus courte de toutes les paires. La durée D'exécution est O(M(n)*log (n)) Pour n points où M (n) est le temps d'exécution de votre algorithme de multiplication matricielle.
le papier donne également la méthode pour calculer les chemins réels (dans le même temps d'exécution) si vous avez besoin de cela aussi.
l'algorithme de Seidel est cool parce que le temps d'exécution est indépendant du nombre de bords, mais nous ne nous soucions pas ici parce que notre graphe est clairsemé. Cependant, ceci peut toujours être un bon choix (malgré le temps d'exécution un peu moins mauvais que n^2) Si vous voulez toutes les paires matrice de distance, et cela pourrait également être plus facile à mettre en œuvre et déboguer que floodfill sur un labyrinthe.
voici le pseudo:
Let A be the nxn (0-1) adjacency matrix of an unweighted, undirected graph, G
All-Pairs-Distances(A)
Z = A * A
Let B be the nxn matrix s.t. b_ij = 1 iff i != j and (a_ij = 1 or z_ij > 0)
if b_ij = 1 for all i != j return 2B - A //base case
T = All-Pairs-Distances(B)
X = T * A
Let D be the nxn matrix s.t. d_ij = 2t_ij if x_ij >= t_ij * degree(j), otherwise d_ij = 2t_ij - 1
return D
pour obtenir la paire de points avec la plus grande distance nous venons de rendre argmax_ij (d_ij)
a fini une maquette en python de la solution de dijkstra au problème. Le Code a été un peu long donc je l'ai posté ailleurs: http://refactormycode.com/codes/717-dijkstra-to-find-two-points-furthest-away-from-each-other
Dans la taille que j'ai mis, il faut environ 1,5 secondes pour exécuter l'algorithme pour un nœud. L'Exécuter pour chaque noeud prend quelques minutes.
ne semble pas fonctionner cependant, il affiche toujours le topleft et coin en bas comme le chemin le plus long; 58 tuiles. Ce qui est bien sûr vrai, quand vous n'avez pas d'obstacles. Mais même en ajoutant quelques uns placés au hasard, le programme trouve toujours que celui-ci est le plus long. Peut-être que c'est encore vrai, difficile à tester sans formes plus avancées.
Mais peut-être qu'il peut au moins montrer mon ambition.
Ok, "algorithme de Hosam" est une première recherche étendue avec une présélection sur les noeuds. L'algorithme de Dijkstra ne doit pas être appliqué ici, parce que vos bords n'ont pas de poids.
la différence est cruciale, parce que si les poids des bords varient, vous devez garder beaucoup d'options (routes alternatives) ouvertes et les vérifier à chaque étape. Cela rend l'algorithme plus complexe. Avec la première recherche de largeur, vous explorez simplement tous les bords une fois d'une manière que assure que vous trouvez le chemin le plus court à chaque nœud. i.e. en explorant les bords dans l'ordre où vous les trouvez.
donc fondamentalement, la différence est que Dijkstra doit 'revenir en arrière' et regarder les bords qu'il a exploré avant de s'assurer qu'il suit le chemin le plus court, tandis que la première recherche de la largeur sait toujours qu'il suit le chemin le plus court.
aussi, dans un labyrinthe les points sur la frontière extérieure ne sont pas garantis pour faire partie de la plus longue route. Par exemple, si vous avez un labyrinthe en forme de spirale géant, mais avec l'extrémité externe de retour à la moyenne, vous pourriez avoir deux points, l'un au cœur de la spirale et l'autre à la fin de la spirale, à la fois dans le milieu!
ainsi, une bonne façon de faire ceci est d'utiliser une recherche de largeur d'abord de chaque point, mais enlever le point de départ après une recherche (vous connaissez déjà tous les itinéraires à et de lui). La complexité de l'étendue est d'abord O(n), où n = |V|+|E|. Nous n' ceci une fois pour chaque noeud en V, donc il devient O(N^2).
votre description sonne pour moi comme un Maze routing problème. Vérifiez L'algorithme Lee . Livres sur les problèmes de place et de route dans la conception VLSI peut vous aider - Sherwani "algorithmes pour VLSI physique Design Automation" est bon, et vous pouvez trouver VLSI physique Design Automation par Sait et Youssef utile (et moins cher dans sa version Google...)
si vos objets(points) ne se déplacent pas fréquemment, vous pouvez effectuer un tel calcul dans un délai beaucoup plus court que O (n^3).
tout ce que vous avez besoin est de briser l'espace dans de grandes grilles et de pré-calculer la distance inter-grille. Ensuite, la sélection de paires de points qui occupent les grilles les plus éloignées est une question de recherche de table simple. Dans le cas Moyen, vous aurez besoin de vérifier par paire seulement un petit ensemble d'objets.
Cette solution fonctionne si la distance les mesures sont continues. Ainsi, si, par exemple, il existe de nombreux obstacles à la carte (comme dans les labyrinthes), cette méthode peut échouer.