Algorithme pour trouver deux points les plus éloignés l'un de l'autre
https://stackoverflow.com/questions/477591
-
20-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Je cherche un algorithme à utiliser dans un jeu de course. La carte / le niveau / la piste sont générés aléatoirement. Je dois donc trouver deux emplacements, le début et l’objectif, qui permettent de tirer le meilleur parti de la carte.
- L'algorithme consiste à travailler dans un espace à deux dimensions
- À partir de chaque point, on ne peut se rendre au point suivant que dans quatre directions; haut, bas, gauche, droite
- Les points ne peuvent être bloqués ou non, seuls les points non bloqués peuvent être traversés
En ce qui concerne le calcul de la distance, il ne devrait pas s'agir du "sentier des oiseaux". faute de meilleur mot. Le chemin entre A et B devrait être plus long s’il existe 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 dans le pseudo-code.
Modifier: Bien. Après avoir parcouru les code de gs , je lui donna un autre coup. Au lieu de python, je l’ai écrit cette fois en C ++. Néanmoins, même après la lecture de algorithme de Dijkstras , le floodfill et pastie . La seule ligne intéressante (je suppose) est la variante Dijkstra elle-même sur les lignes 78-118.
Mais la vitesse n’est pas le principal problème ici. J'apprécierais vraiment l'aide si quelqu'un avait la gentillesse de signaler les différences entre les algorithmes.
- Dans l'algorithme Hosam Alys, la seule différence est-il qu'il scanne depuis les frontières au lieu de chaque nœud?
- À Dijkstras, vous gardez une trace et écrivez la distance parcourue, mais pas en cas d’inondation, mais c’est tout?
La solution
En supposant que la carte soit rectangulaire, vous pouvez effectuer une boucle sur tous les points de bordure et commencer un remplissage 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 ce serait 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 de bordure sur le périmètre, (L * W) est le nombre de points, et 4 est l’hypothèse que le remplissage aurait accès à un point 4 fois au maximum (de toutes les directions). Puisque n est équivalent au nombre de points, cela équivaut à (L + W) * 8 * n , ce qui devrait être supérieur à O (n 2 ) . (Si la carte est carrée, l'ordre serait O (16n 1.5 ) .)
Mise à jour: conformément aux commentaires, la carte étant davantage un labyrinthe (qu'un obstacle avec de simples obstacles comme je le pensais au départ), vous pouvez utiliser la même logique ci-dessus, mais en vérifiant tous les points dans la carte (par opposition aux points de la frontière uniquement). Cela devrait être dans l'ordre de O (4n 2 ) , ce qui est toujours meilleur que les deux F-W et Dijkstra.
Remarque: Le Remplir une inondation convient mieux à ce problème. , puisque tous les sommets sont directement connectés via 4 frontières seulement. Une première traversée étendue de la carte peut donner des résultats relativement rapidement (dans seulement O (n) ). Je suppose que chaque point peut être contrôlé dans le remplissage de chacun de ses 4 voisins, ainsi le coefficient dans les formules ci-dessus.
Mise à jour 2: je suis reconnaissant pour tous les commentaires positifs que j'ai reçus concernant cet algorithme. Un merci spécial à @Georg pour son compte rendu .
P.S. Tous commentaires ou corrections sont les bienvenus.
Autres conseils
Poursuivez avec la question sur Floyd-Warshall ou l’algorithme simple 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 de test, Floyd-Warshall était beaucoup plus lent, probablement en raison du nombre très limité d'arêtes permettant à cet algorithme de réaliser cela.
C’était le moment, chaque fois que le champ était quadruplé et que 3 champs sur 10 constituaient 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, je vous recommande donc d'utiliser cet algorithme. De plus, la consommation de mémoire de Floyd-Warshall est de n 2 , nettement plus que nécessaire. Si vous avez une idée de la lenteur de Floyd-Warshall, n'hésitez pas à laisser un commentaire ou à modifier ce message.
PS: Je n'ai pas écrit C ou C ++ depuis longtemps, j'espère ne pas avoir commis trop d'erreurs.
J'ai supprimé mon message d'origine recommandant l'algorithme Floyd-Warshall. : (
gs a réalisé un test de performance réaliste
Pour mémoire:
Cela ressemble à ce que vous voulez, ce sont les points finaux séparés par le diamètre du graphique . Une approximation assez bonne et facile à calculer consiste à choisir un point au hasard, à en trouver le point le plus éloigné, puis à en trouver le point le plus éloigné. Ces deux derniers points devraient être proches de la séparation maximale.
Pour un labyrinthe rectangulaire, cela signifie que deux remplissages par une inondation devraient vous procurer une bonne paire de points de départ et d'arrivée.
Raimund Seidel donne une méthode simple utilisant la multiplication matricielle pour calculer la matrice de distance toutes paires sur un graphe non pondéré et non dirigé (ce qui est exactement ce que vous voulez) dans la première section de son document Sur le problème le plus court du chemin le plus court dans les graphes non pondérés non pondérés [pdf] .
L'entrée est la matrice d'adjacence et la sortie est la matrice de distance du plus court chemin pour toutes les paires. Le temps 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 de matrice.
Le document indique également la méthode de calcul des chemins réels (dans le même temps d'exécution) si vous en avez également besoin.
L’algorithme de Seidel est cool parce que le temps d’exécution est indépendant du nombre d’arêtes, mais en réalité nous ne nous en soucions pas car notre graphique est peu dense. Cependant, cela peut toujours être un bon choix (malgré le temps d'exécution légèrement pire que n ^ 2) si vous voulez la matrice de distance toutes les paires, et cela pourrait aussi être plus facile à implémenter et à déboguer que de le remplir d'un labyrinthe.
Voici le pseudocode:
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 renvoyons simplement argmax_ij (d_ij)
Finition d'une maquette en python de la solution de dijkstra au problème. Le code a pris un peu de temps alors je l'ai posté ailleurs: http://refactormycode.com/codes/717-dijkstra-toffind-two-points-furthest-away-from-each-other
Dans la taille que j'ai définie, l'exécution de l'algorithme pour un nœud prend environ 1,5 seconde. L'exécuter pour chaque nœud prend quelques minutes.
Ne semble pas fonctionner, il affiche toujours le coin le plus long et le coin le plus long; 58 tuiles. Ce qui bien sûr est vrai, quand vous n'avez pas d'obstacles. Mais même en ajoutant quelques paires placées au hasard, le programme trouve toujours celle-ci la plus longue. Peut-être que c'est toujours vrai, difficile à tester sans formes plus avancées.
Mais peut-être que ça peut au moins montrer mon ambition.
Ok, "l'algorithme de Hosam" est une première recherche en largeur avec une présélection sur les nœuds. L'algorithme de Dijkstra ne doit PAS être appliqué ici, car vos arêtes n'ont pas de poids.
La différence est cruciale, car si le poids des bords varie, vous devez laisser de nombreuses options (itinéraires alternatifs) ouvertes et les vérifier à chaque étape. Cela rend l'algorithme plus complexe. Avec la première recherche étendue, il vous suffit d'explorer tous les bords une fois de manière à garantir que vous trouvez le chemin le plus court vers chaque nœud. c'est-à-dire en explorant les bords dans l'ordre où vous les trouvez.
La différence réside donc dans le fait que Dijkstra doit "revenir en arrière" et regarder les contours qu’elle a explorés auparavant pour s’assurer qu’elle suit le chemin le plus court, alors que la première recherche approfondie sait toujours qu’elle suit le chemin le plus court.
De plus, dans un labyrinthe, les points de la bordure extérieure ne font pas nécessairement partie du plus long itinéraire. Par exemple, si vous avez un labyrinthe en forme de spirale géante, mais dont l’extrémité extérieure remonte au milieu, vous pouvez avoir deux points situés au cœur de la spirale et l’autre au bout de la spirale, les deux au milieu!
Un bon moyen de procéder consiste donc à effectuer une première recherche en profondeur sur tous les points, mais à supprimer le point de départ après une recherche (vous connaissez déjà tous les itinéraires aller et retour). La complexité de la largeur est d'abord O (n), où n = | V | + | E |. Nous faisons cela une fois pour chaque noeud de V, il devient donc O (n ^ 2).
Votre description me semble être un problème de routage du labyrinthe . Consultez le algorithme de Lee . Les livres sur les problèmes d’emplacement et de route dans la conception VLSI peuvent vous aider - Algorithmes de Sherwani L'automatisation de la conception physique VLSI " est bonne et vous pouvez trouver Automatisation de la conception physique VLSI par Sait et Youssef utile (et meilleur marché dans sa version Google ...)
Si vos objets (points) ne bougent pas fréquemment, vous pouvez effectuer un tel calcul dans un temps beaucoup plus court que O (n ^ 3).
Tout ce dont vous avez besoin est de diviser l’espace en grandes grilles et de pré-calculer la distance entre les grilles. Ensuite, la sélection des paires de points occupant les grilles les plus éloignées est une simple question de consultation de table. Dans la plupart des cas, vous ne devez cocher par paire que quelques objets.
Cette solution fonctionne si les mesures de distance sont continues. Ainsi, si, par exemple, il existe de nombreux obstacles sur la carte (comme dans les labyrinthes), cette méthode peut échouer.
