Dieser Inhalt wurde automatisch aus dem Ukrainischen übersetzt.
NP-Schwierigkeit - ist eine Klasse von Aufgaben, für die es sehr schwierig ist, eine Lösung zu finden, aber einfach, die Richtigkeit einer bereits gefundenen zu überprüfen. Mit anderen Worten, wenn Sie die Antwort erraten haben, können Sie sie schnell überprüfen, aber der Prozess der Suche selbst dauert extrem lange.
Beispiele für NP-schwierige Aufgaben:
- Das Handelsreisendenproblem - wie man die kürzeste Route findet, die durch alle Städte führt.
- Stundenplan - einen optimalen Stundenplan erstellen, sodass alle Dozenten, Räume und Studenten ohne Konflikte zusammenpassen.
- Teilmenge - eine Menge von Zahlen in Gruppen mit der gleichen Summe aufteilen.
Wo das im echten Leben wichtig ist:
- Logistik und Lieferwege.
- Produktions- und Zeitplanungsplanung.
- Kryptografie und Datensicherheit.
Ein einfaches Ruby-Beispiel zur Demonstration der Idee der vollständigen Durchsuchung (am Beispiel von Teilmengen):
# NP-schwierige Aufgabe: Suche nach einer Teilmenge mit der gewünschten Summe
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 "Gefundene Lösungen:"
solutions.each { |s| p s }
Ergebnis:
Gefundene Lösungen: [9, 11]
Hier sind sofort mehrere Varianten sichtbar. Und wenn man das Array auf 20–25 Zahlen erhöht, steigt die Anzahl der Überprüfungen sprunghaft an - so sieht der kombinatorische Explosion aus, durch die solche NP-schwierigen Aufgaben durch vollständige Durchsuchung praktisch unlösbar werden.
