NP-складність - це клас задач, для яких дуже складно знайти рішення, але легко перевірити правильність уже готового. Іншими словами, якщо ви здогадалися про відповідь, то перевірити її можна швидко, але сам процес пошуку займає надзвичайно багато часу.
Приклади NP-складних задач:
- Задача комівояжера - як знайти найкоротший маршрут, що проходить через усі міста.
- Розклад занять - скласти оптимальний розклад так, щоб усі викладачі, аудиторії та студенти збіглися без конфліктів.
- Розбиття на підмножини - поділити набір чисел на групи з однаковою сумою.
Де це важливо в реальному житті:
- Логістика та маршрути доставки.
- Планування виробництва та розкладів.
- Криптографія й безпека даних.
Простий Ruby-приклад для демонстрації ідеї повного перебору (на прикладі підмножин):
# NP-складна задача: пошук підмножини з потрібною сумою
numbers = [3, 7, 9, 11, 15]
target = 20
solutions = []
(1..numbers.size).each do |k|
numbers.combination(k).each do |subset|
solutions << subset if subset.sum == target
end
end
puts "Знайдені рішення:"
solutions.each { |s| p s }
Результат:
Знайдені рішення: [9, 11]
Тут видно одразу кілька варіантів. А якщо збільшити масив до 20–25 чисел, кількість перевірок різко зросте - саме так виглядає комбінаторний вибух, через який подібні NP-складні задачі стають практично нерозв’язними перебором.
Цей допис поки що не має жодних доповнень від автора/ки.
