Algorytmy i struktury danych · Senior · Pytanie 25 z 75
Rekruter opisuje problem, który sprowadza się do problemu komiwojażera. Jaka jest rozsądna reakcja?
- 1Powiedzieć, że jest nierozwiązywalny i odpowiedź nie istnieje
- 2Obiecać algorytm O(n log n) z sortowaniem według odległości
- ✓Poprawna odpowiedź: Zauważyć, że jest NP-trudny, i zaproponować heurystyki lub dokładne DP dla małych n
Wyjaśnienie
Nie jest znany żaden algorytm wielomianowy. Dokładne DP na maskach bitowych to O(n² × 2ⁿ), w porządku do około 20 miast. Dla prawdziwych tras używa się heurystyk, np. najbliższego sąsiada plus 2-opt, albo solvera, i akceptuje prawie optymalną odpowiedź.