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ść?
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
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