Un gráfico bidireccional puede ser cualquier gráfico complejo arbitrario. Pero el problema de encontrar la ruta más larga en gráficos arbitrarios es NP-completo, es decir, la ruta más larga no se puede resolver en tiempo polinómico.
Por otro lado, la búsqueda de amplitud primero (BFS) tiene una complejidad lineal de tiempo de ejecución. Por lo tanto, no puede resolver la ruta más larga utilizando una sola instancia de BFS.
Sin embargo, puede usar BFS para recorrer todo el espacio de búsqueda, es decir, todas las rutas posibles .
- Cómo aprender a escribir buenos algoritmos
- ¿Existen algoritmos en R que permitan clasificar una variable binaria basada en un conjunto de cadenas (texto)?
- ¿Cuáles son las características de un algoritmo codicioso?
- Cómo reducir la programación dinámica a programación lineal
- ¿Alguien está usando algoritmos epigenéticos?
Algoritmo:
Desde el nodo inicial, atraviesa todos los nodos vecinos, que atraviesan a sus vecinos, que atraviesan a sus vecinos … hasta que haya construido todas las rutas posibles con longitud [math] | V | [/ math] para el gráfico [math] G = ( V, E). [/ Math] Ahora simplemente evalúa su función de costo en todas las rutas y devuelve la que tiene los costos máximos.
Como este algoritmo tiene que almacenar todas las rutas en la memoria, no es factible para ningún gráfico con más de, digamos, unas pocas docenas de vértices. El algoritmo sería más eficiente en el espacio cuando se utiliza la búsqueda de profundidad primero: revise esta publicación.
