Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:graphen:zpg:dominierende_menge:start [26.11.2022 18:06] – [Keine effizienter Algorithmus?] Frank Schiebel
+++ faecher:informatik:oberstufe:graphen:zpg:dominierende_menge:start [27.11.2022 19:47] (aktuell) – [Keine effizienter Algorithmus?] Frank Schiebel
@@ Zeile 1: / Zeile 1: @@
-====== Eisverkäufer ======
+====== Eisverkäufer: Dominierende Menge ======
 {{ :faecher:informatik:oberstufe:graphen:zpg:dominierende_menge:auswahl_393.png?600 |}}
@@ Zeile 28: / Zeile 28: @@
   * **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.
@@ Zeile 60: / Zeile 60: @@
-==== Näherungslösung ====
+===== Näherungslösung =====
-Wenn es zu lange dauert, die beste Lösung zu finden, ist man manchmal auch mit einer guten Lösung zufrieden: Ein oder zwei Eisstände mehr als bei der optimalen Lösung sind in einer Stadt kein Problem.
+Wenn es zu lange dauert, die **beste** Lösung zu finden, ist man manchmal auch mit einer **guten** Lösung zufrieden: Ein oder zwei Eisstände mehr als bei der optimalen Lösung sind in einer Stadt kein Problem.
+----
+{{:aufgabe.png?nolink  |}}
+=== (A5) ===
+Beschreibe, wie du vorgegangen bist, um deine Lösung im Einstiegsbeispiel zu finden.
+----
+==== Greedy-Strategie ====
+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.
+Es stellt sich jetzt allerdings die Frage, was genau eine "möglichst gute" Platzierung in einem Schritt bedeuten soll.
+----
+{{:aufgabe.png?nolink  |}}
+=== (A6) ===
+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:
+  * a) der Knoten mit den meisten Nachbarknoten.
+  * b) der Knoten mit den wenigsten Nachbarknoten.
+  * c) der Knoten, der die meisten Knoten neu überdeckt.
+  * d) der Knoten der die wenigsten Knoten neu überdeckt.
+  * e) ein Knoten, der von einem schon ausgewählten Knoten die Entfernung 3 hat.
+  * f) ein noch nicht überdeckter Knoten mit Entfernung 2 von einem schon ausgewählten Knoten.
+  * g) ein noch nicht überdeckter Knoten mit Entfernung 3 von einem schon ausgewählten Knoten.
+  * 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.
+----
+{{: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.