Discussion:Algorithme de Dantzig-Ford/Admissibilité
- Admissibilité
- Neutralité
- Droit d'auteur
- Article de qualité
- Bon article
- Lumière sur
- À faire
- Archives
- Commons
Cette page a précédemment fait l’objet d’une discussion quant à sa suppression, consultable ici.
L'admissibilité de la page « Algorithme de Dantzig-Ford » est débattue.
Consignes quant à cette procédure :
- Qui peut participer ?
- Le créateur de la page et les contributeurs ayant un compte ayant fait au moins cinquante contributions aux articles (espace principal) de fr.wikipedia.org au lancement de cette procédure peuvent exprimer leur avis.
- Les avis des personnes n’ayant pas de compte ou un compte ayant moins de 50 contributions sont déplacés dans « Avis non décomptés » et ne sont en principe pas pris en considération. Lors de la clôture, les avis sans argumentaire sont également déplacés et ne sont pas pris en compte.
- Durée de la consultation
- Si un consensus clair s'est dégagé le 19 août après l'expiration de sept jours pleins de débat (168 heures), un contributeur ayant réalisé au moins 500 modifications et ayant 3 mois d'ancienneté (utilisateur autopatrolled) qui n'aura pas pris part au débat peut clore la proposition et indiquer si la page est conservée ou supprimée (la suppression devant être demandée à un administrateur). Dans le cas contraire, la discussion se poursuit et peut être close à partir du 26 août.
Important
- Copiez le lien *{{L|Algorithme de Dantzig-Ford}} et collez-le dans la section du jour de la page principale « Débat d'admissibilité ». Attention, un décalage d'un jour est possible en fonction de la mise en page.
- Avertissez le créateur, les principaux contributeurs de l’article et, si possible, les projets associés en apposant le message {{subst:Avertissement débat d'admissibilité|Algorithme de Dantzig-Ford}} sur leur page de discussion.
Proposé par : Orlodrim [discuter] 12 août 2012 à 00:42 (CEST)
J'avais mis une longue proposition ici mais en fait je vais revoir ma position :
- selon la thèse mentionnée par schlum, l'algorithme est bien décrit quelque part dans le papier mentionné là Il va falloir que je lise ça en détail mais il manque des pages sur Google Books...)
- à part de cet article, on trouve très peu de mentions de cet algorithme. En particulier, il ne semble pas être décrit dans des ouvrages de référence sur les graphes.
A t-il été simplement relégué au rang de curiosité après la publication de l'algorithme de Bellman-Ford ? Toujours selon la thèse mentionnée, c'est polynomial en temps, mais faute d'avoir une description plus détaillée de l'algorithme, difficile d'en savoir plus. Bon, ce n'est pas l'efficacité qui fait l'admissibilité, mais si personne n'a fait ne serait-ce qu'une analyse de complexité, je ne sais pas si c'est justifié de faire un article.
Conclusion
Suppression traitée par Kyro me parler le 26 août 2012 à 02:40 (CEST)
Raison : Hors critères
Discussions
modifierToutes les discussions vont ci-dessous.
Quelques éléments supplémentaires :
- Il est mentionné dans cette thèse [1] (§ 4.2.2, p. 68) avec référence à un ouvrage de 1956 (Dantzig, G., Ford, L., and Fulkerson, D. (1956). A primal-dual algorithm for linear programms. Linear Inequalities and Related Systems, pages 171– 181-> [2]).
- Il est mentionné dans ce mémoire [3] (p. 18) avec Ford-Bellman, mais non utilisés, car l’algorithme de Dijkstra leur est préféré dans le cas étudié (pas de poids négatifs).
schlum =^.^= 12 août 2012 à 02:01 (CEST)
- L´algorithme de Dantzig est cité dans des ouvrages concernant l'information géographique [4], la théorie des graphes [5], la simulation numérique [6], et les transports [7]. Est-ce bien de cet algorithme que l'article parle ?--Silex6 (d) 12 août 2012 à 15:27 (CEST)
- Je ne pense pas :
- Source 1 [8], je cite la fin « this algorithm is very similar to the standard Dijkstra procedure ». La description indique qu'on part d'une source et qu'on sélectionne à chaque fois un sommet qui a la distance minimum à la source parmi ceux qu'on a pas encore atteints. Donc non, ce n'est pas pareil.
- Source 2 [9] : c'est pour calculer les plus courtes distances entre toutes les paires de points par programmation dynamique (même chose que l'algorithme trouvé par MathsPoetry). Pas pareil non plus.
- Source 3 [10] : Dantzig 1960 fait probablement référence à On the shortest route through a network [11]. Comme je l'avais déjà dit à la précédente PàS, ce n'est pas le même algo qu'ici. C'est peut-être le même que celui de la source 1 d'ailleurs, mais il faudrait avoir accès à toutes les pages pour vérifier...
- Orlodrim [discuter] 12 août 2012 à 15:53 (CEST)
- Je ne connais absolument rien au sujet, mais il semble que la requête "Algorithm" "Dantzig-Ford" sur Google Livres renvoie vers plusieurs publications pertinentes (presque toujours se référant également à Fulkerson), non? El Comandante (d) 16 août 2012 à 22:39 (CEST)
- Il n'y a aucun doute qu'il existe une publication de Ford, Dantzig et Fulkerson nommée "A primal-dual algorithm for linear programs". Mais :
- Est-ce que cette publication décrit l'algorithme de Dantzig-Ford dont on parle ici ? (si c'est le cas, ce n'est en tout cas pas le sujet principal de l'article, au vu des pages de l'article consultables sur Google Books ; par ailleurs, les citations dans le lien que tu donnes ne mentionnent pas non plus l'article pour cet algorithme de graphe, mais pour la résolution de problèmes de programmation linéaire)
- En admettant que oui, la description d'un algorithme dans un article de recherche est-elle suffisante pour créer un article sur Wikipédia ? (mon avis est : évidemment pas. Il y a de nombreux articles qui décrivent des avancées mineures, que d'autres articles rendent obsolètes ou exposent de façon plus simple, ou qui sont simplement faux. J'attends d'un article de Wikipédia sur un algorithme de graphes qu'il dise si l'algorithme est utilisé en pratique, comment il se compare à d'autres, etc. Cela n'est possible que si l'algorithme est expliqué, ou du moins cité et commenté, dans un livre de théorie des graphes. Ce n'est apparemment pas le cas ici.)
- Orlodrim [discuter] 17 août 2012 à 00:48 (CEST)
- Il n'y a aucun doute qu'il existe une publication de Ford, Dantzig et Fulkerson nommée "A primal-dual algorithm for linear programs". Mais :
- Je ne connais absolument rien au sujet, mais il semble que la requête "Algorithm" "Dantzig-Ford" sur Google Livres renvoie vers plusieurs publications pertinentes (presque toujours se référant également à Fulkerson), non? El Comandante (d) 16 août 2012 à 22:39 (CEST)
- Pour ma part l'article est admissible s'il restitue de manière convaincante [12],[13] et [14], mais en admettant que ces trois sources soient suffisantes particulièrement eut égard à la dénomination de l'algorithme, laquelle pourrait s'avérer n'être qu'un choix d'usage pratique parfois utilisé dans l'enseignement mais sans valeur historique réelle. Ce qui est ce que semble indiquer son absence en bibliographie. Voir aussi [15]? --Askedonty (d) 18 août 2012 à 14:48 (CEST)
- La première source [16] semble assez solide, mais c'est frustrant qu'elle ne donne toujours pas plus de contexte. Orlodrim [discuter] 18 août 2012 à 19:54 (CEST)
- En première page on lit "Les chapitres VI à X, XII et XIII de ce polycopié sont extraits du livre « Méthodes d’optimisation combinatoire » d’I. Charon, A. Germa et O. Hudry, Masson, Paris, 1996." et cet algorithme est dans le chapitre VII. Il y a donc plus qu'un vague cours.Claudeh5 (d) 19 août 2012 à 16:16 (CEST)
- Je n'ai pas parlé de « vague cours » mais de « source assez solide ». Cependant, cette source ne donne pas beaucoup plus d'éléments que ce qu'il y a actuellement, et qui est très incomplet (comme le dit Silex6 : « analyse de la complexité, applications pratiques, comparaison avec d'autres algorithmes »). Raison pour laquelle j'en reste à « neutre ». Orlodrim [discuter] 20 août 2012 à 18:54 (CEST)
- En première page on lit "Les chapitres VI à X, XII et XIII de ce polycopié sont extraits du livre « Méthodes d’optimisation combinatoire » d’I. Charon, A. Germa et O. Hudry, Masson, Paris, 1996." et cet algorithme est dans le chapitre VII. Il y a donc plus qu'un vague cours.Claudeh5 (d) 19 août 2012 à 16:16 (CEST)
- La première source [16] semble assez solide, mais c'est frustrant qu'elle ne donne toujours pas plus de contexte. Orlodrim [discuter] 18 août 2012 à 19:54 (CEST)
- Je ne pense pas :
Bonjour. je profite de la discussion ci-dessus pour vous rappeler l'existence de cette section: Wikipédia:Notoriété en informatique#notoriété d'un algorithme.--Silex6 (d) 20 août 2012 à 12:06 (CEST)
Avis
modifierEntrez ci-dessous votre avis sur l’admissibilité du thème à l’aune de l’existence de sources extérieures et sérieuses ou des critères d'admissibilité des articles. Il est recommandé d'accentuer l'idée principale en gras (conserver, fusionner, déplacer, supprimer, etc.) pour la rendre plus visible. Vous pouvez éventuellement utiliser un modèle. N’oubliez pas qu’il est obligatoire d’argumenter vos avis et de les signer en entrant quatre tildes (~~~~).
Conserver
modifier- Conserver A partir du moment qu'il a des sources sérieuses, même s'il est rare, ancien, abandonné au profit d'un autre moins contraignant (mais pas fondamentalement meilleur), il a sa place.Claudeh5 (d) 12 août 2012 à 17:31 (CEST)
- trouvé dans Berge, graphes et hypergraphes, p56 "Le problème du plus court chemin a été résolu de façon analogue par de nombreux auteurs; le plus rapide moyen de calcul semble être l'algorithme suivant proposé par G. Dantzig" (ref à G. B. Dantzig, On the shortest route through a network, Manag. #:Sc., T6, 1960, 187-189.
- Berge, graphs, edition 1991, p57. — Le message qui précède, non signé, a été déposé par Claudeh5 (discuter), le 12 août 2012 à 17:56
- Comme indiqué ci-dessus, il y a bien un « algorithme de Dantzig » (pas « Ford-Dantzig ») qui a été publié en 1960 dans On the shortest route through a network, mais il n'a pas de rapport avec celui qui est le sujet de cet article. C'est un algorithme de type Dijkstra. Orlodrim [discuter] 12 août 2012 à 18:01 (CEST)
- trouvé dans Berge, théorie des graphes et ses applications, p68: "algorithme pour le problème 3 (L. Ford) "(algorithme de plus court chemin) ref: L.R. Ford, network flow theory, Rand Corp paper, P-923, 1956.Claudeh5 (d) 12 août 2012 à 18:37 (CEST)
- Est-ce que cet article a un rapport avec l'algorithme de Ford-Dantzig, avec l'algorithme de Bellman-Ford, ou aucun des deux ? Orlodrim [discuter] 12 août 2012 à 18:47 (CEST)
- avec l'algorithme de Bellman-Ford.Claudeh5 (d) 12 août 2012 à 18:54 (CEST)
- Cela dit, la "distance" entre l'algorithme de Dantzig (1960), Dantzig-Ford, de Ford (1956) et de Bellman-Ford me semble faible. Je pencherai pour une assimilation entre Dantzig (1960) et Ford (1956).Claudeh5 (d) 12 août 2012 à 19:13 (CEST)
- Manifestement, il y a plusieurs articles de recherche décrivant des algorithmes assez similaires. Pour éviter tout travail inédit, nous devrions nous fier aux ouvrages de synthèse sur les algorithmes de graphe (depuis 1960, le domaine est bien balisé tout de même) et voir quels algorithmes ils retiennent. Je ne suis pas convaincu qu'il y ait un "algorithme de Dantzig-Ford" dans le lot.
- Concrètement, connaissez-vous une source qui permettrait de rédiger un article sérieux (donner une analyse de complexité et des éléments de comparaison avec les autres algorithmes de recherche de plus court chemin) sur l'algorithme décrit dans cet article ? Orlodrim [discuter] 12 août 2012 à 20:13 (CEST)
- Est-ce que cet article a un rapport avec l'algorithme de Ford-Dantzig, avec l'algorithme de Bellman-Ford, ou aucun des deux ? Orlodrim [discuter] 12 août 2012 à 18:47 (CEST)
- Conserver par précaution, ça laisse une chance d'amélioration,je vois des inconvénients à le supprimer, je n'en vois pas à le garder. Chassaing 13 août 2012 à 01:07 (CEST)
- Conserver comme Chassaing.--Aghuk (d) 15 août 2012 à 11:31 (CEST)
Supprimer
modifier- Supprimer Apparemment, personne ne semble réellement certain de quoi il s'agit. Voilà qui en dit long sur l'absence de notoriété. Un développement ne pourrait être àmha que du TI pur. --Chris a liege (d) 13 août 2012 à 00:33 (CEST)
- Supprimer Pas de source secondaire notable remarquant ou analysant cet algorithme. Il existe des dizaines de milliers de travaux originaux, éventuellement repris dans quelques mémoires, mais qui ne peuvent faire l'objet d'un article de WP chacun, car sans source secondaire il est d'une part très difficile de juger objectivement de leur pertinence, et d'autre part il est difficile et hasardeux de rédiger un article encyclopédique synthétique à leur sujet. --Jean-Christophe BENOIST (d) 12 août 2012 à 11:14 (CEST)
- livre « Méthodes d’optimisation combinatoire » d’I. Charon, A. Germa et O. Hudry, Masson, Paris, 1996.Claudeh5 (d) 19 août 2012 à 16:19 (CEST)
- Supprimer absence de sources secondaires démontrant la notoriété de cet algorithme - analyse de la complexité, applications pratiques, comparaison avec d'autres algorithmes, etc.--Silex6 (d) 12 août 2012 à 20:18 (CEST)
- livre « Méthodes d’optimisation combinatoire » d’I. Charon, A. Germa et O. Hudry, Masson, Paris, 1996.Claudeh5 (d) 19 août 2012 à 16:19 (CEST)
- Supprimer Sources insuffisantes (inexistantes dans l'article, insuffisantes sur le Web). S'il existe un algorithme de Dantzig, l'existence d'un algorithme de Dantzig-Ford ou Ford-Dantzig n'est pas vraiment attestée de faço probante. Deuxtroy (d) 16 août 2012 à 09:45 (CEST)
- Si ! livre « Méthodes d’optimisation combinatoire » d’I. Charon, A. Germa et O. Hudry, Masson, Paris, 1996.Claudeh5 (d) 19 août 2012 à 16:19 (CEST)
Neutre
modifier- Neutre Semble exister, mais être une version édulcorée de Bellman-Ford très peu utilisée. Est-ce que ça mérite une page ? Un paragraphe dans la page de Bellman-Ford ? Rien ? Difficile à dire… schlum =^.^= 12 août 2012 à 02:03 (CEST)
- J'avais dit n'importe quoi tout à l'heure, en fait la ligne "ajuster Long(y) pour les sommets atteignables depuis y dans l'arbre" fait que le comportement de l'algorithme est assez différent. Comme j'ai spammé tout le monde, je vais laisser la procédure continuer, mais je ne crois pas que le mentionner dans la page sur Bellman-Ford soit une bonne idée. Orlodrim [discuter] 12 août 2012 à 02:43 (CEST)
- Neutre Passage en neutre. Orlodrim [discuter] 12 août 2012 à 02:38 (CEST)
- Neutre J'ai vrai du mal à me faire un avis (tout comme schlum et Orlodrim) --PierreSelim [let discussion = fun _ ->] 12 août 2012 à 10:54 (CEST)
- Neutre
Conservermais diviser en Algorithme de Dantzig et Algorithme de Ford ? Il semblerait que ça soit deux algorithmes connus proches, mais différents : http://ufrsciencestech.u-bourgogne.fr/master1/mi1-tc5/COURS_ALGO_HTML/cours_algo017.html . --MathsPoetry (d) 12 août 2012 à 13:49 (CEST)- Non, l'algorithme de Dantzig décrit dans ce cours n'a pas de rapport avec l'article de Ford-Dantzig décrit là : c'est un algorithme qui calcule les plus courts chemins entre toutes les paires de sommets et n'utilise pas du tout le même principe. Et l'algorithme de Ford de ce cours correspond à notre algorithme de Bellman-Ford Orlodrim [discuter] 12 août 2012 à 14:33 (CEST)
- OK, merci, j'avais la flemme de regarder les détails, je sais que j'aurais dû . Je repasse mon avis en neutre. --MathsPoetry (d) 12 août 2012 à 14:36 (CEST)
- Tout cela montre les errements possible quand il n'y a pas de source secondaire notable. Nous sommes obligés de faire une somme de travail (inédit ?) et de recherche qui va au delà de ce qu'un contributeur de WP devrait faire. --Jean-Christophe BENOIST (d) 12 août 2012 à 16:11 (CEST)
- Oui. D'un autre côté, il me semble que Olodrim a à présent rassemblé assez d'informations pour construire une belle... page d'homonymie --MathsPoetry (d) 12 août 2012 à 18:56 (CEST)
- Tout cela montre les errements possible quand il n'y a pas de source secondaire notable. Nous sommes obligés de faire une somme de travail (inédit ?) et de recherche qui va au delà de ce qu'un contributeur de WP devrait faire. --Jean-Christophe BENOIST (d) 12 août 2012 à 16:11 (CEST)
- OK, merci, j'avais la flemme de regarder les détails, je sais que j'aurais dû . Je repasse mon avis en neutre. --MathsPoetry (d) 12 août 2012 à 14:36 (CEST)
- Non, l'algorithme de Dantzig décrit dans ce cours n'a pas de rapport avec l'article de Ford-Dantzig décrit là : c'est un algorithme qui calcule les plus courts chemins entre toutes les paires de sommets et n'utilise pas du tout le même principe. Et l'algorithme de Ford de ce cours correspond à notre algorithme de Bellman-Ford Orlodrim [discuter] 12 août 2012 à 14:33 (CEST)
- Neutre Pas connu dans mon entourage, mais ce n'est pas suffisant pour me faire pencher en faveur de la suppression. — Arkanosis ✉ 13 août 2012 à 20:04 (CEST)
- Neutre Je ne sais que dire. Cet algorithm m'est inconnu, la source est vague, il n'y a pas d'article de Wikipedia anglophone...Malosse (d) 14 août 2012 à 05:00 (CEST)
Avis non décomptés
modifierException étant faite pour le créateur de l’article, les avis d’utilisateurs récemment inscrits (moins de cinquante contributions...) ou non identifiables (IP, opinions non signées...) ne sont en principe pas pris en compte. Si vous êtes dans ce cas, vous pouvez toutefois participer aux discussions ou vous exprimer ci-dessous pour information :
Ancienne discussion
modifierL'admissibilité de la page « Algorithme de Dantzig-Ford » est débattue.
Consignes quant à cette procédure :
- Qui peut participer ?
- Le créateur de la page et les contributeurs ayant un compte ayant fait au moins cinquante contributions aux articles (espace principal) de fr.wikipedia.org au lancement de cette procédure peuvent exprimer leur avis.
- Les avis des personnes n’ayant pas de compte ou un compte ayant moins de 50 contributions sont déplacés dans « Avis non décomptés » et ne sont en principe pas pris en considération. Lors de la clôture, les avis sans argumentaire sont également déplacés et ne sont pas pris en compte.
- Durée de la consultation
- Si un consensus clair s'est dégagé le 25 août après l'expiration de sept jours pleins de débat (168 heures), un contributeur ayant réalisé au moins 500 modifications et ayant 3 mois d'ancienneté (utilisateur autopatrolled) qui n'aura pas pris part au débat peut clore la proposition et indiquer si la page est conservée ou supprimée (la suppression devant être demandée à un administrateur). Dans le cas contraire, la discussion se poursuit et peut être close à partir du 1 septembre.
Important
- Copiez le lien *{{L|Algorithme de Dantzig-Ford}} et collez-le dans la section du jour de la page principale « Débat d'admissibilité ». Attention, un décalage d'un jour est possible en fonction de la mise en page.
- Avertissez le créateur, les principaux contributeurs de l’article et, si possible, les projets associés en apposant le message {{subst:Avertissement débat d'admissibilité|Algorithme de Dantzig-Ford}} sur leur page de discussion.
Conclusion
Raison : Pas de consensus pour une suppression et discussion qui tend à indiquer une pertinence à cet article avec un renommage conseillé Proposé par : - Zil (d) 17 août 2010 à 21:14 (CEST)
Voilà, cet algorithme initialement nommé Danteig-Ford et renommé Dantzig-Ford par Esprit Fugace (d · c · b) n'existe pas sur les listes d'algorithmes des autres wikipédia comme en:List_of_algorithms, il n'est pas présent sur google books (on trouve un Dantzig, Ford, Fulkerson comme ici mais qui parle de linéarité au niveau programmation. Et enfin, il n'y a rien sur google tout court. Donc soit, c'est un hoax, soit le notoriété de cet algorithme n'est pas clairement établie, soit il faut sourcer un peu cet article.
Discussions
modifierToutes les discussions vont ci-dessous.
Ce n'est pas un Hoax, il me semble par contre que c'est l'aglorithme de Ford-Dantzig [17]. Pour info le papier de Dantzig, et al. en liens ne parle pas de linéarité au niveau de la programmation mais de programmation linéaire. Je pense honnêtement que le sujet est admissible, il faudra par contre renommer l'article en fonction (d'ailleurs l'article commence par L'algorithme de Ford-Dantzig). -- PierreSelim [mayday mayday!] 18 août 2010 à 12:10 (CEST)
Pour que l'article soit vraiment intéressant il manque toutes les considérations d'optimisation des temps de calcul. Il serait plus encyclopédique de présenter une bonne description théorique plutôt que du pseudo-code. Mais à côté de ça il y a des sujets sur lesquels il vaudrait mieux être prudent par rapport à Google. Il y en a une autre qui est en train d'être supprimé parce-que les votants ne comprennent pas de quoi il parle. De son côté, Ford-Fulkerson sert à résoudre le problème du flot maximal; ce qui est le genre de concept dont dépend l'existence même de certains systèmes, y compris celui-là. Le même algorithme est connu sous le nom Dantzig-Ford-Fulkerson et encore F-D ou D-F (plein texte), et même, "de Dantzig". Il ne s'agit pas de programmation linéaire. --Askedonty (d) 23 août 2010 à 10:59 (CEST)
Bonjour, j'ai trouvé des références mentionnant cet algorithme (dit de Dantzig, 1960) dans : Berge, C. Gauthier-Villars (Ed.) Graphes 1973, chap4,p 56 en référence à Dantzig, G. On the shortest route through a network Manag. Sc., 1960, 6, 187-189. Il est donc sensé de conserver cet article en le renommant. Rikilabellevie (d) 2 septembre 2010 à 14:55 (CEST)
- Bonjour. L'algorithme décrit dans On the shortest route through a network n'est pas le même que celui dont il est question ici. D'après ce que j'ai compris, c'est plutôt une version naïve de Dijsktra (complexité quadratique, poids forcément positifs ; les deux premières pages sont disponibles sur Google Books [18] et les deux autres ne font que décrire un exemple).
C'était juste une remarque en passant parce que sur Dantzig-Ford, je n'ai pas d'avis. C'est quand même bizarre, non, un algorithme avec zéro hit Google en anglais ? C'est pas juste un exercice de licence ? Orlodrim [discuter] 6 septembre 2010 à 20:48 (CEST)
Avis
modifierEntrez ci-dessous votre avis sur l’admissibilité du thème à l’aune de l’existence de sources extérieures et sérieuses ou des critères d'admissibilité des articles. Il est recommandé d'accentuer l'idée principale en gras (conserver, fusionner, déplacer, supprimer, etc.) pour la rendre plus visible. Vous pouvez éventuellement utiliser un modèle. N’oubliez pas qu’il est obligatoire d’argumenter vos avis et de les signer en entrant quatre tildes (~~~~).
Conserver
modifier- Conserver et Renommer. cf Discussion -- PierreSelim [mayday mayday!] 18 août 2010 à 12:11 (CEST)
- Même avis que Pierre. Il aurait été préférable que Zig demande des explications à Esprit Fugace plutôt que de lancer une PàS. Philippe Giabbanelli (d) 18 août 2010 à 13:21 (CEST)
- Idem PierreSelim. Cantons-de-l'Est 19 août 2010 à 11:19 (CEST)
Supprimer
modifier- Supprimer Aucune source, à part Wikipédia et des références à Wikipedia, ce qui ne correspond pas aux critères du concept nouveau. Chris a liege (d) 18 août 2010 à 01:45 (CEST)
- Supprimer Cet algorithme ne semble pas être décrit dans les ouvrages de référence sur les graphes.
Note : la seule différence avec l'algorithme de Bellman-Ford est l'ordre dans lequel on relâche les arêtes : pour Bellman-Ford, l'ordre est fixe ; pour celui-ci, l'ordre est quelconque mais on met à jour la distance de tous les successeurs dans l'arbre à chaque opération. Je doute donc fortement que cet algorithme ait un intérêt pratique. Ce n'est pas une raison de le supprimer, mais juste un élément qui me pousse à croire que c'est plutôt une variante exotique de Bellman-Ford qu'un algorithme classique dans le domaine. Orlodrim [discuter] 7 septembre 2010 à 13:09 (CEST)
Rediriger
modifier- Transformer en redirection D’après mes lointains souvenirs de cours d’optimisation, il s’agit simplement de l’algorithme du simplexe… schlum =^.^= 24 août 2010 à 01:55 (CEST)
- A priori ce n'est pas le cas: l'algorithme du simplexe de Dantzig (à ne pas confondre avec celui de Nelder-Mead) est l'agorithme de référence pour la résolution de problèmes de programmation linéaire, celui de Ford-Dantzig est un algorithme pour trouver le plus court chemin dans un graphe (graphe orienté, avec ou sans circuit, poids positifs et négatifs). -- PierreSelim [mayday mayday!] 26 août 2010 à 18:05 (CEST)
- C’est loin tout ça… Mais « trouver un chemin optimal (le plus court ou bien le plus long) entre deux sommets d'un graphe orienté » n’est-ce pas une application du « simplexe » ? schlum =^.^= 2 septembre 2010 à 02:05 (CEST)
- En effet, et ça me revient aussi tellement c'est compliqué de réaliser des graphes en poids et que comme ça sert à cerner des figures en fait, on pourrait aussi bien les appeler : "Algorithmes de la Pierre Philosophale". app, c'est joli, non ? Askedonty (d) 4 septembre 2010 à 23:08 (CEST)
- C’est loin tout ça… Mais « trouver un chemin optimal (le plus court ou bien le plus long) entre deux sommets d'un graphe orienté » n’est-ce pas une application du « simplexe » ? schlum =^.^= 2 septembre 2010 à 02:05 (CEST)
- A priori ce n'est pas le cas: l'algorithme du simplexe de Dantzig (à ne pas confondre avec celui de Nelder-Mead) est l'agorithme de référence pour la résolution de problèmes de programmation linéaire, celui de Ford-Dantzig est un algorithme pour trouver le plus court chemin dans un graphe (graphe orienté, avec ou sans circuit, poids positifs et négatifs). -- PierreSelim [mayday mayday!] 26 août 2010 à 18:05 (CEST)