Comment trouver un cycle contenant un ensemble de noeuds dans un graphe?

Question

Etant donné un graphe non orienté G = (V, E) et un ensemble de noeuds P. Je dois trouver un cycle (pas le cycle de longueur la plus courte) contenant ces nœuds? Comment puis-je trouver ce cycle?

Answer 1

Contient hamiltonien Cycle (P = V), d'où le problème de décision (juste savoir s'il y a chose telle) est NP-complet. Donc, il n'y a pas d'algorithme efficace à moins que P = NP.

Answer 2

Je probablement commencer à concevoir l'algorithme en choisissant le premier noeud P (Appelons-le P [0]), puis en exécutant une recherche en profondeur d'abord de P [0], prenant note de tout temps P [0] est à nouveau atteint. Vous devez stocker le chemin prendre pour rétablir la portée P [0] (ou au moins si les autres nœuds de P ont été atteints) afin que vous sachiez que tout cycle, vous trouverez contient tous les noeuds P. temps de fonctionnement devrait être les mêmes que pour la recherche en profondeur d'abord, que je crois est O (V E +).

Quelqu'un peut trouver une meilleure solution, et certains heuristiques pourrait être appliquée à l'aide, mais que vous devriez commencer. (Par exemple, vous pouvez vous devriez commencer à conclure au niveau du noeud de P avec le plus petit nombre de bords au lieu à partir de P [0].)

Modifier

une chose que je pensais ... Lorsque vous atteignez un autre nœud P via votre recherche en profondeur d'abord, il n'y a pas besoin de DFS jamais « recommencer » dès le début, ou à considérer les chemins qui ne sont pas inclure ce nœud nouvellement trouvé. Cette propriété pourrait aider votre algorithme mettre fin plus rapidement dans le cas où un tel cycle de existe.

De plus modifier:

Peu importe la dernière édition - il ne fonctionnera que si on peut constater qu'il n'y a pas de noeud dans P sur un chemin différent entre P [0] et le noeud P atteint qui ne peut être atteint d'une autre manière, et nous ne connaîtrait pas sûr sans faire tout le DFS.

En ce qui concerne la réponse sur les cycles hamiltoniens, je ne sais pas comment la détection du cycle dans le problème à portée de main est NP-complet. Oui, il nous faudrait traverser le graphe entier (tous les sommets et arêtes) accessibles à partir du point de départ afin de déterminer si un cycle répondant aux critères du problème existe main. De plus, nous aurions besoin de savoir sur entrer en contact avec un sommet déjà visité ce que le « chemin avant » du sommet serait de déterminer s'il y a un cycle répondant aux critères. Puisque nous ne se soucient pas les plus brefs ce cycle, cependant, je ne sais comment nous nécessairement essayons de trouver un cycle hamiltonien. Prendre soin d'éclairer?