Ten problem pojawił się w moim niedawnym poście na blogu , przypuśćmy, że masz wycieczkę po TSP, czy jest to zgodne z NP-kompletnym, aby ustalić, czy jest to minimalne?
Dokładniej jest następujący problem NP-zupełny:
Instancja: Biorąc pod uwagę pełny wykres G z krawędziami ważonymi dodatnimi liczbami całkowitymi i prosty cykl C, który odwiedza wszystkie węzły G.
Pytanie: Czy istnieje prosty cykl D, który odwiedza wszystkie węzły G w taki sposób, że całkowity ciężar wszystkich krawędzi D w G jest ściśle mniejszy niż całkowity ciężar wszystkich krawędzi C w G?
Szkic możliwej redukcji, aby udowodnić, że jest kompletny NP.
Nieformalnie zaczyna się od zmodyfikowanej formuły 3SAT służącej do wykazania, że 3SAT jest kompletny z ASP (inny problem z rozwiązaniem) i „podąża” za standardowym łańcuchem redukcji 3SAT => BEZPOŚREDNI HAMCYCLE => BEZPOŚREDNI HAMCYCLE => TSP
Start z wzorem 3SAT φ z n zmiennych x1, . . . xn i m caluses do1, . . . , C.m ;
Trasformuj go do nowej formuły φ′ dodając nową zmienną t ...;
... i rozszerzenie każdej klauzuli do ( x i 1 ∨ x i 2 ∨ x i 3 ∨ t ) ;( xja1∨ xja2)∨ xja3))( xja1∨ xja2)∨ xja3)∨ t )
Od budowydiamenty strukturawykres G = { V , E } celu udowodnienia, że DIRECTED Hamiltona cykl jest NP-zupełny; przypuszczać, że każdy punkt C J odpowiadają węzła N J w G ;φ′G = { V, E}dojotN.jotsol
Zmodyfikuj na wykres G ′ = { V ′ , E ′ }, zastępując każdy węzeł trzema połączonymi węzłami i zmodyfikuj krawędzie zgodnie ze standardową redukcją zastosowaną w celu wykazania kompletności NP NIEZRÓŻNIONEGO CYKLU HAMILTONIANOWEGO z BEZPOŚREDNIEGO HAMILTONIAŃSKIEGO CYCLE tj. jest węzłem używanym do krawędzi przychodzących, jest węzłem używanym do krawędzi wychodzących;solsol′= { V′, E′}u 1 , u 2 , u 3 u 1 u 3uu1, u2),u3)u1u3)
Przekształć instancję NIEZBĘDNEGO CYKLU HAMILTONIAJSKIEGO na na instancję TSP w której wszystkie krawędzie mają wagę , z wyjątkiem (unikalnej) krawędzi diamentu przechodzącej na "dodatnie" przypisanie które ma masę (czerwona krawędź na poniższym rysunku); wreszcie krawędzie dodane w celu uzupełnienia mają ciężar . T G ′ w = 1 t w = 2 G ′ w = 3sol′T.sol′w = 1tw = 2sol′w = 3
Oczywiście instancja TSP ma prosty cykl, który odwiedza wszystkie węzły, co odpowiada zadowalającemu przypisaniu w którym (i ta trasa może być łatwo skonstruowana w czasie wielomianowym), ale ma całkowitą wagę (ponieważ używa krawędzi odpowiadającej przypisaniu która ma wagę 2). ma kolejny prosty cykl, który odwiedza wszystkie węzły o niższej masie całkowitejwtedy i tylko wtedy, gdy nie stosuje się krawędzi ciężaru która odpowiada przypisaniu ; lub równoważnie wtedy i tylko wtedy, gdy istnieje inne zadowalające przypisanieφ ′ t = t r u e | V ′ | + 1 t = t r u e T | V ′ | 2 t = t r u e φ ′ t = f a l s e φT.φ′t = t r u e| V.′| +1t = t r u eT.| V.′|2)t = t r u eφ′w którym
; ale może to być prawdą tylko wtedy, gdy oryginalna formuła jest zadowalająca.t = fa l s eφ
Zastanowię się więcej i napiszę formalny dowód (jeśli nie okaże się, że jest źle :-). Daj mi znać, jeśli potrzebujesz dodatkowych informacji na temat jednego lub więcej powyższych fragmentów.
Jak zauważył domotorp, interesującą konsekwencją jest to, że następujący problem jest NP-zupełny: Czy biorąc pod uwagę wykres i ścieżkę hamiltonowską, ma cykl hamiltonowski?Gsolsol
Więc zasadniczo pokazujesz, że biorąc pod uwagę wykres i ścieżkę H, to NPc decyduje, czy ma cykl H, prawda?
domotorp
Wygląda świetnie. Dzięki za włożenie wysiłku w napisanie. Kilka zmian, aby bezpośrednio odpowiedzieć na moje pytanie: Krawędzie wykresu powinny mieć wagę 1, z wyjątkiem tej specjalnej krawędzi, która powinna być ważona 2, a nie-krawędzie powinny być ważone 3.
Lance Fortnow
1
Jeśli usuniesz tę określoną krawędź z , wtedy H 1 stanie się ścieżką H, a H 2 pozostanie cyklem H, więc zasadniczo pokazujesz to, co napisałem, prawda? Dla mnie to stwierdzenie wygląda bardziej interesująco niż pierwotne pytanie. solH.1H.2)
Ojej ... Mam wrażenie, jakbyś „przywitał kierownicę” :-) Papier jest za paywallem SIAM, czy dowód jest podobny do mojego?
Marzio De Biasi,
Nie mam dostępu do gazety, ale możesz znaleźć dowody także w części 19.9 ich książki , która może być bardziej dostępna.
Marcus Ritt,
Ok dzięki! Dowód jest inny (modyfikują instancję problemu obwodu hamiltonowskiego do G ′, która zawsze ma ścieżkę hamiltonowską, ale ma obwód hamiltonowski tylko wtedy, gdy G ma obwód hamiltonowski). Ale muszę zaktualizować artykuł, który opublikowałem w arXiv i przyjąć do wiadomości, że nie jest to nowy wynik (lub go usunąć). Co myślisz? solsol′sol
Marzio De Biasi,
@Marzio de Biasi Myślę, że aktualizacja dokumentu jest w porządku. Twój alternatywny dowód jest nadal interesujący.
Papadimitriou i Steiglitz (1977) wykazali zupełność NP tego problemu.
źródło