Certains algorithmes de débit maximal de pointe sont-ils pratiques?

30

Pour le problème du débit maximal , il semble y avoir un certain nombre d'algorithmes très sophistiqués, avec au moins un développé aussi récemment que l'année dernière. Le débit maximal d'Orlin en O (mn) temps ou mieux donne un algorithme qui s'exécute en O (VE).

D'un autre côté, les algorithmes que je vois le plus souvent implémentés sont (je ne prétends pas avoir fait une recherche exhaustive; c'est juste par observation occasionnelle):

  • Edmonds-Karp: ,O(VE2)
  • Push-relabel: ou utilisant la sélection de sommets FIFO,O ( V 3 )O(V2E)O(V3)
  • Algorithme de Dinic: .O(V2E)

Les algorithmes avec un meilleur temps de fonctionnement asymptotique ne sont-ils tout simplement pas pratiques pour les tailles de problème dans le monde réel? De plus, je vois que les "arbres dynamiques" sont impliqués dans plusieurs algorithmes; sont-ils déjà utilisés dans la pratique?

Remarque: cette question a été initialement posée sur le débordement de pile, ici , mais on m'a dit que ce serait mieux ici.

EDIT : J'ai posé une question connexe sur cs.stackexchange , en particulier sur les algorithmes qui utilisent des arbres dynamiques (aka arbres coupés de liens), qui peuvent être intéressants pour les personnes qui suivent cette question.

ds.algorithms graph-algorithms application-of-theory max-flow Rob Lachlan
la source
1
parlant dans un sens général, si un algorithme est "pratique" vs s'il est "implémenté" sont un peu différents. dans l'idéal, les auteurs publieraient des implémentations de leurs propres algorithmes, auquel cas il serait généralement «pratique» de les utiliser. unf c'est souvent plus l'exception dans la littérature TCS. mais il n'est souvent pas "pratique" de "mettre en œuvre" les algorithmes d'autres auteurs uniquement dans les descriptions écrites dans des articles écrits en pseudocode, qui sont parfois significativement ou très complexes ... une mise en œuvre réussie comprend de bons tests de correction, un processus parfois intimidant ...
vzn
3
Andrew Goldberg avait l'habitude d'avoir une très bonne base de code pour différentes variantes de flux max basé sur son travail de réétiquetage push. J'ai utilisé le code dans le passé, et c'était très propre. Malheureusement, le site semble avoir disparu.
Suresh Venkat
3
@vzn Je voudrais savoir si les algorithmes se prêtent à une implémentation pratique. Il existe des algorithmes qui ne le font pas, et certaines personnes ont décidé d'appeler ces «algorithmes galactiques», car ils ont un excellent comportement asymptotique mais tellement de frais généraux qu'il n'y a actuellement aucun avantage pratique à les mettre en œuvre. (Les termes d'ordre inférieur importent, après tout.) La multiplication matricielle est le meilleur exemple auquel je puisse penser, où les meilleures solutions asymptotiquement ne voient jamais d'utilisation pratique. Je suis curieux de savoir si Max Flow est une situation similaire.
Rob Lachlan
5
si un algorithme est "pratique" vs s'il est "implémenté" sont un peu différents. - C'est vrai. Un algorithme peut être implémenté sans être pratique, mais pas l'inverse.
Jeffε
2
Voici le code de l' étude expérimentale des algorithmes de coupe minimale .
Austin Buchanan

Réponses:

22

Je suis l'un des auteurs de l'article lié ci-dessus.

Je veux juste mentionner que nous avons utilisé `` l'état de l'art '' pour désigner des algorithmes (avec des implémentations accessibles au public) qui fonctionnent bien sur les instances de flux maximal résultant de la vision par ordinateur.

Je voudrais également ajouter que dans ce contexte étroit (mais pratique), les algorithmes qui fonctionnent bien sont souvent ceux qui ont de mauvaises garanties théoriques. Par exemple, ref [5] de notre article (algorithme Boykov-Kolmogorov) est largement utilisé dans la communauté de la vision par ordinateur, mais n'a pas de limite d'exécution fortement polytime.

Enfin, si quelqu'un est intéressé, les données de nos expériences sont disponibles ici: http://ttic.uchicago.edu/~dbatra/research/mfcomp/index.html

Le code sera également bientôt disponible également.

