Calcolo del numero di percorsi attraverso il grafico

Question

Sto cercando il numero di percorsi unici x attraverso un grafico che inizia da un nodo particolare.

Tuttavia, ho una restrizione che nessun nodo è visitato più di una volta su qualsiasi percorso.

---

consideri ad esempio il seguente grafico:

Se sono dopo il numero di 3 percorsi lunghezza partendo 5.

la risposta sarebbe 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 Sono solo concertato con la risposta (9) non i percorsi specifici.

---

Ho provato utilizzando un adjacency matrix alla potenza di x invia il numero di percorsi, ma non riesco a capire come contabilizzare unica limitazione nodo.

Ho anche provato a utilizzare un depth-first search ma la quantità di nodi e dimensioni di x rende questo non fattibile.

---

EDIT: Confuso DFS con BFS (Grazie Nylon Sorriso & Nikita Rybak).

Answer 1

Questo è NP-Hard.

Riduzione dal percorso hamiltoniano.

Dato un grafo i cui Hamiltoniana Percorso esistenza abbiamo bisogno di controllare ...

eseguire il vostro algoritmo per ogni vertice, con una lunghezza del percorso n-1. Qualsiasi ritorno diverso da zero corrisponde al percorso hamiltoniano e viceversa.

Quindi, in sostanza, se si trova un algoritmo del tempo polinomiale per risolvere il problema, si dispone di un algoritmo del tempo polinomiale per risolvere il problema del percorso hamiltoniano, dimostrando in modo efficace P = NP!

Nota: ciò presuppone che x sia un input.

Se x è stato corretto (cioè indipendentemente dal numero di vertici nel grafico), allora hai algoritmi di tempo O (n^x), che è in P, ma ancora piuttosto poco pratico per le medie dimensioni x.

Answer 2

Questo problema è un problema di conteggio in #P (numero di soluzioni) anziché un problema di decisione in NP (sì o no).

Moron's reduction funziona ancora per dimostrare il problema è #P-Complete perché Hamilton Paths è anche # P-completo.