Discussion:Problème de plus court chemin

six degrés

le lien ne fonctionne pas. Claudeh5 (d) 10 juin 2008 à 11:06 (CEST)

Présentation et choix

Bonjour,

deux critiques :

• il me semble que la présentation avec le semi-anneau n'est pas classique et devrait venir dans une section à part ;
• il ne me semble pas que problème de cheminement soit une appellation très utilisée, il faudrait peut-être penser à des fusions ou des renommages.

Qu'en pensez-vous ? --Roll-Morton (discuter) 5 janvier 2015 à 18:46 (CET)

Renommage ?

Bonjour, je trouve que "problèmes de cheminement" est joli, mais très peu utilisé, on parle de "problème de plus court chemin". Que pensez-vous d'un renommage ? Il y a quelques difficultés, car il y a beaucoup de problèmes proches, comme le montre en:Shortest path problem. Une possibilité serait d'avoir "problème de cheminement" regroupant tous ces problèmes (et l'approche par semi-anneau), et d'avoir des pages spécifiques pour chacun. Qu'en pensez-vous ? --Roll-Morton (discuter) 22 juin 2016 à 17:21 (CEST)

Bonjour, je suis aussi d'avis de renommer en "problème de plus court chemin", ne serait-ce que pour se rapprocher de la philosophie des articles anglais et allemands. Je trouve que l'approche algébrique est utile, et mérite un traitement séparé ; ce n'est qu'une sous-section trop courte : "General algebraic framework on semirings: the algebraic path problem" dans l'article anglais. J'aime bien les tableaux de synthèse dans l'article anglais; j'aime bien la description moins "liste" dans le style allemand; et je suis aussi favorable aux pages spécifiques, peut-être d'ailleurs avec une palette pour s'y retrouver ? Courage aux amateurs ! -- ManiacParisien (discuter) 28 juin 2016 à 20:11 (CEST)

 ManiacParisien : J'ai fait le renommage. reste à faire le vrai boulot. --Roll-Morton (discuter) 22 août 2016 à 11:26 (CEST)

En anglais, il y a quand même aussi l’expression "pathfinding". En fait on est passé sur un impératif de trouver un chemin à celui de trouver le plus court, je suis pas sur qu'on y ait gagné. — TomT0m ^[bla] 22 août 2016 à 11:58 (CEST)

D'ailleurs j’ai l'impression que recherche de chemin aurait du s'appeler "problème de cheminement", et que cet article à la base avait l’ambition d'être plutôt un équivalent de "recherche de chemin", mais a été restreint. Problème classique de manque de communication/conflit entre les contributeurs si c'est le cas. En tout cas ce renommage casse aussi la formulation de l’autre article qui fait toujours référence à l'ancien nom. C'est chiant mais en cas de renommage comme en cas de fusion d'article, il faut aussi contrôler les liens entrant. C'est le problème des articles qui changent de sujet avec le temps ou brusquement à cause d'une fusion / scission. — TomT0m ^[bla] 22 août 2016 à 12:03 (CEST)

Je pense qu'il est naturel de séparer le pathfinding du reste : ce sont des problèmes de connexité, où l'on cherche à connaître l'espace, où une marche aléatoire est un bon exemple d'algorithme, ce qui est très loin dans l'espritdes problèmes d'optimisation de chemin. Pour le reste oui, le renommage n'a pas que des bons cotés, on aimerait peut-être avoir un article qui parle de trouver des chemins en général, en optimisant des choses bizarres etc. Mais il me semble que l'usage est quand même à ce vocabulaire et l’intérêt plutôt porté au chemin court.--Roll-Morton (discuter) 22 août 2016 à 12:30 (CEST)

À mon avis le souci est que cet article amalgame LE problème de plus court chemin, un problème algorithmique précis, celui que résoud l’algo de Dijsktra, avec les problèmes de plus court chemin en général. C'est un choix mais à mon avis c'est pas particulièrement le meilleur vu qu'il y a plein de chose à dire sur le problème classique, et sans doute bien plus sur la famille de problème. — TomT0m ^[bla] 22 août 2016 à 12:36 (CEST)

J'ai fait quelques corrections au tout début. Je ne savais pas la recherche de chemin relève de l'intelligence artificielle - que l'on met décidément à toutes les sauces :-) -- ManiacParisien (discuter) 22 août 2016 à 12:40 (CEST)

C'est un problème sans doute basique, mais que n'importe quel robot autonome doit résoudre. D'où l’intérêt de l’intelligence artificielle pour ce problème. C'est un truc simple et basique, y compris pour un animal ou pour un humain, mais quand tu t’intéresse dans le détail sur comment ça fonctionne dans le cerveau, tu trouves des réseau de neurones intéressant (un "Pour la science" titrait récemment "un GPS dans le cerveau"). Ça demande de modéliser et découvrir son environnement si tu exclus les marches aléatoires qui ne vont fonctionner (efficacement) que dans un environnement relativement petit. — TomT0m ^[bla] 22 août 2016 à 12:47 (CEST)

Je suis d'accord avec l'ambiguité entre le problème classique et les variantes. Je pensais éventuellement à un "problème DU plus court chemin" pour traiter en particulier celui-là. Comme souvent la difficulté est de définir la frontière du sujet : mettre les problèmes variantes dans une section "variantes" est difficile, car cette section serait beaucoup plus grosse que tout le reste. --Roll-Morton (discuter) 22 août 2016 à 14:58 (CEST)

En effet, DU plus court chemin est beaucoup plus fréquent que DE plus court chemin. Et là, on est dans l’algorithmique la plus classique. Ensuite, qu’il s’agisse de robotique ou de GPS, on est dans l’usage ou dans l’application.--ManiacParisien (discuter) 22 août 2016 à 17:27 (CEST)

C'est pas trop la(les) questions. On parle scission de l’article. — TomT0m ^[bla] 22 août 2016 à 19:51 (CEST)

On peut imaginer de renommer avec «DU», et de faire un article généraliste comme en anglais, en faisant une section intro (pas le RI, mais juste après) qui vulgarise le cas classique, puis de parler du reste. Pour éviter le fourre-tout, on pourrait faire des articles détaillés, par exemple sur l'approche algébrique, et sur le problème classique, si on a vraiment beaucoup de choses à dire, et pourquoi pas sur les problèmes plus spécifiques (all pair shortest path, approx etc.). --Roll-Morton (discuter) 22 août 2016 à 20:24 (CEST)

pourquoi les éclipser ?

1/Je lis (oui, je sais lire !) "Cette interprétation a déjà été présentée dans le livre de Aho, Hopcroft et Ullman en 19741, et reprise ultérieurement, par Gondran et Minoux par exemple". C'est vrai mais pourquoi citer des auteurs anglais qui ne sont pas historiquement prioritaires alors que les auteurs initiaux étaient français: P. Robert et J. Ferland dans l'article "Généralisation de l'algorithme de Warshall" paru en 1968 dans Revue Française d'Informatique. Recherche Opérationelle 2 (1968) 71-85.

2/ Je rappelle qu'un problème de cheminement n'est pas un problème de plus court chemin et qu'il aurait été de bon ton de faire plutôt l'inverse: renvoyer les problèmes de plus court chemin vers les problèmes de cheminement. En particulier, j'avais donné en son temps l'exemple de la détermination de tous les chemins, ce qui n'a qu'un lointain rapport avec un problème de plus court chemin.

3/ Contrairement à ce que vous croyez, j'ai interdit à wikipédia (qui l'a effacé) l'utilisation de MES textes que, par une indélicatesse caractérisée, l'historique de l'article n'indique pas dans la formule "29 mai 2008 à 00:24‎ 82.237.177.72 (discuter)‎ . . (9 353 octets) (+7 729)‎ . . (Déplacé la présentation des algos de cheminements depuis la liste des algos sur les graphes)(annuler)"

