Ruta simple más larga

Question

Entiendo que el problema de encontrar la ruta simple más larga en un gráfico es NP-hard, ya que entonces podría resolver fácilmente el problema del circuito de Hamilton estableciendo ponderaciones de borde a 1 y ver si la longitud de la el camino simple es igual al número de bordes.

Mi pregunta es: ¿Qué tipo de ruta recibiría si usted tomó un gráfico, que se encuentra al borde peso máximo, m, reemplazado cada peso de borde w con m - w, y corrió un algoritmo de ruta más corta de serie en eso? Claramente no es el camino simple más largo, ya que si lo fuera, entonces NP = P, y creo que la prueba de algo así sería un poco más complicado = P.

Answer 1

alt text http://dl.getdropbox.com/u/317805/path2.jpg

La gráfica anterior se transforma a continuación, utilizando su algoritmo.

La ruta más larga es la línea roja en el gráfico anterior. Y dependiendo de cómo se rompen los vínculos y el algoritmo que utiliza, la ruta más corta en el gráfico transformado podría ser la línea azul o la línea roja. Así que transformar los pesos del borde del gráfico usando la constante que mencionaste no produce resultados significativos. Esta es la razón por la que no puede encontrar la ruta más larga utilizando los algoritmos de ruta más cortos, sin importar cuán inteligente sea. Una transformación más simple podría ser negar todos los pesos de borde y ejecutar el algoritmo. No sé si he respondido tu pregunta, pero en lo que respecta a la propiedad del camino, el gráfico transformado no tiene información útil sobre la distancia.

Sin embargo, esta transformación particular es útil en otras áreas. Por ejemplo, podría forzar al algoritmo a seleccionar un peso de borde particular en el emparejamiento bipatrite si tiene más de una restricción agregando una constante enorme.

• Editar: He estado diciendo que agregue esta afirmación: El gráfico de arriba no es solo acerca de la distancia física. No necesitan mantener la desigualdad del triángulo. Gracias.

Answer 2

Si se pudiera resolver problema del camino más corto con pesos negativos que se encontraría un camino más largo, los dos son equivalentes, esto podría hacerse poniendo un peso de w en lugar de w

El algoritmo estándar de pesos negativos es el algoritmo Bellman-Ford. Sin embargo, el algoritmo no funcionará si hay un ciclo en el gráfico de manera que la suma de los bordes sea negativa. En el gráfico que creas, todos esos ciclos tienen pesos de suma negativos y, por lo tanto, el algoritmo no funcionará. A menos que, por supuesto, no tenga ciclos, en cuyo caso tiene un árbol (o un bosque) y el problema se puede resolver a través de la programación dinámica.

Si reemplazamos un peso de w por m-w, lo que garantiza que todos los pesos serán positivos, entonces la ruta más corta se puede encontrar mediante algoritmos estándar. Si la ruta más corta P en este gráfico tiene k bordes, entonces la longitud es k * m-w (P) donde w (P) es la longitud de la ruta con los pesos originales. Este camino no es necesariamente el más largo, sin embargo, de todos los caminos con k bordes, P es el más largo.