Parallele Systeme
Graphanalyse: Maximale Konfigurationen
| Beginn: Ab sofort. AnsprechpartnerIn: Eike.Best Voraussetzungen: Keine besonderen Vorkenntnisse erforderlich. Kurzbeschreibung: In dieser Arbeit soll ein effizienter Algorithmus für die Suche nach bestimmten Pfaden in Graphen entwickelt und implementiert werden. |
Beschreibung
Ziel dieses Projekts ist die effiziente Implementierung der Suche nach
maximalen Konfigurationen in gerichteten endlichen azyklischen Graphen.
Maximale Konfigurationen stellen einen bestimmten Abschluss von Graphelementen
nach oben und unten dar. Letztlich möchte man die Menge aller
möglichen Kombinationen von Pfaden, beginnend an den Wurzeln, die an
Kreuzungen genau eine Möglichkeit wählen, genau dann wenn alle
eingehenden Pfade gewählt wurden.
Die einfachste Herangehensweise ist die erschöpfende Suche in allen
Kombinationen. Unter Berücksichtigung der Randbedingungen der Graphen
sollten aber auch effizientere Algorithmen möglich sein.
Das Tool soll in C oder C++ erstellt werden, weitere Kenntnisse sind nicht erforderlich. Wer Petrinetze kennt, kann sich für das beschriebene Problem auch eine Darstellung als Petrinetzproblem holen, da werden die Bedingungen u.U. noch etwas klarer...