4/ actuellement, après le passage d'un maniaque en novembre 2016, l'ensemble est devenu lourd, illisible et touffu à partir de "réseau routier". D'autre part l'article était plus précis sur les applications qui ne sortent pas d'un calcul de plus court chemin.

signé Claudeh5.

Bonjour, merci de vos commentaires et remarques : j'imagine que c'est moi que vous citez au point 4/, et je me permets de vous répondre :

- Je ne connaissais pas l’article de Robert et Ferland, et je vais m'empresser - dès que j'aurais un moment - de l’incorporer dans les références, surtout qu'il est accessible sur numdam.

- Je suis d'accord que les problèmes de cheminement (terme vague) sont plus généraux que le problème de plus court chemin qui est le sujet de l'article, c'est bien pour cela qu'il y a eu renommage

- Je ne connaissais pas la discussion du point 3/, et je ne crois rien à ce propos.

- Je regrette que vous trouvez la dernière partie lourde : il me semblait utile de faire mention de recherches plus récentes même si ce n’est que sous forme imprécise, pour dépasser ce qui se trouve dans tous les manuels.

Bien cordialement. -- ManiacParisien (discuter) 2 mars 2017 à 11:32 (CET)

Bonjour. 1/Quand on prend pour pseudo ManiacParisien, il faut assumer le "maniac". Il en est de même des utilisateurs qui se disent "Ayatollas des sources" et qui s'étonnent après d'être traités d'ayatollas, et j'en passe. 2/ Il est tout de même étonnant que vous ne connaissiez pas cet article qui est cité dans le Gondran et Minoux (que vous citez) dans les références du chapitre 3, en page 128 de l'édition anglaise 3/ Vous n'en croyez rien ? Je vous invite à aller sur la page historique de "liste des algorithmes de la théorie des graphes" à la date du 4 septembre 2006 puis à regarder la date du 28 mai 2008. Quant à l'autorisation voici ce qu'on trouve quand on compare les versions de la page de discussion de claudeh5:

