Czy zadanie polegałoby na wypisaniu, czy aczy dane słowo jest mieszane, czy prawdziwe angielskie słowo może być problemem równoważnym z problemem podróżnego sprzedawcy? Dobrze znaną strategią jest generowanie wszystkich permutacji danego słowa i porównywanie ich wszystkich ze wszystkimi słowami w słowniku angielskim. Ten algorytm miałby złożoność czasową wynoszącą O(N!). Mogłem sobie wyobrazić, że te dwa różnią się między sobąważny aspekt: gdy znajdziesz permutację pasującą do słowa, możesz przestać generować permutacje, podczas gdy z TSP musisz wypróbować każdą kombinację tras niezależnie. Napisałem jednak algorytm, który zamiast generować wszystkie permutacje danego słowa o długości nzamiast tego sortuje litery w danym słowiei wykonuje ten sam algorytm na słowach słownika, a następnie porównuje dwa posortowane ciągi (ta metoda działa przez 100% czasu). Mój algorytm używa domyślnego sortowania Java, a po zbadaniu okazało się, że działa O(n log n). W sumie mój program działa na O(n log n) ponieważ ten termin rośnie jako największy nzbliża się do nieskończoności. Algorytm działa w czasie krótszym niż wielomianowy. Tak więc, jeśli problemy są równoważne, czy nie możesz zastosować podobnej metody do rozwiązania problemu TSP? W jaki sposób odnosi się to do P vs. NP? Przepraszam, jeśli coś z tego nie miało sensu lub nie używałem terminologii poprawnie, nie mam doświadczenia w tej dziedzinie
Odpowiedzi:
4 dla odpowiedzi № 1Fakt, że istnieją algorytmy tego samegozłożoność rozwiązania dwóch problemów niekoniecznie oznacza, że problemy mają tę samą złożoność, ponieważ mogą istnieć bardziej wydajne algorytmy dla jednego z problemów, ale nie dla drugiego.
Właściwy sposób powiązania złożoności różnych problemów to zmniejszenie: Jeśli możesz pokazać, że wystąpił problem ZA można przekształcić w wystąpienie problemu b w taki sposób, że odpowiedź na przekształconą instancję jest taka sama jak odpowiedź na oryginalną instancję, a następnie problem b jest co najmniej tak złożony jak problem ZA (ponieważ algorytm, który rozwiązuje b również może rozwiązać ZA). Jeśli możesz pokazać zmniejszenie również w przeciwnym kierunku, ZA i b są równie złożone.
W twoim przypadku nie jest obecnie znany sposóbprzekształcić arbitralny problem TSP w równoważny problem nieszyfrujący, więc nie jest (według naszej najlepszej wiedzy), że problemy mają tę samą złożoność.