Discussion:Algorithme de Dantzig-Ford/Admissibilité

Dernier commentaire : il y a 12 ans par Orlodrim dans le sujet Algorithme de Dantzig-Ford
Autres discussions [liste]
  • 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.

Algorithme de Dantzig-Ford

modifier

Proposé par : Orlodrim [discuter] 12 août 2012 à 00:42 (CEST)Répondre

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é 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

Le débat a abouti à la suppression de cette page.

Suppression traitée par Kyro me parler le 26 août 2012 à 02:40 (CEST)

Raison : Hors critères

Discussions

modifier

Toutes 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)Répondre

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)Répondre
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)Répondre
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)Répondre
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)Répondre
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)Répondre
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)Répondre
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)Répondre
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)Répondre

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)Répondre

Entrez 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
  1.  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)Répondre
    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)Répondre
    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)Répondre
    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)Répondre
    avec l'algorithme de Bellman-Ford.Claudeh5 (d) 12 août 2012 à 18:54 (CEST)Répondre
    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)Répondre
    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)Répondre
  2.  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)
  3.  Conserver comme Chassaing.--Aghuk (d) 15 août 2012 à 11:31 (CEST)Répondre

Supprimer

modifier
  1.  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)Répondre
  2.  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)Répondre
    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)Répondre
  3.  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)Répondre
    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)Répondre
  4.  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)Répondre
    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)Répondre
  1.  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)Répondre
    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)Répondre
  2.  Neutre Passage en neutre. Orlodrim [discuter] 12 août 2012 à 02:38 (CEST)Répondre
  3.  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)Répondre
  4.  Neutre  Conserver mais 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)Répondre
    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)Répondre
    OK, merci, j'avais la flemme de regarder les détails, je sais que j'aurais dû (Smiley oups). Je repasse mon avis en neutre. --MathsPoetry (d) 12 août 2012 à 14:36 (CEST)Répondre
    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)Répondre
    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 Émoticône sourire --MathsPoetry (d) 12 août 2012 à 18:56 (CEST)Répondre
  5.  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)Répondre
  6.  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)Répondre

Avis non décomptés

modifier

Exception é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

modifier
Revenir à la page « Algorithme de Dantzig-Ford/Admissibilité ».