Cykl maksymalnej masy na wykresie

Question

Biorąc pod uwagę wykres ważony (skierowany lub nieukierunkowany) muszę znaleźć cykl wykresu o maksymalnej wadze.

Waga cyklu będącego sumą masy krawędzi wykresu.

To może być dowolny cykl, a nie tylko podstawa cyklu, dla którego możemy

• znaleźć wszystkie cykl bazową (patrz Algorithms to Identify All the Cycle Bases in a UnDirected Graph)
• obliczyć wagę każdego cyklu podstawowego i znaleźć maksymalna

Mogę spróbować wyliczyć wszystkie cykle wykresu, a następnie obliczyć maksimum, ale całkowita liczba cykli może być naprawdę duża (jeśli wykres jest kompletny, to każda sekwencja wierzchołków, gdzie pierwszy i ostatni są identyczne, jest cyklem) .

Czy masz pomysł, aby znaleźć ten maksymalny cykl masy bez wyliczenia wszystkich cykli?

Jeśli potrzebujesz hipotezy na wykresie (np. Liczby dodatnie), prosimy o ich podanie.

Answer 1

To jest NP-trudny.

Problem z cyklem Hamiltona można zredukować do tego.

Biorąc pod uwagę wykres, dla którego należy sprawdzić, czy istnieje cykl Hamiltona, czy nie, przypisz wagę 1 do każdej krawędzi.

Teraz uruchom algorytm, aby uzyskać maksymalny cykl ważenia. Jeśli waga to < n, to oryginalny wykres nie ma cyklu Hamiltona, w przeciwnym razie jest.

Answer 2

Jeśli możesz znaleźć minimalną ścieżkę ważoną w konkretnym przypadku, po prostu odwróć znaki wszystkich wag i zastosuj swój algorytm. Oczywiście robisz kilka nieokreślonych założeń, ponieważ argument Morona jest poprawny (gra słów nie jest zamierzona). Założenia, które robisz, mogą być dodatnimi lub ujemnymi. Myślę, że powinieneś postarać się je przedstawić, zamiast pozwolić ludziom szukać w nieskończonej przestrzeni możliwych założeń. Jeśli chodzi o wyniki twardości, jest to również trudne do oszacowania pod wieloma względami, sprawdź this paper. Ten sam artykuł zawiera kilka pozytywnych wyników dla ważnych typów wykresów, ale dotyczy najdłuższych nieważonych ścieżek, więc domyślam się, że większość algorytmów w gazecie nie pomoże bezpośrednio w twoim przypadku. Jeśli szukasz "Ciężkich cykli", znajdziesz wiele interesujących artykułów, ale mają one bardziej matematyczny charakter. Jeśli ważysz małe liczby całkowite (do wielomianu w rozmiarze wykresu), możesz spróbować zastąpić każdą krawędź nieważoną ścieżką, aby zredukować swój problem do nieważonego przypadku. Mam nadzieję, że w pewnym stopniu to pomoże, ale możesz mieć otwarty problem badawczy na swoich rękach.