Problem ze zbiorami niezależnymi od maksymalnej wagi dla cyklu (modyfikacja wykresu ścieżki)
Problem: Wykres G = (V, E) z nieujemnymi wagami na wierzchołkach. Pożądany wynik: Niezależny zestaw wierzchołków (niesąsiadujących) o maksymalnej całkowitej wadze w cyklu C z n wierzchołkami v1. . . vn (dla każdego i <n, vi jest połączone z vi + 1, vn jest połączone z v1 i są to jedyne krawędzie w C).
Ten problem jest modyfikacją tego problemu: Problem ze zbiorami niezależnymi od maksymalnej wagi dla wykresu ścieżki
Wiem, że w przypadku pierwotnego problemu z wykresem ścieżki, który nie zawiera cyklu, rozwiązaniem jest
a[i] = max(a[i - 1], a[i - 2] + w[i])
Dzieje się tak, ponieważ IS może być taki, który zawiera vn lub taki, który go nie zawiera, a czas wykonywania wynosi O (n) w najgorszym przypadku, ponieważ każdy podproblem pobiera tylko część n i redukuje go, ponieważ jest podzielony i pokonany.
Oto moje podejście do modyfikacji cyklu:
- IS zawiera v1, ale nie vn,
- IS zawiera vn, ale nie v1,
- IS nie zawiera wersji v1 ani vn.
Nie jestem pewien, czy równanie będzie takie samo jak wykres ścieżki (pokazany powyżej) dla modyfikacji cyklu i nie jestem pewien, jak to napisać, i nie jestem pewien, czy czas działania byłby nadal taki sam jak dobrze. Proszę pomóż.
Odpowiedzi
Nie potrzebujemy, aby przypadki się pokrywały. Jeśli znajdziemy maksimum rozwiązań, które wykluczają v1, i maksimum rozwiązań, które wykluczają vn, to całkowite maks musi zostać dopasowane przez jedno z tych dwóch rozwiązań kandydujących, ponieważ żadne rozwiązanie nie zawiera zarówno wersji v1, jak i vn. W przypadku tych podproblemów ścieżka DP działa świetnie.