Jednowymiarowy problem ścieżki sprzedawcy podróży jest oczywiście tym samym, co sortowanie, a zatem można go rozwiązać dokładnie przez porównanie w czasie , ale sformułowano go w taki sposób, aby przybliżenie, a także dokładne rozwiązanie ma sens. W modelu obliczeń, w którym dane wejściowe są liczbami rzeczywistymi i możliwe jest zaokrąglanie do liczb całkowitych, łatwo jest aproksymować do współczynnika , dla dowolnej stałej , w czasie : znajdź min i maks, zaokrąglij wszystko do liczby w odległości od pierwotnej wartości, a następnie użyj sortowania radix. Ale modele z zaokrąglaniem mają problematyczną teorię złożoności, co doprowadziło mnie do zastanowienia się, a co ze słabszymi modelami obliczeń?
Jak dokładnie można aproksymować jednowymiarowy TSP w liniowym modelu drzewa porównawczego obliczeń (każdy węzeł porównawczy testuje znak funkcji liniowej wartości wejściowych) za pomocą algorytmu, którego złożoność czasowa wynosi ? Ta sama metoda zaokrąglania umożliwia uzyskanie dowolnego współczynnika aproksymacji postaci (za pomocą wyszukiwania binarnego w celu wykonania zaokrąglenia i zaokrąglenia znacznie bardziej zgrubnie, aby było wystarczająco szybkie). Ale czy możliwe jest osiągnięcie nawet współczynnika aproksymacji takiego jak dla niektórych ?
źródło
Odpowiedzi:
EDYCJA (AKTUALIZACJA): Dolną granicę w mojej odpowiedzi poniżej udowodniono (innym dowodem) w „O złożoności przybliżania podróży euklidesowych sprzedawcom i minimalnym drzewom spinającym”, autorstwa Das i in .; Al Algorytmica 19: 447-460 (1997).
Nie. Oto dolna granica.
Roszczenie. Dla każdego każdy algorytm aproksymacji oparty na porównaniu wymaga w najgorszym przypadku porównań .n 1 - ϵ Ω ( ϵ n log n )ϵ>0 n1−ϵ Ω(ϵnlogn)
Pod pojęciem „na podstawie porównania” rozumiem dowolny algorytm, który wysyła zapytania tylko do danych wejściowych za pomocą zapytań binarnych (prawda / fałsz).
Oto próba dowodu. Mam nadzieję, że nie ma błędów. FWIW wydaje się, że dolna granica rozciąga się na algorytmy losowe.
Skoryguj i dowolnie mały, ale ciągłego .ϵ > 0n ϵ>0
Rozważ tylkoinstancje wejściowe „permutacja” które są permutacjami . Optymalne rozwiązanie dla każdego takiego przypadku ma koszt .( x 1 , x 2 , … , x n ) [ n ] n - 1n! (x1,x2,…,xn) [n] n−1
Zdefiniuj koszt permutacji jako. Modeluj algorytm jako przyjmujący permutację , wyprowadzający permutację i płacący koszt .cπ π π ′ d ( π , π ′ ) = c ( π ′ ∘ π )c(π)=∑i|π(i+1)−π(i)| π π′ d(π,π′)=c(π′∘π)
Zdefiniuj jako minimalną liczbę porównań dla dowolnego algorytmu opartego na porównaniu, aby osiągnąć współczynnik konkurencyjny w tych przypadkach. Ponieważ opt ma wartość , algorytm musi gwarantować koszt co najwyżej .n 1 - ϵ n - 1 n 2 - ϵC n1−ϵ n−1 n2−ϵ
Pokażemy .C≥Ω(ϵnlogn)
Zdefiniuj aby dla każdego możliwego wyjścia był ułamek możliwych nakładów, dla których wyjście osiągnęłoby koszt co najwyżej . Ta część jest niezależna od .π ′ π ′ n 2 - ϵ π ′P π′ π′ n2−ϵ π′
π c ( π ) n 2P równa się również prawdopodobieństwu, że dla losowej permutacji jego koszt wynosi najwyżej . (Aby zobaczyć dlaczego, weź jako permutację tożsamości Następnie jest ułamkiem danych wejściowych, dla których
co najwyżej , ale .)π c(π) π ′ IPd(π,I) n 2 - ϵ d(π,I)=c(π)n2−ϵ π′ I P d(π,I) n2−ϵ d(π,I)=c(π)
Lemat 1. .C≥log21/P
Dowód. Napraw dowolny algorytm, który zawsze używa mniej niż porównań. Drzewo decyzyjne algorytmu ma głębokość mniejszą niż , więc jest mniej niż liści, a dla niektórych permutacji wyjściowych algorytm podaje jako wyjście dla więcej niż ułamek nakładów. Z definicji , dla co najmniej jednego takiego wejścia, wynik daje koszt większy niż . CO BYŁO DO OKAZANIAlog21/P 1 / P π ′ π ′ P P π ′ n 2 - ϵlog21/P 1/P π′ π′ P P π′ n2−ϵ
Lemma 2. .P≤exp(−Ω(ϵnlogn))
Zanim podamy dowód na Lemat 2, zauważ, że dwa lematy razem dają roszczenie:
Dowód lematu 2. Niech będzie przypadkową permutacją. Przypomnijmy, że równa się prawdopodobieństwu, że jego koszt wynosi najwyżej . Powiedz, że każda para jest przewagą kosztu, więc jest sumą kosztów brzegowych.P c ( π )π P c(π) ( i , i + 1 ) | π ( i + 1 ) - π ( i ) | c ( π )n2−ϵ (i,i+1) |π(i+1)−π(i)| c(π)
Załóżmy, że .c(π)≤n2−ϵ
Następnie dla dowolnego najwyżej krawędzi ma koszt lub więcej. Powiedz, że krawędzie kosztują mniej niż są tanie .n 2 - ϵ / q q qq>0 n2−ϵ/q q q
Napraw . Zastępując i upraszczając, najwyżej krawędzi nie są tanie. n 1 - ϵ / 2q=n1−ϵ/2 n1−ϵ/2
Tak więc co najmniej krawędzi jest tanie. Tak więc istnieje zestaw zawierający tanich krawędzi.S n / 2n−n1−ϵ/2≥n/2 S n/2
Roszczenie. Dla danego zbioru o krawędzi, prawdopodobieństwo, że wszystkie krawędzie w są tanie, co najwyżej .n / 2 S exp ( - Ω ( ϵ n log n ) )S n/2 S exp(−Ω(ϵnlogn))
Zanim udowodnimy to twierdzenie, zwróć uwagę, że sugeruje to następujący lemat. Według twierdzenia i naiwnego związku, prawdopodobieństwo istnienia takiego zestawu wynosi co najwyżej ( nS ≤exp
Dowód roszczenia. Wybierz w następujący sposób. Wybierz jednolicie z , następnie wybierz jednolicie z , a następnie wybierz jednolicie z itd.π ( 1 ) [ n ] π ( 2 )π π(1) [n] π(2) π ( 3 ) [ n ] - { π ( 1 ) , π ( 2 ) }[n]−{π(1)} π(3) [n]−{π(1),π(2)}
Rozważmy brzeg w . Rozważ czas tuż po wybraniu , kiedy zostanie wybrany . Niezależnie od pierwszych wyborów (dla dla ), istnieje co najmniej wybór dla , a najwyżej z nich wybory dadzą przewagę mniejszą niż (co czyni ją tanią).S π ( i ) π ( i + 1(i,i+1) S π(i) i π ( j ) j ≤ i n - i π ( i + 1 ) 2 n 1 - ϵ / 2 ( i , i + 1 ) n 1 - ϵ / 2π(i+1) i π(j) j≤i n−i π(i+1) 2n1−ϵ/2 (i,i+1) n1−ϵ/2
Zatem, zależnie od pierwszych wyborów , prawdopodobieństwo, że krawędź jest tania, wynosi najwyżej . Zatem prawdopodobieństwo, że wszystkie zbocza w są tanie, wynosi co najwyżej Od czasu , w jest co najmniej krawędzi z . Tak więc ten produkt jest co najwyżej 2 n 1 - ϵ / 2i n/2S∏(i,i+1)∈S2n 1 - ϵ / 22n1−ϵ/2n−i n/2 S | S| ≥n/2n/4Sn-i≥n/4(2n 1 - ϵ / 2
CO BYŁO DO OKAZANIA
źródło