Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:graphen:zpg:dominierende_menge:start [14.09.2024 11:31] – [Kein effizienter Algorithmus?] 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%>
-  * 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.
+  * 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).
 </WRAP>
 ===== Näherungslösung =====
@@ Zeile 93: / Zeile 93: @@
 Analysiere, welcher Knoten als nächstes hinzugefügt werden sollte.
-Notiere zunächst deine Überlegungen und kontrolliere die Ergebnisse dann mit dem Graphentester "Dominierende Menge (Greedy (a-i))" anhand der Graphen //"graph_domknotenXX"//. Dort sind die dominierenden Knoten einer optimalen Lösung mit einem Stern (*) markiert. Du kannst also untersuchen, wie gut eine Strategie funktioniert:
+Notiere zunächst deine Überlegungen und kontrolliere die Ergebnisse dann mit dem Graphentester "Dominierende Menge (Greedy (a-i))" anhand der Graphen //''graph_knoten10''// und //''graph_knoten15''//. ((Ursprünglich waren hier die Graphen //"graph_domknotenXX"// vorgesehen, diese scheinen aber nicht zu funktionieren. Dort sind die dominierenden Knoten einer optimalen Lösung mit einem Stern (*) markiert.)) Beim Graphen mit 10 Knoten enthält die optimale Lösung der dominierenden Menge **2** Knoten, beim Graphen mit 15 Knoten **4** Knoten. Du kannst also untersuchen, wie gut eine Strategie funktioniert. Notiere dir am besten pro Graph und Strategie die jeweilige Lösung, um dann die insgesamt beste Lösung ermitteln zu können.
   * a) der Knoten mit den meisten Nachbarknoten.