Pour quels algorithmes existe-t-il un grand fossé entre l'analyse théorique et la réalité?

52

Deux manières d’analyser l’efficacité d’un algorithme sont:

  1. mettre une limite supérieure asymptotique sur son temps d'exécution, et
  2. pour l'exécuter et collecter des données expérimentales.

Je me demande s’il existe des cas connus où il existe un écart important entre (1) et (2). Par cela, je veux dire que soit (a) les données expérimentales suggèrent un asymptotique plus étroit, soit (b) il existe des algorithmes X et Y tels que l'analyse théorique suggère que X est bien meilleur que Y et les données expérimentales suggèrent que Y est bien meilleur que X.

Comme les expériences révèlent généralement un comportement de cas moyen, je pense que les réponses les plus intéressantes se réfèreront aux bornes supérieures du cas moyen. Cependant, je ne veux pas exclure des réponses potentiellement intéressantes qui parlent de différentes limites, telles que la réponse de Noam à propos de Simplex.

Inclure les structures de données. S'il vous plaît mettez un algo / ds par réponse.

Radu GRIGore
la source
Il serait utile que vous clarifiiez de quel type de limite supérieure vous parlez. Ne parlez-vous que des problèmes pour lesquels il existe un écart important entre les limites supérieures et inférieures connues pour la complexité temporelle dans le cas le plus défavorable? Ou encore, incluez-vous également des problèmes pour lesquels des limites serrées concernant la complexité temporelle dans le cas le plus défavorable sont connues, mais les durées de fonctionnement typiques sont considérablement plus rapides? Il peut être plus intéressant de considérer la complexité lissée plutôt que la complexité du pire des cas. Les résultats expérimentaux sur des entrées «typiques» ou des entrées aléatoires n'infirment guère l'existence d'entrées pathologiques.
James King
Dans ce cas, je pense que deux questions doivent être posées séparément: une sur les écarts entre la complexité du cas le plus défavorable et la complexité du cas moyen / lissée, et une autre sur les écarts entre la complexité théorique du cas moyen / lissée et les résultats expérimentaux pratiques. Edit: vous avez fait un edit adressant ceci pendant que j'écrivais mon commentaire :)
James King

Réponses:

37

L'exemple le plus frappant est bien sûr la méthode Simplex qui fonctionne rapidement dans la pratique, suggérant la poly-timeness, mais prend un temps exponentiel en théorie. Dan Spielman vient de recevoir le prix Nevanlinna dans une large mesure pour avoir expliqué ce mystère.

Plus généralement, de nombreux cas de programmation Integer peuvent être résolus très bien avec les solveurs IP standard, par exemple les enchères combinatoires pour la plupart des distributions tentées sur des entrées de taille significative peuvent être résolues - http://www.cis.upenn.edu/~mkearns /teaching/cgt/combinatorial-auctions-survey.pdf

Noam
la source
3
At-on trouvé une famille explicite de programmes linéaires pour lesquels simplex prend un temps exponentiel?
Opt
1
Pour autant que je sache, de nombreuses familles explicites nécessitent un temps exponentiel (par exemple, le premier énoncé donné par Klee et Minty: "Quelle est la qualité de l'algorithme simplex?", 1972). Cependant, le choix de la règle de pivot est pertinent pour ces résultats. Je suppose que la plupart des références à ces résultats se trouvent dans l'article de Spielman et Teng ( arxiv.org/abs/cs/0111050 ).
MRA
Il existe des limites inférieures pour certaines règles pivotantes spécifiques dans cet article. cs.au.dk/~tdh/papers/random_edge.pdf
Igor Shinkar
26

Bases de Groebner . Le temps d'exécution le plus défavorable est doublement exponentiel (en nombre de variables). Cependant, dans la pratique, en particulier pour les problèmes bien structurés, les algorithmes F4 et F5 sont efficaces (c'est-à-dire qu'ils se terminent assez rapidement). Il reste encore un domaine de recherche actif pour déterminer quelle devrait être la bonne conjecture en ce qui concerne la durée moyenne ou prévue. On suppose qu'il est lié, d'une manière ou d'une autre, au volume du polytope de Newton de l'idéal sous-jacent.

