Problème d'ensemble indépendant du poids maximum pour un cycle (modification du graphe de trajectoire)

Question

Problème: Un graphe G = (V, E) avec des poids non négatifs sur les sommets. Sortie souhaitée: Un ensemble indépendant de sommets (non adjacents) de poids total maximum dans un cycle C avec n sommets v1. . . vn (pour chaque i <n, vi est connecté à vi + 1, vn est connecté à v1 et ce sont les seules arêtes de C).

Ce problème est une modification de ce problème: problème d'ensemble indépendant du poids maximum pour un graphe de chemin

Je sais que pour le problème d'origine avec le graphique de chemin qui ne contient pas de cycle, la solution est

a[i] = max(a[i - 1], a[i - 2] + w[i])

Cela est dû au fait que le SI peut être soit celui qui contient vn, soit celui qui ne contient pas, et que le temps d'exécution est O (n) dans le pire des cas, car chaque sous-problème ne prend qu'une partie de n et la réduit car il est diviser pour conquérir.

Pour la modification du cycle, voici mon approche:

1. le SI contient v1 mais pas vn,
2. le SI contient vn mais pas v1,
3. le SI ne contient ni v1 ni vn.

Je ne sais pas si l'équation sera la même que le graphique de chemin (illustré ci-dessus) pour la modification du cycle et je ne sais pas comment l'écrire, et je ne suis pas sûr si le temps d'exécution serait toujours le même que bien. Veuillez aider.

Answer 1

Nous n'avons pas besoin que les cas ne se chevauchent pas. Si nous trouvons le maximum de solutions qui excluent v1 et le maximum de solutions qui excluent vn, alors le maximum global doit correspondre à l'une de ces deux solutions candidates, car aucune solution n'inclut à la fois v1 et vn. Pour ces sous-problèmes, le chemin DP fonctionne très bien.