faecher:informatik:oberstufe:graphen:zpg:dominierende_menge:start

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

Link zu der Vergleichsansicht

Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung
Nächste Überarbeitung		 Vorherige Überarbeitung
faecher:informatik:oberstufe:graphen:zpg:dominierende_menge:start [26.11.2022 17:16] – [Greedy-Strategie] Frank Schiebelfaecher:informatik:oberstufe:graphen:zpg:dominierende_menge:start [20.09.2024 11:39] (aktuell) – Marco Kuemmel
Zeile 1: Zeile 1:
-====== Eisverkäufer ======+====== Eisverkäufer: Dominierende Menge ======
  
 {{ :faecher:informatik:oberstufe:graphen:zpg:dominierende_menge:auswahl_393.png?600 |}} {{ :faecher:informatik:oberstufe:graphen:zpg:dominierende_menge:auswahl_393.png?600 |}}
Zeile 25: Zeile 25:
 Zu diesem Problem gibt es **zwei Fragestellungen**: Zu diesem Problem gibt es **zwei Fragestellungen**:
  
-  * **Existenz:** Gibt es eine dominierende Menge mit weniger als Knoten, als der Graph hat?+  * **Existenz:** Gibt es überhaupt eine dominierende Menge mit weniger Knoten, als der Graph hat?
   * **Optimale Lösung:** Finde eine dominierende Menge mit möglichst wenigen Knoten.   * **Optimale Lösung:** Finde eine dominierende Menge mit möglichst wenigen Knoten.
  
-===== Keine effizienter Algorithmus? =====+===== Kein effizienter Algorithmus? =====
 Du hast sicher eine Lösung für den Eisverkäufer gefunden, die die Abdeckung der Stadt mit Eisständen sicherstellt. Aber ist das die beste Lösung? Vielleicht geht es ja mit weniger Eisständen.  Du hast sicher eine Lösung für den Eisverkäufer gefunden, die die Abdeckung der Stadt mit Eisständen sicherstellt. Aber ist das die beste Lösung? Vielleicht geht es ja mit weniger Eisständen. 
  
Zeile 48: Zeile 48:
 === (A3) === === (A3) ===
  
-Führe im Simulationsmodus des Programms Graphentester den Algorithmus //"Dominierende Menge (Vollständig)"// bei den Graphen ''graph_knotenX.csv'' (X=5-10) aus und bestimme den Zeitbedarf. Stelle dabei die Geschwindigkeit so ein, dass beim Graphen mit 5 Knoten ca. 3 Sek. benötigt werden.+Führe im Simulationsmodus des Programms Graphentester den Algorithmus //"Dominierende Menge (Vollständig)"// bei den Graphen ''graph_knotenX.csv'' (X=5-10) aus und bestimme den Zeitbedarf. Stelle dabei die Geschwindigkeit so ein, dass beim Graphen mit 5 Knoten ca. 3 Sek. benötigt werden. __Hinweis:__ Die Klasse ist zu finden bei ''algorithmen/GraphAlgo_DominatingSetBacktracking''. 
 Untersuche, wie sich der Zeitbedarf durch einen zusätzlichen Knoten verändert. Untersuche, wie sich der Zeitbedarf durch einen zusätzlichen Knoten verändert.
  
Zeile 59: Zeile 60:
   * Berechne, wie lange es für das Einstiegsbeispiel dauern würde.   * Berechne, wie lange es für das Einstiegsbeispiel dauern würde.
  
 +----
  
 +<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 ($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 ($O(n^c)$ mit c = Konstante).
 +</WRAP>
 ===== Näherungslösung ===== ===== Näherungslösung =====
  
Zeile 77: Zeile 83:
 Die **Greedy-Strategie** (gieriger Algorithmus) ist ein Ansatz, um Näherungslösungen zu bestimmen. Sie zeichnen sich dadurch aus, dass sie nacheinander die Möglichkeit auswählen, die zum Zeitpunkt der Wahl den größten Gewinn bzw. das beste Ergebnis verspricht.  Die **Greedy-Strategie** (gieriger Algorithmus) ist ein Ansatz, um Näherungslösungen zu bestimmen. Sie zeichnen sich dadurch aus, dass sie nacheinander die Möglichkeit auswählen, die zum Zeitpunkt der Wahl den größten Gewinn bzw. das beste Ergebnis verspricht.
  
-Beim Problem der dominierenden Menge fügt man schrittweise der gesuchten Teilmenge Knoten hinzu, bis sie eine überdeckende Teilmenge darstellt. In jeden Schritt versucht man natürlich, den Eisstand möglichst gut zu platzieren. Hat man einen Knoten jedoch einmal hinzugefügt, nimmt man diese Entscheidung nicht mehr zurück, auch wenn man später erkennt, dass die Entscheidung nicht optimal war.+Beim Problem der dominierenden Menge fügt man schrittweise der gesuchten Teilmenge Knoten hinzu, bis sie eine überdeckende Teilmenge darstellt. In jedem Schritt versucht man natürlich, den Eisstand möglichst gut zu platzieren. Hat man einen Knoten jedoch einmal hinzugefügt, nimmt man diese Entscheidung nicht mehr zurück, auch wenn man später erkennt, dass die Entscheidung nicht optimal war.
  
 Es stellt sich jetzt allerdings die Frage, was genau eine "möglichst gute" Platzierung in einem Schritt bedeuten soll. Es stellt sich jetzt allerdings die Frage, was genau eine "möglichst gute" Platzierung in einem Schritt bedeuten soll.
Zeile 87: Zeile 93:
 Analysiere, welcher Knoten als nächstes hinzugefügt werden sollte.  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 der 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.   * a) der Knoten mit den meisten Nachbarknoten.
Zeile 98: Zeile 104:
   * h) der noch nicht überdeckte Knoten, der von möglichst vielen schon ausgewählten Knoten die Entfernung 3 hat.   * h) der noch nicht überdeckte Knoten, der von möglichst vielen schon ausgewählten Knoten die Entfernung 3 hat.
   * i) der noch nicht überdeckte Knoten mit der größten Entfernung von allen schon ausgewählten Knoten.   * i) der noch nicht überdeckte Knoten mit der größten Entfernung von allen schon ausgewählten Knoten.
 +
 +----
 +{{:aufgabe.png?nolink  |}}
 +=== (A7) ===
 +
 +Wende die erfolgversprechenden Strategien auf das Einstiegsbeispiel an.
 +
 +----
 +{{:aufgabe.png?nolink  |}}
 +=== (A8) ===
 +Begründe, warum die Näherungslösungen viel schneller als die optimale Lösung gefunden werden.
  • faecher/informatik/oberstufe/graphen/zpg/dominierende_menge/start.1669482995.txt.gz
  • Zuletzt geändert: 26.11.2022 17:16
  • von Frank Schiebel