Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung Nächste Überarbeitung | Vorherige Überarbeitung Nächste ÜberarbeitungBeide Seiten, nächste Überarbeitung | ||
faecher:informatik:oberstufe:graphen:zpg:kartenfaerben:start [06.12.2022 12:33] – [Weiterführende Fragen & Aufgaben] Frank Schiebel | faecher:informatik:oberstufe:graphen:zpg:kartenfaerben:start [06.12.2022 12:36] – [Beschreibung] Frank Schiebel | ||
---|---|---|---|
Zeile 57: | Zeile 57: | ||
++++ Lösungsvorschlag | | ++++ Lösungsvorschlag | | ||
{{ : | {{ : | ||
- | Werden die Knoten in der angegebenen Reihenfolge | + | Werden die Knoten in der angegebenen Reihenfolge |
++++ | ++++ | ||
- | ===== Algorithmus ===== | ||
+ | ---- | ||
+ | {{: | ||
+ | === (A4) === | ||
- | ==== Beschreibung ==== | + | Landkarten lassen sich immer mit vier Farben einfärben. Bestimme die Anzahl der möglichen Färbungen (ohne Beachtung der Regel, dass Nachbarländer nicht die gleiche Farbe haben dürfen) einer Landkarte aus 20 Ländern mit 4 Farben. |
+ | ++++ Lösung | | ||
+ | Es gibt 4< | ||
+ | ++++ | ||
- | Der hier beschriebene Algorithmus findet nicht die perfekte Lösung, d.h. die minimale Anzahl an Farben, aber eine gute Näherungslösung. Er arbeitet dabei nach dem Greedy-Verfahren, er wählt für ein Land die momentan am besten erscheinende Lösung. | + | ---- |
+ | {{:aufgabe.png? | ||
+ | === (A5) === | ||
- | Zunächst wird eine Reihenfolge festgelegt, in der die Farben verwendet werden sollen. | + | Für das Kartenfärbeproblem ist kein Algorithmus bekannt, der eine optimale Lösung bestimmt, ohne dabei alle Möglichkeiten auszuprobieren. Begründe |
- | + | ===== Algorithmus ===== | |
- | z.B. Rot - Blau - Grün - Gelb - Lila - Orange - Braun (es müssen ausreichend viele Farben sein) | + | |
- | {{: | + | |
- | Dann betrachtet man der Reihe nach alle Knoten. Für jeden Knoten wird dann Folgendes gemacht: Man schaut jeden der Nachbarknoten an und merkt sich, dass seine Farbe schon verwendet wurde. Dann wählt man aus der Liste der Farben | + | |
- | z.B. Der rot umrandete Knoten ist aktuell an der Reihe. Alle Nachbarknoten werden betrachtet und ihre Farben ermittelt. | ||
- | {{ : | ||
- | Die erste noch nicht benutzte Farbe ist grün. Daher wird der Knoten grün gefärbt. | ||
==== Pseudocode ==== | ==== Pseudocode ==== |