Anhang B: NP-schwere Probleme
Das Mengenüberdeckungsproblem und das Problem des Handlungsreisenden haben eine Gemeinsamkeit: Sie sind beide schwer zu lösen. Du musst jeden möglichen Schätzwert prüfen, um die kleinste Überdeckung oder die kürzeste Route zu finden.
Die beiden Probleme sind NP-schwer. NP ist eine Komplexitätsklasse. Ich habe festgestellt, dass die Begriffe NP, NP-schwer und NP-vollständig immer wieder zu Verwirrung führen – auch bei mir. In diesem Anhang möchte ich erklären, was die einzelnen Begriffe bedeuten. Aber bevor ich damit beginne, muss ich dir ein paar andere Konzepte vorstellen. Die folgende Abbildung zeigt, wie die einzelnen Schritte dieser Reise aufeinander aufbauen:
Bereit? Gut, dann fange ich besser damit an ...
Get Algorithmen kapieren - Visuell lernen und verstehen mit Illustrationen, Alltagsbeispielen und Python-Code now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