Dhruv Batra
la source
très chouette que tu aies rejoint le groupe! Bienvenue! une question sur le papier [depuis le 1er le trouver]. il serait très intéressant d'en savoir plus sur le processus de sélection des algorithmes utilisés dans l'article - il ne semblait pas en dire plus à ce sujet. peut-être pourriez-vous partager quelque part "en arrière-plan" des notes de fond quelque part [par exemple une page Web?] sur les algorithmes qui ont été sélectionnés, qui ont été omis, pourquoi, quels défis il y avait dans l'obtention / l'exécution des implémentations, ce que vous pensez des plus exotiques des algorithmes tels que le récent Orlins et leurs perspectives de mise en œuvre éventuelle, etc.
vzn
7

il existe plusieurs façons de répondre à cette question mais pas nécessairement une réponse consensuelle. généralement, les algorithmes qui ont été mis en œuvre et diffusés pour la distribution publique sont «pratiques». cependant, certains algorithmes qui ont été conçus mais pas encore mis en œuvre peuvent être pratiques mais "le jury est absent" pour ainsi dire. **

une bonne stratégie à des fins pratiques consiste à rechercher une enquête. aussi pour ceux qui s'intéressent aux algorithmes pratiques, les points de référence par rapport aux données du monde réel peuvent être une excellente indication quant à leur comportement "réel" attendu.

une étude comparative peut être suffisante, mais elle se trompera du côté des algorithmes viables. il s'agit d'une analyse empirique récente et approfondie de 14 algorithmes de flux max «à la pointe de la technologie» comparés empiriquement aux instances de traitement de la vision, où le flux max a de nombreuses applications. «état de l'art» désigne les algorithmes «mis en œuvre».

[1] MaxFlow Revisited: une comparaison empirique des algorithmes Maxflow pour les problèmes de vision dense par Verma et Batra, 2012

** certains algorithmes théoriques appartiennent à une catégorie de plus en plus répandue dans la communauté TCS sous le nom informel de "galactique", mais malheureusement, les auteurs du TCS n'auto-étiquettent pas directement leurs algorithmes dans cette catégorie, et il n'y a pas de critères publiés ou généralement acceptés pour des algorithmes "galactiques", bien qu'il y ait une référence dans les blogs .

le caractère pratique dans ce sens est peut-être une nouvelle dimension émergente pour l'étude théorique. dans l'idéal, il y aurait une étude des algorithmes de flux maximum spécifiquement sur cet axe / critère "pratique", mais cela n'existe probablement pas au moment de l'écriture. c'est un concept plus récemment reconnu / reconnu dans TCS qui n'a pas encore été complètement formalisé (contrairement par exemple à l'acceptation répandue des algorithmes P comme "efficaces").

vzn
la source
3
+1. Je ne sais pas pourquoi cela a été rejeté; Je lis le document auquel vous avez fait un lien, et il m'a été très utile de voir quelles sont les approches pratiques, du moins dans ce domaine problématique.
Rob Lachlan
3
Robert Sedgewick a déclaré dans un discours assez récent que le concepteur d'algorithmes qui n'exécute pas d'expériences risque de se perdre dans l'abstraction. La discussion porte sur la recherche de chemins dans les graphiques et est également quelque peu liée à maxflow. Cela ne répond pas à la question, mais pourrait être intéressant pour quelqu'un.
Juho
5
@Rob, la seule partie pertinente de cette réponse est un lien vers le document et il n'y a pas grand-chose dans la réponse expliquant pourquoi ce document est lié du tout. Je suppose que l'OP a trouvé le lien par Google et ne l'a pas lu. Le reste de la réponse est quelques remarques générales et commentaires indiquant le point de vue personnel d'OP sur des questions sur lesquelles il n'est pas un expert et pas vraiment pertinent ici. Les réponses ne sont pas des articles de blog. Un lien vers un article pertinent peut être un bon commentaire, mais il ne donne pas de réponse. C'est une mauvaise réponse si elle en est une. C'est pourquoi je l'ai rejeté.
Kaveh
2
@Kaveh assez juste. J'ai trouvé le document comme un indicateur utile de ce que les gens considèrent comme des algorithmes pratiquement utiles. Je suis d'accord que beaucoup reste sans réponse.
Rob Lachlan
3
Je ne comprends pas non plus les downvotes. Il n'y a aucune raison de croire que l'affiche n'a PAS lu l'article lié, et il semble pertinent. Je peux voir le désir de ne pas voter positivement, mais pas un vote négatif.
Suresh Venkat