STP087: Graphen von Null bis Dijkstra

<p>Nachdem wir den Begriff schon ein paar Male gestreift haben, heute ein genauerer Blick auf Graphen. Darin: informierte und uninformierte Suche sowie eine Erkundung der Dresdner Umgebung.</p><h2>Shownotes</h2><ul>
<li>
<p>oft erwähnt, aber nie systematisch eingeführt: der Begriff <strong>Graph</strong></p>
<ul>
<li><a href="de.wikipedia.org/w/index.php?title=Graph_(Grap…)&oldid=260114694">Graph</a>: eine Menge von Knoten mit Kanten dazwischen</li>
<li>z.B. Nahverkehrsnetz: Knoten = Haltestellen, Kanten = Direktverbindung zwischen zwei Haltestellen</li>
<li>z.B. soziale Medien: Knoten = Personen, Kanten = "ist befreundet/folgt"</li>
<li>anders als bei Listen (STP077) oder Maps (STP079) große Variabilität darin, was ein Graph fundamental ist
<ul>
<li>z.B. gerichtete vs. ungerichtete Graphen: Haben die Kanten eine Richtung oder nicht? (siehe Beispiele oben)</li>
</ul>
</li>
<li>häufig verwendete Unterarten von Graphen:
<ul>
<li><a href="de.wikipedia.org/w/index.php?title=Baum_(Graph…)&oldid=260160360">Baum</a>: ayzklischer ungerichteter zusammenhängender Graph (z.B. siehe STP077/STP079: zum effizienten Abspeichern von sortierten Listen bzw. Maps)</li>
<li>azyklischer gerichteter Graph (z.B. Versionsverwaltung, Familienstammbaum, Firmen-Organigramm)</li>
<li><a href="de.wikipedia.org/w/index.php?title=Planarer_Gr… Graph</a>: siehe <a href="chiark.greenend.org.uk/~sgtatham/puzzles/js/un…;
</ul>
</li>
</ul>
</li>
<li>
<p>Wie durchschreitet man einen Graphen? -> Suchalgorithmen, im allgemeinsten Fall die zwei wichtigsten "uninformierten" Suchalgorithmen</p>
<ul>
<li><a href="de.wikipedia.org/w/index.php?title=Breitensuch…;: von einem Startpunkt pro Runde alle Nachbarn von bereits besuchten Knoten besuchen</li>
<li><a href="de.wikipedia.org/w/index.php?title=Tiefensuche…;: vom Startpunkt aus immer erst einen Nachbarn besuchen und dann dort wieder einen Nachbarn; sobald keine weiteren unbesuchten Nachbarn möglich sind, Backtracking zum vorherigen Knoten, bis ein neuer unbesuchter Nachbar gefunden wird</li>
<li>sowohl Breiten- als auch Tiefensuche erzeugen beim Durchschreiten des Graphen einen Suchbaum, der ein <a href="de.wikipedia.org/w/index.php?title=Spannbaum&a…; ist (vgl. Spanning Tree bei Ethernet in STP028)</li>
<li>Abwägung: Tiefensuche ist einfacher zu implementieren und hat weniger Speicheraufwand (braucht nur eine "besucht-Markierung" und keine Kandidatenliste), <a href="xkcd.com/761/">kann aber in der Praxis problematisch sein :)</a></li>
</ul>
</li>
<li>
<p>Beobachtung: Breitensuche findet garantiert den kürzesten Pfad vom Startpunkt zu einem gewünschten Endpunkt</p>
<ul>
<li>Abwandlung für Wegfindung: <a href="de.wikipedia.org/w/index.php?title=Dijkstra-Al…;
<li>Voraussetzung: Kanten haben auch noch ein Gewicht (analog zu einer Streckenlänge)</li>
<li>Breitensuche merkt sich bei jedem Knoten den kürzesten Gesamtweg zu diesem Knoten</li>
<li>beim Auswählen des nächsten Besuchskandidaten Wahl des Knotens mit dem kürzesten Gesamtweg</li>
<li>Erweiterung zum <a href="de.wikipedia.org/w/index.php?title=A*-Algorith…; mittels Ergänzung um eine Heuristik, die beschreibt, wie nahe gefundene Knoten am Ziel sind (damit je nach Situation enorme Effizienzsteigerung möglich, siehe z.B. <a href="factorio.com/blog/post/fff-317">dieser Blogpost der Factorio-Entwickler</a>)</li>
</ul>
</li>
<li>
<p>im Gespräch erwähnt: <a href="wissenschaftspodcasts.de/wisspodcast/wisspodwe… 3: Das Haus vom Niko…hä?!? mit Geschichten aus der Mathematik</a></p>
</li>
</ul>