Jak można ograniczyć błąd przybliżenia, nie znając optymalnego rozwiązania?

14

Patrzyłem na tę stronę i mówi, że ludzie znaleźli rozwiązania dla wycieczek TSP, które są tylko o 0,031% wyższe niż optymalna wycieczka. Bez znalezienia optymalnej trasy, skąd wiedzą, jaka to powinna być długość?

complexity-theory approximation Ilya Gazman
źródło
4
Rozwiązania są NAJBARDZIEJ 0,031% wyższe niż optymalna trasa. Bez znalezienia optymalnej trasy nadal można znaleźć na niej dolną granicę i algorytm aproksymacyjny, które pozwalają zatem „porównać” przybliżone rozwiązania z optymalnym rozwiązaniem.
Tpecatte
3
Naprawdę powinieneś naprawdę wybrać książkę o teorii złożoności i / lub rozwiązywaniu trudnych problemów NP . Nie masz nadziei, że rozwiążesz P? = NP w swoim życiu i przekonasz wszystkich, że to zrobiłeś, jeśli nadal wysuwałeś propozycje / pytania, które dowodzą, że nie rozumiesz pojęć licencjackich. Oczywiście możemy pomóc ci w zrozumieniu tego.
Raphael
pomocne byłoby zacytowanie osoby określającej ten limit [TO, to samo]. afaik, ogólny limit czasu P nie jest znany. istnieją inne granice aproksymacji wyrażone w funkcjach parametrów problemu, np. punkty itp.
vzn

Odpowiedzi:

8

Zasadniczo, gdy chcesz ograniczyć współczynnik przybliżenia algorytmu, szukasz łatwej dolnej granicy optymalnej wartości. Najprostszym jest często rozluźnienie LP (odpowiednio dobranego) sformułowania problemu ILP. Czasami używane są inne rzeczy, na przykład w TSP możesz również użyć masy MST (optymalna trasa minus jedna krawędź to drzewo, więc nie może ważyć mniej niż MST).

W szczególnych przypadkach możesz oczywiście nadal używać rzeczy, których używasz w swoich dowodach, tzn. Możesz rozwiązać LP i porównać swoje heurystyczne rozwiązanie z wartością LP. Jeśli masz więcej czasu na procesorze, możesz także rozpocząć proces związany z rozwiązaniem ILP. Nawet jeśli nie rozwiążesz całkowicie ILP, uzyskasz lepsze dolne granice z dualności LP.

adrianN
źródło
Czy możesz mi wyjaśnić lub podać link do przeczytania. Co to jest LP, ILP, MST
Ilya Gazman
1
Zredagowałem swoją odpowiedź, aby uwzględnić linki wikipedii.
adrianN