Quel est l'algorithme le plus rapide qui existe pour résoudre un problème complet de NP-complet? Par exemple, une implémentation naïve de Vendeur de voyage est O (n!), Mais avec la programmation dynamique peut être fait dans O (n ^ 2 * 2 ^ N). Y a-t-il peut-être un problème NP-complet peut-être «plus facile» qui a une meilleure heure de fonctionnement?
Je suis curieux des solutions exactes, pas d'approximations.
3 Réponses :
Une caractéristique des problèmes de NP-Complets est que l'un des problèmes de NP peut être transformé mécaniquement dans l'un des problèmes de NP-complets dans, au plus, du temps polynomial.
Par conséquent, quelle que soit la meilleure solution pour tout problème NP-complet, il est automatiquement une solution similaire-bonne pour tout autre problème NP.
Étant donné que la programmation dynamique peut résoudre le problème du vendeur itinérant dans 2 ^ n Time et 2 ^ n Espace, il en va de même pour tous les autres problèmes de NP [Eh bien, plus le temps d'appliquer la transformation, je suppose - donc cela pourrait être 2 ^ (n + 1)].
Je pense que cela ne nécessite que O (n) espace
Je ne me suis pas souvenu hors de la main, alors je l'ai regardé sur Wikipedia. Pourrait être que j'ai mal interprété l'article ...
[...] avec une programmation dynamique, cela peut être fait en O (n ^ 2 * 2 ^ N). Y a-t-il peut-être un problème NP-complet peut-être «plus facile» qui a une meilleure heure de fonctionnement?
sorte de. Vous pouvez vous débarrasser de tout facteur polynomial en créant un problème artificiel qui code la même solution dans une entrée polynomenale plus grande. Tant que l'entrée n'est que polynomialement plus grande, le problème résultant est toujours NP-complet. Étant donné que la complexité est par définition, la fonction qui mesure la taille d'entrée à l'heure de fonctionnement, si la taille d'entrée augmente la fonction se situe dans des classes O inférieure.
Donc, le même algorithme exécutant sur TSP avec l'entrée rembourrée avec des bits inutiles N ^ 2, sera complexité O (1 * 2 ^ SQRT (N)).
Généralement, vous ne pouvez pas trouver la solution meilleure pour le problème de vendeur de voyage générique sans essayer toutes les combinaisons (il pourrait y avoir des distances négatives, etc.).
En ajoutant des restrictions supplémentaires et en relâchant la nécessité d'obtenir la solution meilleure , vous pouvez accélérer des choses un peu.
Par exemple, vous pouvez obtenir du temps exécutable polynomial si les distances du problème obéissent au "il ne vient plus d'aller directement de A à B que d'aller de A à C à B" (c'est-à-dire un raccourci n'est jamais plus long), < em> et vous pouvez vivre avec le résultat étant maximal de 1,5 fois la valeur optimale. Voir
0 commentaires
Je vais +1, je suis intéressé de voir ce que les autres voient.
Votre question pose votre question "Quel est l'algorithme le plus rapide que nous avons proposé?" Et ensuite "Notez que je ne suis pas intéressé par des approximations, mais des solutions exactes." Comment pouvons-nous connaître l'algorithme exact le plus rapide que vous propose-t-il?
Avez-vous essayé mathoverflow.net ?
@Ricknz: par 'Nous "je voulais dire" humanité en général ". Je n'essaie pas de vous avoir gars battre mon algorithme, je veux juste savoir ce que le plus rapide est celui qui existe.
Mathoverflow version: Mathoverflow.net/Questtions/6418/...
Je ne suis pas tout à fait sûr, mais n'est-il pas (2 ^ n * n ^ 2) == O (2 ^ N)?