July 2024
Intermediate to advanced
336 pages
9h 48m
German
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 ...
Read now
Unlock full access