Discussion:Recherche de chemin
- Admissibilité
- Neutralité
- Droit d'auteur
- Article de qualité
- Bon article
- Lumière sur
- À faire
- Archives
- Commons
Cet article est indexé par les projets Robotique, Informatique et Mathématiques.
Les projets ont pour but d’enrichir le contenu de Wikipédia en aidant à la coordination du travail des contributeurs. Vous pouvez modifier directement cet article ou visiter les pages de projets pour prendre conseil ou consulter la liste des tâches et des objectifs.
| Avancement | Importance | pour le projet | |
|---|---|---|---|
| Bon début | Élevée |  | Robotique (discussion • critères • liste • stats • hist. • comité • stats vues) |
| Moyenne |  | Informatique (discussion • critères • liste • stats • hist. • comité • stats vues) | |
| À évaluer |  | Mathématiques (discussion • critères • liste • stats • hist. • comité • stats vues) | |
Cet article ne comporte pas de liste de tâches suggérées. Vous pouvez saisir une liste de tâches à accomplir (par exemple sous forme d'une liste à puces), puis sauvegarder. Vous pouvez aussi consulter la page d'aide.
Fusion avec Problèmes de cheminement ? modifier
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
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*.