Esta es una excelente pregunta. No tengo una explicación completamente satisfactoria, pero déjame darte un comienzo.
En primer lugar, es importante comprender que no podemos resolver este problema simplemente enumerando todos los ciclos y verificando el peso de cada uno. Por qué no? Porque puede haber (y a menudo hay) exponencialmente muchos ciclos. Por lo tanto, simplemente enumerarlos necesariamente tomará tiempo exponencial, demasiado tiempo para ser factible.
Entonces, ¿cómo funciona Bellman-Ford? Funciona con algún truco inteligente que evita la necesidad de examinar individualmente cada ciclo uno por uno. En cambio, crea un resumen que resume algo sobre el efecto de todos los caminos y ciclos de longitud hasta . Efectivamente, para cada vértice , resume todas las rutas que comienzan en , terminan en y toman como máximo pasos. Como cada ciclo debe contener una ruta de esta forma, el resumen de alguna manera encapsula el efecto de todos los ciclos posibles.nvvvn
¿Por qué no podemos usar esto para detectar (por ejemplo) si existe un ciclo de peso ? Es porque el resumen de Bellman-Ford incluye caminos que recorren el ciclo varias veces. Si el ciclo es de longitud , entonces incluirá rutas de longitud , es decir, rutas que recorren el ciclo aproximadamente veces. Por ejemplo, si tiene un ciclo de longitud , entonces el resumen incluye una ruta que recorre el ciclo tres veces.≥1knn/kn/3
¿Cuál es el efecto de caminar alrededor de un ciclo varias veces? Si desea distinguir los ciclos de peso positivo de los ciclos cuyo peso no es positivo, caminar por un ciclo varias veces no hace daño. Si el ciclo tiene un peso positivo, puede caminar varias veces y el peso total seguirá siendo positivo. Si el peso del ciclo no es positivo, puede caminar varias veces y el peso total seguirá siendo no positivo. Entonces, si lo único que nos importa es la diferencia entre el peso positivo y el no positivo, caminar por el ciclo varias veces no hace daño.
Pero ahora considere cómo cambian las cosas si lo que nos importa es la diferencia entre "peso " versus "peso ". Si tenemos un ciclo cuyo peso es y lo recorremos varias veces, el peso total podría convertirse en . Por ejemplo, si el peso del ciclo es y caminamos alrededor del ciclo tres veces, entonces el peso total de ese camino es , que es : comenzamos con un ciclo de peso y terminamos con una trayectoria de peso . Este hecho arruina totalmente a Bellman-Ford y lo hace inútil para verificar si existe un ciclo de peso≥1<1<1≥11/21.5≥1<1≥1.5≥1. (¿Ves la diferencia?)
Me doy cuenta de que esta no es una respuesta 100% satisfactoria. Te dice por qué Bellman-Ford no va a funcionar para resolver tu problema. Sin embargo, no le da ninguna intuición para explicar por qué esto es difícil en general (por ejemplo, por qué es difícil encontrar algún otro algoritmo para resolverlo). No tengo una buena intuición para eso, tal vez alguien más tenga una mejor explicación para ti. Mientras tanto, tal vez esto le permita comenzar a entender por qué este problema es difícil.
Consideremos las versiones más simples de estos problemas donde los bordes no están ponderados.
Dado un gráficoG , comprobar si sol Tiene un ciclo.
Dado un gráficosol y un numero k , comprobar si sol tiene un ciclo de longitud al menos k .
El primero es fácil y se puede resolver con DFS. El segundo es NP-hard.
Veamos un problema aún más simple:
Dado un gráficosol y dos vértices s y t , verifique si hay una ruta simple desde s a t en sol .
Dado un gráficosol y dos vértices s y t y un numero k , verifique si hay una ruta simple desde s a t en sol de longitud al menos k .
Todos estos problemas son del mismo sabor. El superior es fácil, mientras que el inferior es NP-duro. Explicaré la diferencia para el último porque es más simple pero la misma explicación se aplica a los otros pares.
La razón por la cual las superiores son fáciles mientras que las inferiores no lo son es el resultado de la estructura de las respuestas a estos problemas.
Primero veamos el problema de encontrar un camino simple e intentemos resolverlo recursivamente. Si solo intentamos resolver este problema directamente, necesitaríamos hacer un seguimiento de los vértices que hemos usado hasta ahora:
Si intentamos resolver el problema con este ingenuo algoritmo recursivo, llevará tiempo exponencial: ¡ existen exponencialmente muchas posibilidades para el conjunto de vértices no utilizados! Tenemos que ser más inteligentes.
¿Por qué obtuvimos exponencialmente muchas posibilidades? Debido a que estábamos tratando de encontrar un camino simple y hacer cumplir esta condición, necesitábamos hacer un seguimiento de los vértices no utilizados.
Bien, dejemos esa condición y veamos dónde podemos obtener:
Considere el problema de encontrar un camino (no necesariamente simple) des a t . Dado que el camino no necesita ser simple, no necesitamos hacer un seguimiento de los vértices no utilizados. En otras palabras, el gráfico no cambia con el tiempo.
Pero aún no hemos terminado. El problema es que no sabemos siPathG(s,u)
es un problema menor que PathG(s,t) . Entonces, esta solución recursiva podría terminar en un bucle y nunca terminar.
Para evitar esto, podemos agregar un parámetro adicional que asegure que el problema se reduzca: el número de bordes en la ruta.
Ahora tenga en cuenta que hay un camino simple desdes a t si hay un camino desde s a t con a lo sumo n bordes En otras palabras:
Los puntos esenciales aquí son:
Cada camino simple (no trivial) desdes a t
consiste en un camino simple desde s a algún vértice u y una ventaja ut .
Podemos suponer quet no aparece en la ruta simple desde s a u .
No necesitamos mantener explícitamente la lista de vértices no utilizados.
Estas propiedades nos permiten tener una recursión inteligente por la existencia de un problema de ruta simple.
Ahora, esto no se aplica al problema de encontrar una ruta de longitud al menosk . No sabemos cómo reducir el problema de encontrar una ruta simple de longitud al menosk
a un subproblema más pequeño sin mantener la lista de vértices no utilizados. Esas propiedades nos permiten resolver la existencia del problema del camino de manera eficiente.
Cuando un gráfico no tiene un ciclo negativo, nos permiten resolver la existencia de una ruta de longitud como máximok problema y la ruta más corta problemas simples de manera eficiente.
Sin embargo, no sostienen la existencia de un camino de longitud al menosk . Considere una gráfica con3 vértices s,u,t .
w(su)=1000,w(st)=1000,w(ut)=10,w(tu)=10 . El camino de longitud al menos1001 desde s a t contiene u y el camino de longitud al menos 1001 desde s a u contiene t . Por lo tanto, no podemos reducir una instancia del problema a una instancia más pequeña del problema sin dar explícitamente la lista de vértices no utilizados.
En otras palabras, no conocemos una recursión inteligente para la existencia de un camino simple de longitud al menosk problema mientras conocemos una recursión inteligente para la existencia de un camino simple.
Volviendo a la última parte de su pregunta, hay un problema con su argumento.
De hecho, es cierto que la existencia de un ciclo de longitud>k
se puede resolver en tiempo polinómico para cualquier fijo k (es decir k no es parte de la entrada). (Similar a cómo se puede verificar si un gráfico no ponderado tiene un ciclo de longitudk
a tiempo O(nk) .)
sin embargo cuandok es parte de la entrada, esto ya no se mantiene ya que el tiempo de ejecución depende de k mal.
fuente