Come trovare un ciclo che contiene un insieme di nodi in un grafico?

Question

Dato un grafo orientato G = (V, E) e un insieme di nodi P. I necessità di trovare un ciclo (non il ciclo più breve lunghezza) contenente questi nodi? Come faccio a trovare questo ciclo?

Answer 1

Contiene Hamiltonian ciclo (per P = V), da qui il problema decisionale (solo sapere se c'è una cosa del genere) è NP-completo. Quindi non c'è nessun algoritmo efficiente a meno che P = NP.

Answer 2

I probabilmente iniziare a progettare l'algoritmo scegliendo il primo nodo P (chiamiamolo P [0]), poi eseguire una ricerca in profondità da P [0], prendendo atto del momento P [0] è di nuovo raggiunto. Si dovrà memorizzare il percorso intrapreso per ri-portata P [0] (o almeno se gli altri nodi di P sono stati raggiunti) in modo da sapere che ogni ciclo di trovare contiene tutti i nodi in P. Tempo di esecuzione dovrebbe essere lo stesso che per ricerca in profondità, che credo sia O (V + E).

Qualcuno potrebbe trovare una soluzione migliore, e alcune euristiche potrebbe essere applicata per aiutare, ma che dovrebbe iniziare. (Ad esempio, si può concludere si dovrebbe iniziare al nodo P con i bordi minor numero invece di iniziare a P [0].)

Modifica

Ancora una cosa che ho pensato ... Quando si raggiunge un altro nodo P tramite la ricerca in profondità, non è necessario per il DFS mai per "ricominciare", fin dall'inizio o da considerare percorsi che non lo fanno includere questo nodo ritrovata. Questa struttura potrebbe aiutare il vostro algoritmo terminare più rapidamente nel caso in cui non esista tale ciclo.

Ulteriori edit:

Non importa l'ultima modifica - sarebbe solo lavoro se può essere accertato che non v'è alcun nodo P su un percorso diverso tra P [0] e il nodo in P raggiunto che non può essere raggiunto in un altro modo, e noi non saprebbe per certo senza fare tutto il DFS.

Per quanto riguarda la risposta su cicli Hamiltoniani, io non so come la rilevazione ciclo nel problema in questione è NP-completo. Sì, dovremmo attraversare l'intero grafico (tutti i vertici e bordi) raggiungibili dal punto di partenza per determinare se un ciclo che soddisfano i criteri del problema in esiste. Inoltre, avremmo bisogno di sapere su di entrare in contatto con un vertice in precedenza visitato ciò che il "percorso in avanti" del vertice sarebbe quello di determinare se v'è un ciclo di soddisfare i criteri. Dal momento che non si preoccupano più breve tale ciclo, però, non sono sicuro di come stiamo necessariamente lavorando per trovare un ciclo hamiltoniano. Cura per illuminare?