"Je vous rappelle que wikipédia n'a plus l'autorisation d'utiliser mes textes.Cordialement dit. Le tigre à dents de sabre.Claudeh5 (discuter) 7 juin 2015 à 00:21 (CEST)"

Bien cordialement. Claudeh5, le 2 mars 2017 à 15h52

Bonjour, il me semble que l'utilisateur Claudeh5 a été banni notamment pour des propos agressifs, il n'est donc pas de très bon ton de contourner cette mesure, qui plus est en étant agressif. Pour ce qui est des contenus :

• Je ne comprends pas la partie sur l'autorisation d'utiliser les textes : si ces textes sont sur wikipedia, ou bien ils ont été recopiés illégalement depuis un autre texte, alors il y a un copyvio, et il faut être plus précis pour que le tort soit réparé ; ou bien ils étaient inédits, et alors ils sont sous licence creative commons, et tout le monde peut les utiliser.
• Pour ce qui est de la référence en français, c'est un simple oubli et qui plus est la phrase ne parle pas de la première référence, mais d'une référence.
• Pour ce qui est du titre, il y a eu une discussion sur le sujet au-dessus, il y a peut-être mieux à trouver. --Roll-Morton (discuter) 2 mars 2017 à 23:55 (CET)

Présentation de l'algorithme généralisé de Floyd Warshall

Bonjour, je crois que dire que l'algorithme généralisé de Floyd Warshall marche dans tout demi-anneau est faux. Après avoir lu l'article de Robert et Ferland, il me semble qu'il faut que le neutre de la multiplication soit également absorbant dans l'addition : a + 1 = 1. Eux ils parlent de Q-semi-anneau.

Sinon, ça voudrait que l'algorithme de Floyd Warshall marcherait pour (R,+,x), et alors le problème consisterait à calculer la somme des poids des chemins de longueur <= n entre toutes paires de sommets, ce qui ne marche manifestement pas.

Je ne sais pas comment modifier cela car 1. je ne suis pas sûr à 100% de moi 2. l'introduction de cette section parle beaucoup de demi-anneau : devrait-on tout supprimer ? --Julien Courtiel (discuter) 27 juillet 2018 à 15:15 (CEST)