Алгоритми та структури даних · Senior · Запитання 25 з 75
Інтерв'юер описує задачу, що зводиться до задачі комівояжера. Яка розумна реакція?
- 1Сказати, що вона нерозв'язна й відповіді не існує
- 2Пообіцяти алгоритм за O(n log n) із сортуванням за відстанню
- ✓Правильна відповідь: Зауважити, що вона NP-складна, і запропонувати евристики або точне DP для малих n
Пояснення
Поліноміального алгоритму не відомо. Точне DP по бітових масках - O(n² × 2ⁿ), прийнятне приблизно до 20 міст. Для реальних маршрутів використовують евристики, як-от найближчий сусід плюс 2-opt, або солвер, і приймають майже оптимальну відповідь.