Schlüsseltechnologie

STP087: Graphen von Null bis Dijkstra

Listen Later

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.

Shownotes

  • oft erwähnt, aber nie systematisch eingeführt: der Begriff Graph

    • Graph: eine Menge von Knoten mit Kanten dazwischen
    • z.B. Nahverkehrsnetz: Knoten = Haltestellen, Kanten = Direktverbindung zwischen zwei Haltestellen
    • z.B. soziale Medien: Knoten = Personen, Kanten = "ist befreundet/folgt"
    • anders als bei Listen (STP077) oder Maps (STP079) große Variabilität darin, was ein Graph fundamental ist
      • z.B. gerichtete vs. ungerichtete Graphen: Haben die Kanten eine Richtung oder nicht? (siehe Beispiele oben)
      • häufig verwendete Unterarten von Graphen:
        • Baum: ayzklischer ungerichteter zusammenhängender Graph (z.B. siehe STP077/STP079: zum effizienten Abspeichern von sortierten Listen bzw. Maps)
        • azyklischer gerichteter Graph (z.B. Versionsverwaltung, Familienstammbaum, Firmen-Organigramm)
        • planarer Graph: siehe "Untangle"

        • Wie durchschreitet man einen Graphen? -> Suchalgorithmen, im allgemeinsten Fall die zwei wichtigsten "uninformierten" Suchalgorithmen

          • Breitensuche: von einem Startpunkt pro Runde alle Nachbarn von bereits besuchten Knoten besuchen
          • 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
          • sowohl Breiten- als auch Tiefensuche erzeugen beim Durchschreiten des Graphen einen Suchbaum, der ein Spannbaum ist (vgl. Spanning Tree bei Ethernet in STP028)
          • Abwägung: Tiefensuche ist einfacher zu implementieren und hat weniger Speicheraufwand (braucht nur eine "besucht-Markierung" und keine Kandidatenliste), kann aber in der Praxis problematisch sein :)

          • Beobachtung: Breitensuche findet garantiert den kürzesten Pfad vom Startpunkt zu einem gewünschten Endpunkt

            • Abwandlung für Wegfindung: Dijkstra-Algorithmus
            • Voraussetzung: Kanten haben auch noch ein Gewicht (analog zu einer Streckenlänge)
            • Breitensuche merkt sich bei jedem Knoten den kürzesten Gesamtweg zu diesem Knoten
            • beim Auswählen des nächsten Besuchskandidaten Wahl des Knotens mit dem kürzesten Gesamtweg
            • Erweiterung zum A*-Algorithmus 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. dieser Blogpost der Factorio-Entwickler)

            • im Gespräch erwähnt: #WissPodWeihnacht 3: Das Haus vom Niko…hä?!? mit Geschichten aus der Mathematik

              ...more
              View all episodesView all episodes
              Download on the App Store
              SchlüsseltechnologieBy Xyrillian Noises

              More shows like Schlüsseltechnologie

              View all
              Freak Show by Metaebene Personal Media - Tim Pritlove

              Freak Show

              9 Listeners

              Lage der Nation - der Politik-Podcast aus Berlin by Philip Banse & Ulf Buermeyer

              Lage der Nation - der Politik-Podcast aus Berlin

              241 Listeners

              Logbuch:Netzpolitik by Metaebene Personal Media - Tim Pritlove

              Logbuch:Netzpolitik

              5 Listeners