Generación de todas las rutas de un grafo acíclico dirigido

Question

Estoy trabajando en un conjunto de datos muy grande de un solo DAG cuyos vértices tienen un factor de ramificación bajo. Necesito generar todas las trayectorias (simples) posibles partiendo del origen y escribirlas en un fichero.

Mi pregunta es: ¿qué es complejidad computacional clase de este problema?

Si este problema NP-Hard ¿existe algún algoritmo relativamente eficiente en términos de espacio que pueda generar iterativamente este número exponencial de caminos?

Cualquier referencia será muy apreciada.

Gracias de antemano.

Answer 1

El peor caso es exponencial en el número de nodos. Consideremos un Diagrama de decisión binario ordenado (OBDD) que es un DAG con outdegrees 2. Sea en $n$ variables booleanas y en $m$ nodos. Cada asignación de las variables corresponde a un camino hacia Verdadero o Falso, por lo que hay al menos $2^n$ caminos (simples). Incluso si la salida de una ruta es $O(1)$ tendrás que hacerlo $2^n$ veces (sin contar las rutas internas).

Para comprobar si tiene suerte, puede contar eficazmente el número de caminos mediante potencias del matriz de adyacencia .

El software libre salvia (disponible en línea en http://sagenb.org/ ) tiene un método "all_simple_paths()" que hace exactamente lo que quieres.