Jak mogę zweryfikować rozwiązanie problemu Traveling Salesman w czasie wielomianowym?

31

Tak więc problem decyzyjny TSP (problem sprzedawcy podróży) jest NP kompletny .

Ale nie rozumiem, w jaki sposób mogę sprawdzić, czy dane rozwiązanie TSP jest w rzeczywistości optymalne w czasie wielomianowym, biorąc pod uwagę, że nie ma sposobu na znalezienie optymalnego rozwiązania w czasie wielomianowym (co jest spowodowane tym, że problem nie występuje w P)?

Coś, co mogłoby mi pomóc zobaczyć, że weryfikacja może być faktycznie wykonana w czasie wielomianowym?

complexity-theory np-complete traveling-salesman

— Lazer
źródło

20

Mówiąc ściślej, nie wiemy, czy TSP jest w . Możliwe, że da się to rozwiązać w czasie wielomianowym, chociaż być może powszechne jest przekonanie, że . Przypomnijmy teraz, co to znaczy, że problemem jest -hard i -complete, patrz na przykład moja odpowiedź tutaj . Wierzę, że twoje źródło zamieszania wynika z definicji: problem trudny problem niekoniecznie występuje w . $\mathsf{P}$ $\mathsf{P} \neq \mathsf{NP}$ $\mathsf{NP}$ $\mathsf{NP}$ $\mathsf{NP}$ $\mathsf{NP}$

Jak podajesz ty i strona w Wikipedii, którą łączysz, problem decyzyjny jest kompletny: biorąc pod uwagę koszty i liczbę całkowitą , zdecyduj, czy wycieczka jest tańsza niż . Jednym ze sposobów dostrzeżenia problemu jest to, że polega na tym, że biorąc pod uwagę rozwiązanie, łatwo jest sprawdzić w czasie wielomianowym, czy rozwiązanie jest tańsze niż . Jak możesz to robić? Wystarczy postępować zgodnie z podaną trasą, zapisać całkowity koszt i ostatecznie porównać całkowity koszt do . $\mathsf{NP}$ $x$ $x$ $\mathsf{NP}$ $x$ $x$

— Juho
źródło

„Wystarczy postępować zgodnie z podaną trasą, zapisać całkowity koszt i na koniec porównać całkowity koszt do x”. -> Tak, ale istnieje wykładnicza liczba wycieczek do sprawdzenia!

— Lazer,

2

Wygląda na to, że byłem odrobinę za wolny. ;-)

— Niel de Beaudrap,

3

@ Lazer Nie, jest dokładnie jedna trasa do sprawdzenia. Dostajesz wycieczkę i rejestrujesz jej długość. Jeśli jest mniejsza niż , wyślij tak , w przeciwnym razie nie .

x

$x$

— Juho,

„zdecyduj, czy jest trasa”, to zdecydowanie oznacza, że nie mamy trasy. czego mi brakuje?

— Lazer,

3

@Lazer Nie, w problemie pojawia się wykres ważony i koszt docelowy. Certyfikat jest wycieczką. Aby uzyskać alternatywne wyjaśnienie, zobacz odpowiedź Niel. Podobnie jak w przykładzie na Wiki w przypadku SUBSET-SUM, nie otrzymujemy zera, ale zamiast tego otrzymujemy określony podzbiór jako certyfikat.

— Juho,

34

Chodzi o to, że musisz wziąć pod uwagę problem decyzyjny :

Problem podróżującego sprzedawcy (wersja decyzyjna). Biorąc pod uwagę wykres ważony G i koszt docelowy C , czy istnieje cykl hamiltonowski w G, którego waga wynosi co najwyżej C ?

Na „tak” przykład, świadectwo to tylko niektóre cykl Hamiltona, którego waga wynosi co najwyżej C . Jeśli potrafisz skutecznie rozwiązać ten problem, możesz znaleźć koszt minimalnej wycieczki za pomocą wyszukiwania binarnego, zaczynając od ciężaru całej sieci jako górnej granicy.

— Niel de Beaudrap
źródło

3

Prawdopodobnie myślisz o problemie ustalenia, czy dane rozwiązanie TSP jest najlepszym rozwiązaniem. Jednak nie ma znanego rozwiązania wielomianowego, co oznacza, że problem ten jest trudny w NP, ale niekoniecznie NP-Complete.

Problem decyzyjny TSP polega w rzeczywistości na określeniu, czy waga dowolnego rozwiązania na wykresie Gjest najbardziej kosztowna C(jak wyjaśniono lepiej w odpowiedzi Niel), co z pewnością można zweryfikować w czasie wielomianowym.

— Casey Kuball
źródło

5

Przepraszamy za pedanterię, ale TSP nie jest trudne NP, ponieważ są trasy . Na przykład sortowanie odbywa się w P, chociaż istniejemożliwe permutacje również. Ogromne lub szybko rosnące przestrzenie wyszukiwania nie zawsze oznaczają twardość.

O (n!)

$O(n!)$

n!

$n!$

— Juho,

@Juho Jest możliwe, aby zweryfikować, że sekwencja jest posortowana, wystarczy zaznaczyć, że . Jednak, aby wiedzieć, że coś jest NAJLEPSZYM rozwiązaniem dla TSP, należy wiedzieć, że koszt to koszt minimalny, który z natury wymaga znajomości wszystkich innych kosztów.

n_{0} <= n_{1} <= . . .

$n_0 <= n_1 <= ...$

— Casey Kuball,

4

Nie, możesz uzyskać optymalne nawet bez obliczania długości wszystkich innych tras. I tak, można udowodnić, że jest to optymalne bez obliczania wszystkich innych tras. Na przykład rozważ gałąź i powiązanie.

— Juho,

7

Mówię tylko, że ogromne przestrzenie wyszukiwania niekoniecznie oznaczają, że problem jest trudny. Nawet jeśli na przykład nie znamy lepszego algorytmu niż brutalna siła, który wylicza wszystkie możliwości, nie oznacza to, że jest to jedyny dostępny algorytm. Programowanie dynamiczne jest dobrym przykładem nawet tutaj: algorytm Held-Karp jest dokładnym algorytmem dla TSP działającym w czasie . Przepraszam, to prawdopodobnie tylko drapanie, ale chciałem tylko dodać przypomnienie :)

O (n^{2} 2^{n})

$O(n^22^n)$

— Juho

@Juho dobry punkt. Zaktualizowałem odpowiedź, aby nie wskazywała już brutalnej siły jako jedynej opcji (tyle, że nie ma żadnych rozwiązań wielomianowych).

— Casey Kuball,

2

$M$ $M$

— Rekurencyjnie ironiczny
źródło