Cálculo del número de rutas a través del gráfico

Question

Estoy buscando el número de x rutas de longitud únicas a través de un gráfico que comienza en un nodo particular.

Sin embargo, tengo la restricción de que no se visita ningún nodo más de una vez en ninguna ruta.

---

Por ejemplo tomar el siguiente gráfico:

Si soy después de que el número de 3 caminos de longitud a partir de 5.

la respuesta sería 9.

5 -> 2 -> 1 -> 3 
5 -> 2 -> 4 -> 3 
5 -> 2 -> 4 -> 7 
5 -> 4 -> 2 -> 1 
5 -> 4 -> 3 -> 1 
5 -> 4 -> 7 -> 6 
5 -> 6 -> 7 -> 4 
5 -> 7 -> 4 -> 2 
5 -> 7 -> 4 -> 3 

Nota: solo estoy de acuerdo con la respuesta (9) no las rutas específicas.

---

He intentado usar un adjacency matrix a la potencia de x para dar el número de caminos, pero no puedo encontrar la manera para tener en cuenta la restricción de nodo único.

También he intentado usar un depth-first search pero la cantidad de nodos y el tamaño de x lo hacen inviable.

---

EDIT: Confundido DFS con BFS (Gracias sonrisa de nylon & Nikita Rybak).

Answer 1

Esto es NP-Hard.

Reducción de Hamiltonian Path.

Dada una gráfica cuya existencia Camino hamiltoniano tenemos que comprobar ...

ejecutar su algoritmo para cada vértice, con una longitud de trayectoria n-1. Cualquier retorno distinto de cero corresponde a la ruta de Hamilton y viceversa.

Así que, básicamente, si encuentra un algoritmo de tiempo polinomial para resolver su problema, entonces tiene un algoritmo de tiempo polinomial para resolver el problema de la ruta de Hamilton, ¡demostrando efectivamente P = NP!

Nota: Esto supone que x es una entrada.

Si x se corrigió (es decir, independientemente del número de vértices en el gráfico), entonces tienes algoritmos de tiempo O (n^x), que están en P, pero aún son poco prácticos para x de tamaño medio.

Answer 2

Este problema es un problema de conteo en #P (número de soluciones) en lugar de un problema de decisión en NP (sí o no).

Moron's reduction sigue funcionando para demostrar que el problema es #P-Complete porque Hamilton Paths también es # P-complete.