Problema del viajante: una peor

Question

Para aquellos no familiarizados con el problema, aquí está el artículo de Wiki; puede ser entendida por cualquier persona. Yo en particular interesado en el algoritmo del vecino más cercano, también conocido como el algoritmo voraz, que esencialmente dice: "escoger el más cercano de los no visitados de la ciudad".

En Wikipedia se afirma que existen ejemplos en los que esta es la peor estrategia posible, y esto es lo que soy después, ya que la idea parece algo contradictorio. He visitado a los que se hace referencia en el artículo , pero está muy por encima de mi cabeza. Mis preguntas son:

• ¿Cuál es el más pequeño ejemplo de este tipo de construcción? (sólo necesita ser la peor estrategia dada de partida de la ciudad, si que estrecha las cosas)
• Si el citado ejemplo no es demasiado complejo, alguien puede proporcionar una construcción explícita de uno?

Answer 1

El artículo que enlaza a los acuerdos con el asimétrica el problema del viajante. Los autores tienen un papel posteriores, que trata con el más habitual simétrica TSP: Gutin y Yeo, "El Algoritmo Voraz para el TSP Simétrico" (2007). Una construcción explícita de un gráfico en el que "el algoritmo voraz produce la única peor tour", que se da en la prueba del Teorema 2.2. El más pequeño trivial caso es $n=4$, por lo que el borde de gastos son los siguientes: $$\begin{array}{cccc} c(AB)=200, && c(AC)=201, && c(AD)=400, \\ && c(BC)=200, && c(BD)=201, \\ && && c(CD)=300. \end{array}$$ (Hay un parámetro de $M>n$ en su construcción, que me he puesto a $M=100$ para mayor claridad.)

El algoritmo voraz a partir de $A$ los rendimientos de la tour $ABCDA$ cuyo costo $c(ABCDA)=200+200+300+400=1100$ es peor que la de los dos otros tours, $c(ABDCA)=902$$c(ACBDA)=1002$.