Dans le cadre de ma thèse de lycée, je décris l'heuristique du problème du voyageur de commerce. je lisais ce sorte d'étude de cas (page 8) mais je ne peux pas comprendre ce que ces phrases signifient:
Le temps d'exécution pour NN comme décrit est (N ^ 2 ). [...] En particulier, nous avons la garantie que NN (I) / OPT (I) ≤ (0,5) (log_ {2} N + 1).
Cette partie est très claire pour moi. Mais alors:
Substantiellement une meilleure garantie est toutefois possible, car il existe des cas pour lesquels le rapport grandit comme (logN).
Que veut dire il y a des cas pour lesquels?
La même chose se passe avec l'algorithme glouton:
... mais le pire les exemples connus pour Greedy font seulement croître le rapport en tant que (logN) / (3 log log N).
Alors, quel est le sens de ces déclarations? Est-ce que cela a à voir avec des instances non-euclidiennes (je ne le pense pas, car il suffit de lire la colonne d'une matrice de distance pour la résoudre)? noeud de départ nécessitant l’algorithme pour scinder l’arbre de la solution ou quelque chose de similaire?
MODIFIER: Grâce à @templatetypedef (votre réponse sera toujours considérée comme correcte), tout est logique. Cependant, je voudrais demander si quelqu'un connaît un exemple (ou même juste un lien) de ces graphiques spécifiques (Peu importe l’algorithme utilisé.) Je ne pense pas que c’est trop hors sujet, mais plutôt d’ajouter quelque chose d’utile au sujet.
Réponses:
1 pour la réponse № 1Jetez un coup d'œil à ces deux affirmations côte à côte:
En particulier, nous avons la garantie que NN (I) / OPT (I) ≤ (0,5) (log_ {2} N + 1).
Aucune garantie substantiellement meilleure n'est toutefois possible, car il existe des cas pour lesquels le rapport augmente en tant que (logN).
Cette première déclaration dit que l'algorithme NN, dansdans le pire des cas, donne une réponse qui "s (environ) à moins de 1/2 lg N de la vraie réponse (pour le voir, il suffit de multiplier les deux côtés par OPT (I)). C’est une bonne nouvelle! La question de suivi naturelle est donc de savoir si la limite réelle est encore plus étroite que cela. Par exemple, ce résultat n’exclut pas la possibilité que nous ayons aussi NN (I) / OPT (I) ≤ log log N ou que NN (I) / OPT (I) ≤ 2. C’est une limite beaucoup plus étroite.
C’est là que la deuxième déclaration entre en jeu. Cette déclaration indique qu'il existe des exemples connus de TSP (c'est-à-dire de graphiques spécifiques pondérés) où le rapport NN (I) / OPT (I) est (log n) (c'est-à-dire que le rapport est proportionnel au log du nombre de nœuds dans le graphique). Comme nous connaissons déjà de telles entrées, il n’est pas possible que NN (I) / OPT (I) soit limité d’en haut par quelque chose comme log log n ou 2, car ces limites sont trop strictes.
Cependant, cette deuxième déclaration isolée estpas très utile. Nous savons qu’il existe des entrées qui feraient en sorte que l’algorithme produise quelque chose qui "décolle par un facteur de log, mais pourrait-il toujours être possible que des entrées l’entraînent pour être déséquilibré beaucoup plus, disons par un facteur exponentiel "Avec la première déclaration, nous savons que cela ne peut pas se produire, car nous savons que nous n’obtenons jamais plus qu’un facteur de log.
Pensez à ces énoncés en deux étapes: le premier énonce limite supérieure l’approximation peut être mauvaise - ce n’est jamais pire qu’un facteur optimal de 1/2 lg N + 1. borne inférieure l’approximation peut être mauvaise - il existe des cas spécifiques où l’algorithme ne peut «faire mieux que l’approximation log (log N) de la réponse optimale.
(Notez que le log (log n) ici n’a rien à voir avec le runtime - c’est juste une façon de dire "quelque chose de logarithmique".)
En allant de l'avant, gardez un œil sur les limites supérieure et inférieure. Les deux vous disent collectivement beaucoup plus que quiconque individuellement.
Bonne chance avec la thèse!