Jacques Carette
la source
Moyenne / prévue sous quelle distribution? Je pensais que même définir le temps de course attendu était difficile pour des problèmes algébriques ...
Joshua Grochow
1
Je ne sais pas pour les cas résolus rapidement par les méthodes F4 et F5, mais il est assez facile de construire un système de polynômes à plusieurs variables et à faible degré qui codent une instance SAT. Dans ce cas, je ne suis pas au courant que l'algorithme surpasse DPLL / DPLL +. Je voudrais vraiment en savoir plus sur les résultats expérimentaux sur ces choses!
MassimoLauria
@Joshua: à ce stade, toute distribution qui permet d'obtenir des résultats ... @ Massimo: le problème de codage X en tant qu'instance de Y ne bat presque jamais les algorithmes spécialisés pour X! Mais GB et DPLL étant essentiellement équivalents, je serais très surpris de voir une différence effective.
Jacques Carette
1
@ Massimo: Oui, le calcul en Go est NP-Hard. Selon la formulation. En fait, la plupart des questions (achèvement, adhésion idéale, champ fermé algébriquement vs booléens) sont complètes ou moins bien PSPACE (EXPSPACE complet). C’est-à-dire que les calculs en GB devraient être beaucoup plus difficiles que les problèmes NP-complets (et même dans ce cas, aucun algorithme tel que F5 ne surpasserait probablement les performances de DPLL).
Mitch
22

L' isomorphisme des graphes est un exemple remarquable et peu reconnu de ce phénomène . Le meilleur algorithme connu prend quelque chose comme le temps , mais l'isomorphisme des graphes a tendance à être résolu assez rapidement dans la pratique. O(2((nlogn)))

Je ne sais pas s'il y a un résultat formel sur la complexité moyenne / lissée du problème, mais je me souviens de l'avoir lu: un autre peut peut-être aider à signaler un résultat formel. Certes, il existe de nombreuses preuves expérimentales et beaucoup de solutions rapides. Je suis également curieux de savoir si cette propriété s'étend à d'autres membres de la famille GI-complete.

Anand Kulkarni
la source
1
Je ne connais aucune analyse lissée pour GI - ni même à quoi cela ressemblerait exactement - mais il existe une analyse de la mise en œuvre pratique la plus connue (nauty) qui montre qu'elle fonctionne dans le pire des cas, exponentielle. Bien sûr, Nauty n’implémente pas l’algorithme . Voir cstheory.stackexchange.com/questions/3128/… pour une référence. O(2nlogn)
Joshua Grochow
2
Oh! Vous pensez peut-être à Babai-Kucera, qui fournit un algorithme de cas moyen linéaire pour le GI: doi.ieeecomputersociety.org/10.1109/SFCS.1979.8
Joshua Grochow
Oui, Babai-Kucera est le bon! Merci pour la référence.
Anand Kulkarni
20

