En la versión estándar de TSP (problema de vendedor ambulante), el vendedor no puede volver a visitar ninguna ciudad visitada anteriormente. Sin embargo, el problema sigue siendo NP completo si eliminamos esta restricción, permitiendo que el vendedor visite cada ciudad varias veces y simplemente solicite la ruta de menor costo que visite cada ciudad al menos (en lugar de exactamente ) una vez.
Esto se puede ver mediante una reducción del tiempo múltiple del problema de la ruta de Hamilton, que le pide que encuentre una ruta a través de un gráfico no dirigido que visite cada vértice exactamente una vez. Si le damos a cada peso de borde 1 y luego ejecutamos un algoritmo que resuelve el problema de TSP modificado, el gráfico tiene una ruta hamiltoniana si y solo si el solucionador de TSP modificado genera una ruta de costo total n-1, donde n es el número de vértices en el gráfico.
Es decir, incluso si al vendedor se le permite volver a visitar ciudades ya visitadas, en gráficos no ponderados, la ruta de menor costo será necesariamente una que nunca vuelva a visitar una ciudad, siempre que dicha ruta exista. Por lo tanto, cualquier algoritmo que afirme dar la ruta óptima tendría la capacidad de encontrar rutas hamiltonianas en los gráficos donde existen, un problema que ya se sabe que es NP completo.
- ¿La membresía a https://www.interaction-design.org es una buena inversión?
- Si tenemos un conjunto muy grande de objetos comparables, ¿qué implementación de la tabla de símbolos es empíricamente más rápida: una tabla hash o un árbol de búsqueda binario balanceado? ¿Por qué?
- ¿Por qué se sigue utilizando el modo de cifrado CBC en lugar del modo CTR aunque el modo CBC ha demostrado ser vulnerable (por ejemplo, ataque de caniche)?
- ¿Cómo funcionan las actuales interfaces cerebro-computadora?
- Cómo hacer que el envío directo sea automatizado
