Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
| Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung | |||
| faecher:informatik:oberstufe:graphen:zpg:dominierende_menge:start [14.09.2024 13:38] – Marco Kuemmel | faecher:informatik:oberstufe:graphen:zpg:dominierende_menge:start [20.09.2024 11:39] (aktuell) – Marco Kuemmel | ||
|---|---|---|---|
| Zeile 63: | Zeile 63: | ||
| <WRAP center round info 95%> | <WRAP center round info 95%> | ||
| - | * Würde man also alle Teilmengen (alle möglichen Lösungen) überprüfen und davon die tatsächlich beste wählen, so wäre die Laufzeit exponentiell ($2^n$ mit n = Anzahl der Knoten). Das ist für Algorithmen eine geradezu katastrophale Laufzeit. | + | * Würde man also alle Teilmengen (alle möglichen Lösungen) überprüfen und davon die tatsächlich beste wählen, so wäre die Laufzeit exponentiell ($O(2^n)$ mit n = Anzahl der Knoten). Das ist für Algorithmen eine geradezu katastrophale Laufzeit. |
| - | * In so einem Fall versucht man fast immer eine andere algorithmische Vorgehensweise zu finden, die vielleicht nicht die perfekte Lösung findet, aber eine vergleichsweise gute Lösung in dafür viel kürzerer Zeit findet. Die alternative Lösung hat dann typischerweise eine polynomielle Laufzeit ($n^c$ mit c = Konstante). | + | * In so einem Fall versucht man fast immer eine andere algorithmische Vorgehensweise zu finden, die vielleicht nicht die perfekte Lösung findet, aber eine vergleichsweise gute Lösung in dafür viel kürzerer Zeit findet. Die alternative Lösung hat dann typischerweise eine polynomielle Laufzeit ($O(n^c)$ mit c = Konstante). |
| </ | </ | ||
| ===== Näherungslösung ===== | ===== Näherungslösung ===== | ||