Como parte de mi tesis de escuela secundaria, describo las heurísticas para el problema del vendedor ambulante. estaba leyendo esta tipo de estudio de caso (página 8) pero no puedo entender lo que significan estas oraciones:
El tiempo de ejecución para NN como se describe es Θ (N ^ 2 ). [...] En particular, tenemos la garantía de que NN (I) / OPT (I) ≤ (0. 5) (log_ {2} N + 1).
Esa parte es muy clara para mí. Pero entonces:
No sustancialmente Sin embargo, es posible una mejor garantía, ya que hay casos en los que la relación crece como Θ (logN).
Cuál es el significado de hay instancias para las cuales?
Lo mismo sucede con el algoritmo codicioso:
... pero lo peor los ejemplos conocidos de Greedy solo hacen que la proporción crezca como (logN) / (3 log log N).
Entonces, ¿cuál es el significado de esas declaraciones? ¿Tiene que ver con instancias no euclidianas (no lo creo porque solo tiene que leer la columna de una matriz de distancias para resolverla)? O simplemente instancias con, por ejemplo, múltiples nodos a la misma distancia de la ¿El nodo inicial que requiere el algoritmo para dividir el árbol de soluciones o algo similar?
EDITAR: Gracias a @templatetypedef (su respuesta será aceptada como correcta), todo tiene sentido. Sin embargo, me gustaría preguntar si alguien conoce algún ejemplo (o incluso un enlace) de estos graficas especificas (No importa de qué algoritmo). No creo que sea demasiado fuera de tema, preferiría agregar algo útil al tema.
Respuestas
1 para la respuesta № 1Eche un vistazo a estas dos afirmaciones de lado a lado:
En particular, tenemos la garantía de que NN (I) / OPT (I) ≤ (0. 5) (log_ {2} N + 1).
Sin embargo, no es posible una garantía sustancialmente mejor, ya que hay casos en los que la proporción crece como Θ (logN).
Esta primera afirmación dice que el algoritmo NN, enen el peor de los casos, produce una respuesta que "s (aproximadamente) dentro de 1/2 lg N de la respuesta verdadera (para ver esto, simplemente multiplique ambos lados por OPT (I)). ¡Es una gran noticia! La pregunta de seguimiento natural, entonces, es si el límite real es incluso más estricto que eso. Por ejemplo, ese resultado no descarta la posibilidad de que también tengamos NN (I) / OPT (I) ≤ log log N o que NN (I) / OPT (I) ≤ 2. Esos son límites mucho más estrictos.
Ahí es donde entra la segunda declaración. Esta declaración dice que hay instancias conocidas de TSP (es decir, gráficos específicos con pesos en ellos) donde la relación NN (I) / OPT (I) es Θ (log n) (es decir, la proporción es proporcional al registro). del número de nodos en la gráfica). Debido a que ya sabemos acerca de entradas como esta, no es posible que NN (I) / OPT (I) esté limitado desde arriba por algo como log log n o 2, ya que esos límites son demasiado ajustados.
Sin embargo, esa segunda afirmación en aislamiento esNo es muy útil. Sabemos que hay entradas que podrían hacer que el algoritmo produzca algo que está desactivado por un factor logarítmico, pero podría ser posible que haya entradas que causen que esté desactivado por mucho más; por ejemplo, por un factor exponencial ? Con la primera afirmación, sabemos que esto no puede suceder, ya que sabemos que nunca obtenemos más que un factor logarítmico.
Piense en estas declaraciones en dos pasos: la primera declaración da una límite superior sobre qué tan mala puede ser la aproximación, nunca es peor que un factor óptimo de 1/2 lg N + 1. En la segunda afirmación se da una límite inferior sobre qué tan mala puede ser la aproximación: hay casos específicos en los que el algoritmo no puede hacer nada mejor que una aproximación de Θ (registro N) de la respuesta óptima.
(Tenga en cuenta que Θ (log n) aquí no tiene nada que ver con el tiempo de ejecución, es solo una forma de decir "algo logarítmico").
En el futuro, manténgase atento a los límites superiores e inferiores. Los dos colectivamente te dicen mucho más de lo que cualquiera hace individualmente.
¡Mucha suerte con la tesis!