11 Approximative Algorithmen
In diesem Kapitel werden Probleme behandelt, für die es höchstwahrscheinlich nur Algorithmen mit exponentieller Laufzeit gibt. Zunächst wird eine relativ informelle Einführung in die Komplexitätsklassen , und gegeben. Danach werden approximative Algorithmen eingeführt, und es werden Maßzahlen definiert, mit denen die Qualität dieser Algorithmen charakterisiert werden kann. Diese Maßzahlen sind zum einen wichtig, um verschiedene approximative Algorithmen zu vergleichen und zum anderen, um eine Abschätzung der Abweichung der erzeugten Lösung von der optimalen Lösung zu haben. Unter der Voraussetzung
Get Algorithmische Graphentheorie, 5th Edition 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.