D'après David Johnson, une différence entre les ratios d'approximation théorique et expérimental: Le problème du voyageur de commerce: une étude de cas en optimisation locale, DS Johnson et LA McGeoch . Dans cet article, ils présentent des preuves expérimentales d'asymptotiques (puisque les expériences atteignent la taille N = 10 000 000!) Qui défient les asymptotiques théoriques: l'algorithme "Greedy" ou "Multi-Fragment" de Jon Bentley (rapport d'approximation dans le pire des cas au moins logN / loglogN) bat le plus proche Insertion et le double MST, qui ont tous deux un rapport d'approximation dans le cas le plus défavorable de 2.

Joshua Grochow
la source
20

Un autre exemple qui n'a pas été bien compris jusqu'à récemment est le temps d'exécution de l'algorithme k-means de Lloyd , qui (du point de vue pratique) est l'algorithme de choix pour la classification depuis plus de 50 ans. Ce n'est que récemment que, en 2009, il a été prouvé (par Vattani ) que, dans le pire des cas, l'algorithme de Lloyd nécessitait un nombre d'itérations exponentiel par rapport au nombre de points d'entrée. D'autre part, une analyse lissée (d' Arthur, Manthey et Röglin ) a également montré que le nombre d'itérations lissées est simplement polynomial, ce qui explique la performance empirique.

ARM
la source
10

Les corollaires de traversal, deque et de split de la conjecture d'optimalité dynamique pour les arbres évasés sont des exemples de telles lacunes. Les expériences sauvegardent l'allégation de temps linéaire, mais il n'y a pas de preuve connue.

Radu GRIGore
la source
3
Seth Pettie a prouvé que n opérations ne prenaient pas plus de temps que O (n alpha * (n)), où "alpha *" est la fonction de Ackermann inverse itérée, qui est un assez petit espace.
jbapple
9

Il y a un léger problème avec la question. Il existe en fait plus de deux manières d’analyser un algorithme, et l’une des méthodes théoriques négligées est la durée d’exécution attendue, et non la pire des exécutions. C'est vraiment ce comportement de cas moyen qui est pertinent pour faire des expériences. Voici un exemple très simple: Imaginons que vous disposiez d’un algorithme pour une entrée de taille n, qui prend un temps n pour chaque entrée possible de taille n, à l’exception d’une entrée spécifique de chaque longueur qui prend un temps de 2 ^ n. Écoutez, le temps d'exécution le plus défavorable est exponentiel, mais le cas moyen est [(2 ^ n -1) n + (2 ^ n) 1] / (2 ^ n) = n - (n-1) / 2 ^ n qui limites à n. Il est clair que les deux types d'analyse donnent des réponses très différentes, mais il faut s'y attendre, car nous calculons des quantités différentes.

En exécutant l'expérience plusieurs fois, même si nous prenons le temps d'exécution le plus long pour l'échantillon, nous n'échantillons qu'une petite partie de l'espace des entrées possibles. Par conséquent, si les instances matérielles sont rares, nous risquons de les manquer. .

Il est relativement facile de construire un tel problème: si les n / 2 premiers bits sont tous nuls, résoudre l'instance 3SAT codée avec les n / 2 derniers bits. Sinon, rejette. Au fur et à mesure que n s'agrandit, le problème a à peu près le même temps d'exécution dans le pire des cas que l'algorithme le plus efficace pour 3SAT, où le temps d'exécution moyen est garanti comme étant très faible.

Joe Fitzsimons
la source
J'ai déjà répondu à James King ci-dessus que je m'attends à ce que les réponses les plus intéressantes portent sur l'exécution attendue. Je vais modifier la question pour la rendre plus visible.
Radu GRIGore
9

Il est prouvé que l'inférence de type Damas-Milner est complète pour le temps exponentiel, et il existe des cas faciles à construire avec une explosion exponentielle de la taille d'un résultat. Néanmoins, sur la plupart des entrées du monde réel, il se comporte de manière réellement linéaire.

sclv
la source
Y a-t-il une référence que vous recommanderiez pour ce résultat? J'aimerais en savoir plus à ce sujet.
Radu GRIGore
1
Je ne l'ai pas lu moi-même, mais Harry G. Mairson est le document le plus fréquemment cité: "La décidabilité du typage ML est complète pour le temps exponentiel déterministe", 17ème Symposium sur les principes de langages de programmation (1990).
sclv
9

Le PTAS for Steiner tree dans les graphes planaires a une dépendance ridicule à epsilon. Cependant, une mise en œuvre montre une performance étonnamment bonne dans la pratique.

zotachidil
la source
8

Couplage de tas, depuis [1] - ils implémentent des tas, où insertion et fusion ont une complexité amortie de O (log n), mais sont supposés être O (1). En pratique, ils sont extrêmement efficaces, en particulier pour les utilisateurs de la fusion.

Je viens juste de les découvrir aujourd'hui en lisant Sec. 5.5 du livre de C. Okasaki "Des structures de données purement fonctionnelles", j'ai donc pensé partager des informations à leur sujet.

[1] Fredman, ML, Sedgewick, R., Sleator, DD et Tarjan, RE 1986. Le tas d'appariement: une nouvelle forme de tas auto-ajustable. Algorithmica 1, 1 (janvier 1986), 111-129. DOI = http://dx.doi.org/10.1007/BF01840439

Blaisorblade
la source
Il y a eu quelques progrès depuis Okasaki, et il existe maintenant (impératif) des tas de paires avec O (0) meld, O (1) insert et findMin, O (lg lg n) diminutionKey et O (lg n) deleteMin: arxiv. org / abs / 0903.4130 . Ce segment utilise un mécanisme d'appariement différent de celui des tas d'appariement de Fredman et al.
Jbapple
7

En rapport avec la remarque de Ilyaraz sur les branches et les liens, Pataki et al. montrer que la réduction de base de branche et liée plus réseau peut résoudre presque toutes les IP aléatoires en temps réel.

Marco
la source
6

L'heuristique de Lin-Kernighan pour le TSP ("Une heuristique efficace pour le problème du vendeur itinérant", Operations Research 21: 489-516, 1973) est très efficace dans la pratique, mais il lui manque encore une analyse moyenne ou lissée pour en expliquer les performances. . En revanche, Matthias Englert, Heiko Röglin et Berthold Vöcking (Algorithmica, à paraître) ont analysé de manière lissée l'heuristique à double opt pour le TSP.

Bodo Manthey
la source
5

Il y a beaucoup de très rapide et efficace dans la pratique branche et liée algorithmes pour différents problèmes NP-difficiles que nous ne pouvons pas analyser rigoureusement: TSP, arbre de Steiner, emballage bin et ainsi de suite.

En outre, il existe de très bons algorithmes pour max-flow qui sont pratiquement linéaires, mais seules les limites ont été prouvées.Ω(nm)

ilyaraz
la source
Vous voulez dire O (mn), ou suis-je confus?
Radu GRIGore
La meilleure limite jusqu'à présent est . O(nmlog(n2/m))
ilyaraz