Discussion:Recherche de chemin

Une page de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche
Autres discussions [liste]
  • Suppression
  • Neutralité
  • Droit d'auteur
  • Article de qualité
  • Bon article
  • Lumière sur
  • À faire
  • Archives

Fusion avec Problèmes de cheminement ?[modifier le code]

Bonjour,

J'ai laissé un message sur la page de discussion du projet informatique, mais je n'ai pas eu de réponse. Même si le contenu des deux pages est partiellement différent, ne serait-il pas mieux de les fusionner ?

Cordialement,

Nordald (d) 2 mai 2010 à 11:27 (CEST)

Il s'agit selon moi de domaines qui ne se recoupent que ponctuellement. Les problèmes de cheminement partent d'un graphe existant pour en extraire un chemin. La recherche de chemin abordée dans cette page est un problème plus concret qui part d'un environnement pour tenter de s'y déplacer (éventuellement en construisant un graphe). Quant à la planification de mouvement, c'est un cas particulier de recherche de chemin.
Concrètement, la recherche de chemin va intéresser les roboticiens, les concepteurs de jeux vidéo, etc., alors que les problèmes de cheminement seront plutôt étudiés par des mathématiciens.
Donc la fusion ne me semble pas souhaitable.
Atvaark (d) 3 mai 2010 à 10:56 (CEST)
Cette explication me convainc. Dans ce cas, sur cet article, je vais juste mettre le lien problèmes de cheminement dans le bon paragraphe, et nettoyer la section des liens internes (je ne vois pas de raison de mentionner ici les parcours en profondeur et en largeur, ni les algorithmes de recherche de plus court chemin avec poids négatifs - enfin si ça ne vous va pas, dites-moi). À vrai dire, c'est plus l'autre article que je voulais éditer, mais je voulais régler ça avant. Nordald (d) 3 mai 2010 à 18:40 (CEST)

Imprécisions[modifier le code]

L'article est plutôt bon, mais il y a deux éléments qui me semblent imprécis.

"Tout d'abord, la complexité augmente fortement avec le nombre d'obstacles présents simultanément."

L'article ne cite pas d'algorithme en particulier, mais en général, la complexité des algorithmes de pathfinding est fonction du nombre de noeuds présents dans le graphe, indépendamment des caractéristiques de ces noeuds. Le nombre d'obstacles peut faire varier le temps d'exécution d'une instance d'un problème de pathfinding, bien sur, mais il me semble hasardeux de généraliser ainsi à tous les cas possibles. D'autant plus que la complexité est très bien définie, et de manière tout à fait rigoureuse, en algorithmique.

"Les calculs de recherche de chemin sont actuellement effectués par le processeur de l'ordinateur, mais il est possible qu'ils soient bientôt accélérés matériellement."

Il est tout à fait possible d'accélérer matériellement des algorithmes de pathfinding, encore faut il qu'ils soient parallèlisable. Ça se fait très bien avec Dijkstra, nettement moins avec A*.

--Naxelyss (discuter) 1 décembre 2015 à 07:54 (CET)