Ta treść została automatycznie przetłumaczona z ukraińskiego.
NP-trudność - to klasa problemów, dla których bardzo trudno znaleźć rozwiązanie, ale łatwo sprawdzić poprawność już gotowego. Innymi słowy, jeśli zgadłeś odpowiedź, to można ją szybko zweryfikować, ale sam proces poszukiwania zajmuje niezwykle dużo czasu.
Przykłady problemów NP-trudnych:
- Problem komiwojażera - jak znaleźć najkrótszą trasę, która przechodzi przez wszystkie miasta.
- Plan zajęć - stworzyć optymalny plan tak, aby wszyscy nauczyciele, sale i studenci zgrali się bez konfliktów.
- Podział na podzbiory - podzielić zbiór liczb na grupy o równej sumie.
Gdzie to jest ważne w życiu codziennym:
- Logistyka i trasy dostaw.
- Planowanie produkcji i harmonogramów.
- Kryptografia i bezpieczeństwo danych.
Prosty przykład w Ruby do demonstrowania idei pełnego przeszukiwania (na przykładzie podzbiorów):
# NP-trudny problem: wyszukiwanie podzbioru o wymaganej sumie
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 "Znalezione rozwiązania:"
solutions.each { |s| p s }
Wynik:
Znalezione rozwiązania: [9, 11]
Widać tutaj od razu kilka wariantów. A jeśli zwiększyć tablicę do 20–25 liczb, liczba sprawdzeń gwałtownie wzrośnie - tak właśnie wygląda wybuch kombinatoryczny, przez który podobne problemy NP-trudne stają się praktycznie nierozwiązywalne przez przeszukiwanie.
