Existe-t-il un autre algorithme dont le temps d'exécution le plus défavorable est exponentiel, alors qu'il fonctionne très bien en pratique autre que l'algorithme Simplex?

9

Nous appelons généralement un algorithme «bon algorithme» si son temps d'exécution est polynomial dans le pire des cas. Mais dans certains cas (par exemple l'algorithme Simplex), même si le pire des cas de l'algorithme est exponentiel, cela pourrait très bien fonctionner dans la pratique.

Existe-t-il des exemples (déterministes) de cette situation autres que l'algorithme Simplex?

ds.algorithms Arman
la source
1
Vous pouvez être intéressé par une question connexe: cstheory.stackexchange.com/questions/305/…
Radu GRIGore

Réponses:

13

Les algorithmes de résolution SAT modernes sont capables de résoudre la plupart des instances assez rapidement, même si le pire temps d'exécution est, bien sûr, exponentiel. Dans ce cas, cependant, la vitesse pratique est davantage le résultat d'années d'ingénierie algorithmique que celle d'un seul algorithme élégant. Bien que j'aie compris que l'apprentissage des clauses axées sur les conflits a provoqué un saut majeur dans les performances des solveurs SAT, les améliorations ultérieures ont souvent été obtenues par une utilisation intelligente de diverses heuristiques dans les algorithmes.

Janne H. Korhonen
la source
13

L' algorithme moyens pour le clustering est prouvablement exponentiel même dans le plan, mais il fonctionne très bien en pratique.k

Suresh Venkat
la source
13

L'inférence de type Hindley-Milner est complète en EXPTIME, mais sur les programmes que les gens écrivent, elle est assez proche du linéaire.

Neel Krishnaswami
la source
1
N'est-ce pas un peu différent cependant? Si je me souviens bien, nous pourrions caractériser une condition nécessaire pour que Hindley-Milner se comporte mal (laisse profondément imbriquée) et donc la raison pour laquelle HM est bon en pratique est que cette imbrication est, en pratique, limitée assez bas (en général, nous tirons plus en retrait au fur et à mesure) plus profondément dans les fixations let et devenir nerveux alors que nous nous dirigeons vers le bord le plus à droite de l'écran ...) Certes, j'ai fait cette affirmation de mémoire auparavant et je n'ai pas été en mesure récemment de récupérer la référence pour cela.
Rob Simmons
2
Non, ce n'est pas une condition nécessaire. Vous pouvez donner une séquence de let-bindings (sans imbrication!) De sorte qu'elle ajuste la taille du type déduit à chaque entrée supplémentaire dans la séquence. Voir cstheory.stackexchange.com/questions/2428/… pour un exemple.
Neel Krishnaswami
L'exemple est en SML, et je connais mieux la façon de faire d'OCaml, mais si cette séquence de liaisons était "louée", alors je pense qu'elles seraient imbriquées. C'est seulement parce qu'ils définissent des fonctions globales qu'ils ne le sont pas, mais il y a une imbrication implicite en cours ici: Une définition donnée a accès à toutes les définitions au-dessus d'elle et à aucune de celles ci-dessous.
2016
1
@amnn: l'imbrication à laquelle il était fait référence était l'imbrication de la forme étant liée - c'est-à-dire, let z = (let y = e in e') in e''par opposition à que let y = e in let z = e' in e''.
Neel Krishnaswami
9

Le programme nauty (No AUTomorphisms, Yes?) De Brendan McKay résout le problème d'étiquetage canonique des graphiques (résolvant simultanément les problèmes d'isomorphisme graphique et d'automorphisme graphique) et a des performances exponentielles dans le pire des cas (Miyazaki, 1996). Cependant, cela fonctionne très rapidement pour la plupart des graphiques, en particulier ceux avec quelques automorphismes.

Plus précisément, l'algorithme commence par partitionner les sommets par degré, puis par degré entre chaque partie. Lorsque ce processus se stabilise, un choix doit être fait pour distinguer un sommet dans une partie non triviale, ce qui conduit au comportement exponentiel. Dans la plupart des graphiques, la profondeur de cette procédure de branchement est faible.

Derrick Stolee
la source
Je pensais que nauty utilisait également un peu de hasard pour aider au raffinement? Dans ce cas, cela pourrait être très analogue à l'algorithme du simplexe (bien qu'il n'y ait évidemment pas de notion d'analyse lissée pour l'isomorphisme des graphes).
Joshua Grochow
1
Il n'utilise pas le caractère aléatoire, car il doit créer un étiquetage canonique cohérent. Cependant, il peut utiliser une procédure invariante de vertex personnalisée pour aider à partitionner les sommets. Parfois, cet invariant semble aléatoire comment il a été produit (souvent, c'est une fonction compliquée sur les séquences distance-degré), mais c'est juste pour réduire les collisions.
Derrick Stolee
1
Cet invariant de vertex peut être comparé aux règles anti-cycliques de l'algorithme simplex.
Derrick Stolee
4

Plusieurs algorithmes pour les jeux stochastiques simples fonctionnent bien dans la pratique, même s'ils ont des temps d'exécution exponentiels dans le pire des cas. Bien sûr, ce problème est en quelque sorte lié à la programmation linéaire, bien qu'il ne soit pas connu qu'il soit en temps polynomial.

Peter Shor
la source
1

Il existe un algorithme pour trouver des équilibres Nash mixtes qui est similaire à l'algorithme simplex pour les LP. (J'oublie le nom.) Il a une complexité exponentielle dans le pire des cas, mais j'ai un vague souvenir qu'il se comporte souvent bien dans la pratique.

Warren Schudy
la source
Voulez-vous dire l'algorithme de Lemke-Howson?
Rahul Savani
1

L'emballage des bacs (de nombreuses variantes) est un problème dont la complexité est connue pour être NP-difficile:

http://en.wikipedia.org/wiki/Bin_packing_problem

Cependant, de nombreuses heuristiques appliquées à des versions "pratiques" fonctionnent très bien. Pour l'emballage bin à 1 dimension, certaines de ces heuristiques, comme le premier ajustement; premier ajustement décroissant; meilleur ajustement; le meilleur ajustement décroissant est très intéressant comme sujet à montrer aux élèves. Les élèves peuvent souvent découvrir par eux-mêmes certaines des heuristiques de base.

Joseph Malkevitch
la source
Il existe de nombreux exemples même si le problème est NP-complet, des algorithmes simples peuvent y faire face, en particulier avec des algorithmes d'approximation. Mais je recherche en fait des algorithmes à temps exponentiel, votre exemple est lié à un problème difficile qui est facile à résoudre avec des algorithmes simples. Peut-être existe-t-il un algorithme de temps exponentiel pour résoudre exactement le casier Bin (ou un autre problème); et en pratique, cela prend du temps polynomial.
Arman
0

L'algorithme de persistance (originaire d'Edelsbrunner-Letscher-Zomorodian, avec de nombreuses variations depuis) ​​est le pire des cas cubique, mais semble d'expérimentation pour s'exécuter généralement en temps linéaire.


la source