Suche passenden Suchalgorithmus

  • C#

Es gibt 9 Antworten in diesem Thema. Der letzte Beitrag () ist von ~blaze~.

    Suche passenden Suchalgorithmus

    Hallo zusammen,

    ich bin neu hier und möchte mich zunächst kurz Vorstellen: Tobias, 26, Elektrotechniker im Master.

    Das Problem mit dem ich zu euch komme begründet sich aus meiner Unwissenheit zum Thema der Suchalgorithmen. Ich habe Elektrotechnik studiert und leider nicht Informatik. Ich habe zwar C und Java gelernt aber von solchen Algorithmen lernt man da leider nichts. Für meine küftige Masterarbeit muss ich Stromleitungen auswerten und analysieren. Bevor das geschieht, müssen die Daten aufbereitet und sortiert werden (worum es hier geht).
    Ich hoffe, dass man solche Sachen bei einem Informatik-Studium (oder Ähnlichem) lernt, bzw. ihr habt ja sicher einiges an Erfahrung ^^ Achja und ich werde mir für die MA C# aneignen und meine Analyse dort programmieren.

    Meinen Recherchen nach eignen sich diverse Suchalgorithmen und ich hätte gern eine Einschätzung eurerseits ob das, was ich mir ausgedacht habe, überhaupt Sinn macht oder ob es einfachere praktikablere Lösungsansätze gibt.

    Also es geht um folgendes Problem:

    Die Daten eines Stromnetzes sind in einer Accessdatenbank abgelegt. Eine Stromleitung besteht aus vielen Abschnitten, verbunden über Knoten, jede Verknüpfung zwischen Leitung und Knoten hat eine Terminal ID. Im Anhang befindet sich ein Schemabild, wie Knoten, Terminal und Element (die Leitung) in der Datenbank abgelegt werden.
    Schaut man sich das Schema oben an, so sieht man, dass vom oberen zum unteren Knoten (von Knoten 6 nach Knoten 10) 3 "selektive Leitungen" existieren (die Leitung rechts ist eine "Stichleitung", dazu gleich mehr)
    Auf den jeweiligen selektiven Leitungen gibt es Abhänge, die irrelevant sind, wie die Leitungen 4 und 10+12.

    Meine Idee war folgende: ich nutze den Bellman Ford- Algorithmus, ausgehend von Knoten 6 und dann kenne ich die kürzeste Entfernung zum Knoten 10. Ich passe den Algorithmus so an, dass jedes Teilstück der Leitung gespeichert wird. Erkenne ich also die Kürzeste Leitung, so speichere ich mir diese ab und lösche die Leitungen der kürzesten Leitung aus der Adjanzenzmatrix und lasse den Algorithmus wiederholt laufen bis her keine Verbindung mehr findet?

    Ich habe schon ein Beispiel mit dem Bellman Ford programmiert und ich habe die kürzeste Leitung erkannt. :thumbsup: Das Speichern und löschen der Elemente dürte ja kein Problem sein. Die Frage wäre eher die Performance? Kleine Netze bestehen aus 300/400 Abschnitten. Bei großen Netzen dementsprechend mehr. Die Frage ist, ob der Algorithus geeignet ist? 300^3 multipliziert mit der Anzahl der selektiven Leitungen...!?

    Zu der Stichleitung ganz rechts: Hierbei ist es wichtig, dass der entfernteste Punkt gefunden wird. Hierzu habe ich mir bisher noch keine genaueren Gedanken gemacht, da ich mit dem ersten Thema schon sehr beschäftigt bin. Bei nur einer Stichleitung lässt sich das ja wunderbar auch über den Bellman Ford Algorithmus erkennen. Sind mehrere Vorhanden wird es wiederum tricky.

    Ganz unten befindet sich eine Grafik, wie ein Reales Ortsnetz aussehen kann, links Schematisch vereinfacht. Zu erkennen sind die unzähligen abzweigungen, die ignoriert werden müssen. ;)


    Also wiederholt die Frage: eignet sich der Bellmann Ford Algorithmus überhaupt? wäre ein anderer Algorithmus wie Dijkstra oder A Stern schneller oder einfacher? oder gibt es andere Lösungsansätze die euch spontan einfallen?

    anbei eine Excel-Datei mit dem Beispiel

    Vielen Dank schon einmal
    Grüße Tobias
    Dateien

    Hi
    also so ganz klar ist mir noch nicht, was genau du vorhast.
    Kannst du nochmal beschreiben, was exakt das gewünschte Ziel ist?
    Was hebt 4, 10, 12 von 6, 3, 5, 19, 11, bzw. 19 oder 11 alleinstehend ab? Ansonsten hätte ich gesagt, dass du nur Zyklen betrachten willst bzw. Knoten, die Nachbarn besitzen, die zugleich Teil eines Subgraphen sind, der den Nachbarn und zugleich alle miteinander verbundenen Knoten enthält, die in keinem Zyklus enthalten sind (oder so ähnlich) (ich meine damit, dass die Kanten 11 und 19 nicht Teil des Zykluses sind, der durch die Knoten 6, 10, 1, 2, usw. (aber nicht 3, 12, 14, 5, 18, usw.) gebildet wird.

    Ich denke mal, der Graph ist stets zusammenhängend und ungerichtet? Wenn du dann nicht nur von einem Knoten aus berechnen willst, sondern den kompletten Spannbaum benötigst, wären ggf. auch die Algorithmen von Kruskal oder insbesondere Prim (Vorschlagen würde ich tatsächlich die Kombination mit Fibonnaci-Heaps) ganz praktisch.

    Die Adjazenzmatrix ist ggf. eine nicht so gute geeignete Darstellung für so einen Vorgang, ggf. könnte man auch da noch etwas machen.
    Evtl. wäre auch eine graphenorientierte Datenbank anstatt der Accessdatenbank eine Überlegung wert.

    Viele Grüße
    ~blaze~

    Hi,
    danke für deine Antwort :)
    immer schwer die Mitte zu treffen zwischen zu viel und ausreichend Text :D dann also ausfürhlich

    Das gewünschte Ziel ist, die selektiven Leitungen herauszufinden. Diese stehen in der Excel im grünen Kasten, hätte ich wohl erwähnen sollen, sorry.
    Ich hatte mir ein Array einer Struktur vorgestellt (zumindest erinnere ich mich da an C im ersten Semester :-)) in dieser Struktur sind für jede selektive Leitung alle Element_IDs und Node_IDs vorhanden.
    Durch die Element IDs kann ich nachher die Leitungsdaten (Länge und Impedanz) ermitteln und über die Knoten die Rechenergebnisse der Kurzschlussstromberechnung zuordnen.

    Wenn es sonst ein Nebenprodukt wäre, dann könnte man für die zweite selektive Leitung (16+2+13+9+17) die Leitungen 4+10+12 mit entsprenden Knoten (3+12+14) in einem weiteren Array in der Struktur abspeichern, das wäre das optimum, aber nicht zwingend notwendig.

    Hintergrund ist, dass eine Auslegung der Sicherungen automatisiert erfolgen soll, welche eben über diese Leitungsimpedanzen dimensioniert wird (es kommen noch weitere Faktoren hinzu, aber die Leitung gibt den Maximalwert vor und stellt den Grundstock für alles weitere dar).
    Leitung 4 bzw 10+12 und 6+3+5+19/11 unterscheiden sich eben genau weil es um eine Absicherung geht:
    Eine Absicherung findet an der Einspeisung (Knoten 6) und am Kabelverteilerschrank (Knoten 10) statt, für jede einzelne Leitung. Also an den Termials (grün) 6,2,11,3,32,36,35. Somit muss die Leitung 6+3+5+19/11 betrachtet werden. Leitung 4 bzw 10+12 hingegen stellen nur einen Abzweig für einen Hausanschluss dar, wo keine Sicherungen eingebaut werden können.

    Derzeit liegen die Daten so vor, wie in der Excel Beispielhaft dargestellt. Einen ungerichteten Graphen kann man ja leicht erstellen. Ein gerichteter Graph wäre bei dieser Netztopologie möglich, ob man das pauschalisieren sollte weiß ich nicht. Ich denke eher nicht.

    Ich habe mir Kuskal und Prim auch angeguckt (gibt so ein wunderbares Web-Applet in der TU München) aber wie mir die helfen sollen, weiß ich nicht.

    Eine Graphen Datenbank sagt mir leider gar nichts. Aber unsere Daten liegen nunmal in Access vor. Inwiefern sich das umwandeln lässt musst du mir sagen :) Auf die Adjanzanzmatrix bin ich ja auch nur gekommen, durch den Bellmann Ford Algorithmus.

    Grüße Tobias

    tobi45f schrieb:

    immer schwer die Mitte zu treffen zwischen zu viel und ausreichend Text

    Je mehr Information, desto besser ;) Die genaue Realisierung des Programms ist meist irrelevant für die Problemstellung; was zählt ist eher die Art, wie das Problem beschaffen ist, also unter exakt welchen Bedingungen etwas bspw. als selektive Leitung zu klassifizieren ist. Das Problem bei Algorithmen ist, dass sie im Allgemeinen auf eine Familie von Problemen zugeschnitten sind und nicht das gewünschte Ergebnis liefern, wenn sie falsch angewendet werden.

    Gleich mal noch als Hinweis:
    - Es könnte auch eine Lösung über Datenbankoperationen wie Joins und Projektion geben
    - Ich habe noch nicht ganz geblickt, wie die "Bevorzugung" stattfindet, es ist keine "Richtung" zu erkennen, in die der Fluss stattfindet:
    182
    686

    Hier ist ja eigentlich keine Richtung verzeichnet, oder? Oder wird das über die Angaben in Node.Flag_Type gelöst und inwiefern?
    Die fehlende Richtung führt nämlich zum Problem, dass es pro effektiver selektiver Leitung zwei Leitungen gibt, wobei die eine exakt die gleiche ist, wie die andere, aber in die andere Richtung führt.

    Außerdem hätt' ich noch folgende Fragen:
    - Sind die Knoten 10 und 6 durch ihren Flag_Type besonders ausgezeichnet oder wie findet man jene Knoten, von denen ausgegangen werden soll? Wie findet man die Knoten, zu denen eine Verbindung durchgeführt werden soll?
    - Es sollen alle Leitungen von bspw. 6 nach 10 ausgegeben werden, oder?
    - Was genau ist dann eigentlich mit sel.Leitung 4? Die führt ja nicht zu Knoten 10

    Mal zur Struktur:
    Ich würde die Knoten direkt als Klasse Node modellieren. Du hast im Prinzip einen kantengewichteten Graphen, oder? Die Gewichte sind durch die Einträge der Line-Tabelle dargestellt und wohl für die kürzesten Pfade relevant. Diese Einträge würde ich also ebenfalls abfragen und in eine Struktur Line überführen.
    Wie hast du den Graphen realisiert?

    Viele Grüße
    ~blaze~

    Im Sticky steht man soll nicht so viel schreiben, das würde die Leute abschrecken :D

    Dass keine Richtung vorhanden ist, ist eben auch Teil meines Problems. Ich wäre nur in der Lage, einen ungerichteten Graphen zu erstellen (Zumindest fällt mir keine Möglichkeit ein, eine Richtung vorzugeben). Allerdings sind durch den Node.Flag_type Anfang und Ende bekannt. Eine selektive Leitung befindet sich (sofern kein Stich, ganz rechts) immer zwischen Flag_Type 4 und 5, oder 5 und 5 (4 und 4 kommt nicht vor, btw)
    Auch wenn ich die doppelte Anzahl an selektiven Leitungen hätte wäre das ja in Ordnung. Ich nehme an, einen Vergleich über die Inhalte könnte problemlos die überschüssigen Elemente filtern...?

    Genau, die Knoten 6 und 10 sind besonders.
    Zum Verständnis: Flag Type 4: de.wikipedia.org/wiki/Transformatorenstation (hier wird der Strom von 20 kV auf 1kV transformiert, abgesichert und verteilt)
    Flag Type 5: mylius-innovation.de/mediapool…ig_14865518_0_250-333.JPG (sehr ihr an jeder Straßenecke, dort kann geschaltet und abgesichert werden)
    Flag Type 1: de.wikipedia.org/wiki/Muffe (bei 2 Kabeln, Verlängerung oder durch eine Störung, Austausch eines Teiles)
    gt-gmbh.com/wp-content/uploads…sharz-abzweigmuffe-t2.jpg (bei 3 Kabeln z.B. Hausanschluss wie bei euch vor der Tür)

    Mein Gedanke war der, von Knoten 6 zu Knoten 10 so oft zu suchen und die Verbindung zu bestimmen, bis keine Verbindung mehr existiert.
    Ja, von 6 nach 10 brauche ich 3 verschiedene selektive Leitungen. Gucke ich von Knoten 6 aus in alle Richtungen, dann brauche ich am Ende 4 selektive Leitungen.
    (Es ist auch möglich, dass mehrere Knoten des Type 5 existieren, siehe in der Excel unten das Beispiel)
    Selektive Leitung 4: möglich wäre es doch, wenn man bereits sel.Leitung 1-3 hat, entfernt man diese aus den Daten und man würde den Algorithmus laufen lassen, dann würde er ja den entferntesten Punkt zu jeder Verbindung finden. Der Entfernteste Punkt ist dann der, den ich betrachten würde. Logischerweise kann der ja nur noch auf der sel.Leitung 4 liegen.

    Was ich als Klasse erstelle, ist noch nicht sicher. Dachte mir bisher, dass nur meine selektiven Leitungen eine Klasse sind? Würde es Sinn machen, ggf. auch die signifikanten Knoten wie Flag Type 4&5 als Klasse zu erstellen?


    Seit meinem vorhigen Post habe ich viel zu tun gehabt und mir auch hin und wieder andere Sachen durch den Kopf gehen lassen.
    Also eine Zwischenfrage: wie performant und erfolgsversprechend wäre eine Rekursion?
    Über meinen Startknoten 6 bekomme ich ganz einfach die Leitungen 8, 16, 18 und 6 heraus. Angenommen ich würde die Rekursion so bauen, dass ich sage, er soll von seinem Standpunkt aus über seine Knoten benachbarte Leitungen finden. Ist der Knoten Flag Type 1, dann darf er weiter, bei 4 und 5 wäre Ende, war er dort bereits, wird das Ziel ausgeschlossen, findet er nichts mehr, ist er fertig.

    Beispiel Leitung 16:
    eine Richtung führt über Knoten 6 zu den anderen drei Leitungen, die er aber aufgrund des Flag Types nicht erreicht -> Abbruch
    die zweite Richtung führt ihn über Knoten 4 zur Leitung 2.
    Erneuter Aufruf der Funktion von Leitung 2 aus. Zurück kann er nicht, nach vorn findet er Knoten 13 und Leitung 4 und 13. In Richtung 4 geht es danach nicht weiter, also Abbruch also gehts danach bei der 13 weiter etc etc bis er am Ende mit Leitung 17 auf seine letzte Begrenzung trifft und dann alle Leitungen der Strecke hat.
    Sprich ich hätte folgende Leitungen in der Reihenfolge: 16,2,13,10,12,9,17,4 (je nach dem welche Strecke die Rekursion zuerst abarbeitet)

    Ja, hier sind jetzt alle Hausanschlüsse (4,10,12) enthalten. Nun habe ich jedoch eine verminderte Anzahl an Knoten und ich kann den Bellmann Ford Algorithmus 1x laufen lassen und bekomme ein Ergebnis. Wenn ich den Algorithmus über wenig Daten laufen lasse, ist das vermutlich schoneinmal um ein vielfaches schneller. Der Bellmann Ford Algorithmus hat schließlich 3 Schleifen über die gesamte Anzahl der Knoten. Bei 1000 Knoten kommt da einiges zusammen. Hat man dann 5 Leitungen mit je 200 Knoten, sieht das ganze schon vermutlich besser aus als 5x 1000^3 :)

    Also in meinem Kopf macht das Sinn =)
    Grüße Tobias

    Ich frage mich gerade, ob es nicht auch die Möglichkeit gäbe, über eine rekursive Query dieses Verhalten zu erzeugen. Aber irgendwie bezweifle ich, dass das in Access möglich ist... Das wäre dann ggf. sogar recht performant. Ansonsten hilft wohl nichts, als die Rekonstruktion des Graphen.
    Zur Modellierung als Klasse: Ich würde die selektiven Leitungen als allgemeine Klasse Path modellieren und diese dann über eine (private) Liste von Edges oder Nodes darstellen (je nachdem, ob die Kanten Information enthalten), die die Daten readonly aufzeigt.

    Bei Rekursion ergibt sich das Problem, dass du nicht beliebig viele Rekursionsschritte durchführen kannst. Es kann also sein, dass nach ein paar hundert bis tausend Rekursionsschritten ein sog. stack overflow auftritt. Allerdings lässt sich auch jedes rekursive Programm als iteratives Programm schreiben (ggf. anhand der Verwendung der Stack<T>-Klasse, die ihre Daten im Heap ablegt).

    Ich überleg' mir mal was. Für einen Startknoten ist es einfach. Einfach ausgehend vom Startknoten sukzessiv alle Nachbarn absuchen, ob es sich um einen Endknoten handelt (Pfad in einem Stack behalten. Kreise kann man so eliminieren, dass man überprüft, ob der Knoten bereits angelaufen wurde (wenn man das mit den Nachbarn wie beim Dijkstra-Algorithmus macht, erhält man eben auch den kürzesten Pfad zu allen Endknoten. Man würde einfach die Abbruchsbedingung so setzen, dass sie erst beim vollständigen Besuchen aller Endknoten oder, wenn man an diese nicht effizient kommt, auf das vollständige Besuchen des Graphen zurückführen)

    Jetzt hätte ich für die Entwicklung des Algos noch ein paar Fragen:
    1. Die Start- oder Endknoten (oder beide) sind nicht explizit bekannt, oder? Die müsste man erst bestimmen?
    2. Gibt es mehr als einen Start- und Endknoten?
    3. Können Start- und Endknoten zusammenfallen, d.h. Startknoten = Endknoten?
    4. Wenn man über ineffiziente Umwege auch von einem Startknoten zu einem Endknoten kommen kann, sollen die wegfallen? Also bspw. man hat die Pfade (a, d) und (a, b, c, d), wobei (a, d) "kürzer" ist als (a, b, c, d)
    5. Soll angenommen werden, dass es sich beim Graphen um eine Zusammenhangskomponente handelt? Bitte sag' ja. :P
    6. Soll angenommen werden, dass es sich um einen Grpahen mit gerichteten Kanten handelt oder ungerichtete?
    7. Was passiert, wenn es zwei Startknoten-Endknoten-Paare gibt, die sich in einem Netz befinden? Wird dann der effizientere Pfad gewählt?

    Und eine Frage, die du dir stellen musst:
    8. Iterativ oder rekursiv?

    Gleich mal vorweg Anmerkungen, wie das den Algorithmus beeinflusst, wenn ich mal kurz drüber nachdenke:
    zu 1. Wenn nein, müsste man den Graphen von einem beliebigen Knoten beginnen. D.h. man würde das gleiche machen, nur den Pfad vom ersten zum letzten Knoten umkehren und am als erstes besuchten Knoten mit der Suche fortfahren.
    zu 2. Wenn's nur jeweils einen gibt, genügt es, diese zu finden und alle Pfade abzulaufen. Gibt es nur einen Startknoten, aber mehrere Endknoten müssen weniger Dinge beachtet werden.
    zu 3. Ist simpel: Die Abfrage, ob es sich um einen Endknoten handelt, wird nach vorn verschoben
    zu 4. Man müsste sich wohl die bisher von a nach d gefundenen Wege merken und bei einem effizienteren Pfad entfernen
    zu 5. Wenn nein, muss man alle besuchten Knoten aus einer Liste aller Knoten entnehmen und dann den Algorithmus solange wiederholen, bis kein Knoten mehr in dieser Liste ist.
    zu 6. Da funktioniert Schritt 1 nicht so, wie ich es beschrieben habe. Man müsste wohl erst die Startknoten finden
    zu 7. Tja, da müsste ich mir erst Gedanken zu machen. Wenn die letztere Frage mit ja beantwortet wird, würde das ähnlich funktionieren, wie 4. mit beliebigem a.
    zu 8. Ich empfehle Iterativ, wenn unbekannt ist, welche Ausmaße das System nehmen kann (wobei es dann schlecht sein kann, alles auf einmal im Speicher zu haben), der Einfachheit halber ist rekursiv aber implementationstechnisch zu empfehlen. Es gibt teilweise geschickte Transformationen, da beschäftige ich mich aber erst damit, wenn es dazu kommt (einfachste Lösung: Einfach als Stack<S> mit einer Struktur S, die alle Parameter enthält, ablegen)

    Fehlerfreiheit garantiere ich dir vorweg aber schon mal nicht. ;)

    Die den Algorithmen zugrundeliegenden Prinzipien sind häufig recht simpel: Wenn du willst, dass möglichst kurze Pfade gesucht werden, laufe in jedem Schritt den Knoten an, der die kürzeste Gesamtdistanz besitzt. Bei ungerichteten Kanten {a, b} gilt, dass d(a, b) = d(b, a), bei gerichteten i.a. Kanten nicht.
    Ich stelle mir im Moment das Problem mehrere unbekannte Startknoten zu mehreren unbekannten Endknoten recht schwierig (im Sinne von ineffizient) vor, aber vielleicht hilft es, wenn ich mir das mal aufmale. Aber sag' mir davor mal bescheid.

    Viele Grüße
    ~blaze~

    Hi,
    danke erst einmal, dass du mir so viel hilft :)

    Ich habe Rücksprache mit einem Kollegen gehalten, also mehrere Tausend Schritte werden es wohl nicht. Wenn ich mir das Durchschnitssnetz angucke, dann besteht eine selektive Leitung aus grob 50-100 Teilabschnitten, selten mal mehr. Von daher sollte das mit dem Stack Overflow hoffentlich nicht passieren.

    Zu deinen Fragen:
    1(&2). Die Start und Endknoten sind "bekannt" alle Knoten mit FlagType = 4 oder 5 sind die Startknoten. Über eine einfache Abfrage kann ich diese ja bestimmen. Welcher von beiden natürlich Start- und welcher Endknoten ist, ist nur bedingt bekannt. FlagType 4 ist immer nur ein Mal vorhanden, 5 kann mehrfach vorhanden sein. Sprich alle Leitungen zwischen FlagType 4 und jedem FlagType 5er Knoten, würden den 4er als Startknoten und 5er als Endknoten haben. Allerdings können auch Leitungen zwischen zwei 4er Knoten existieren (in meinem Beispiel jetzt nicht graphisch zu erkennen), hierbei wäre die Richtung also Zufall.

    2. Es kann Netze geben, mit nur einem FlagType 4 Knoten. Das ist aber eher selten. Normalerweise gibts mehrere Knoten.

    3. Nein, sowas ist nicht möglich.

    4. Je nach dem wie du es meinst, das ist jetzt wahrscheinlich recht verwirrend und doof zu beschreiben.. eehm.. zwischen zwei Knoten mit FlagType 4/5 gibt es immer ineffiziente Wege, wie auch in meinem Excelblatt, dort sind ja 3 Wege zwischen den zwei Knoten, von denen einer ja der effizienteste sein muss.
    Wenn deine Frage darauf abzielt, ob eine selektive Leitung eine ineffizienz wie - stell dir eine Verbindung zwischen Knoten 3 und Knoten 14 vor in meinem Beispiel - dann nein, sowas gibt es nicht.

    5. Da ich mir die Bedeutung von "Zusammenhangskomponente" grade erst einmal aneignen musste :) - so wie ich es verstehe, ja. Eine Leitung kann immer nur zwischen 2 Knoten exisitieren. Fehlt z.B. der letzte Knoten, so fehlt auch die Leitung.

    6. ich denke ungerichtet. Wie in 1 beschrieben, ist die Richtung schwer zu bestimmen.

    7. Verstehe die Frage ich leider nicht?!

    8. Wie gesagt, die Ausmaße des einer Leitung begrenzt sich auf, wenns schlecht läuft, 150-200 Elemente.


    Vielen Dank! Meine nächste Nachricht wird etwas dauern, da ich ab Samstag 2 Wochen im Urlaub bin :)
    Grüße Tobias

    Hm, also 1(&2) hab' ich noch nicht ganz geblickt. Kann es mehr als einen Startknoten geben?
    Darauf bezieht sich dann auch die 5. und die 7.
    5. Ggf. wäre es sinnvoller gewesen, es anders zu formulieren: Ist der Graph zusammenhängend, d.h. jeder Punkt des Graphen ist von einem der anderen Punkte erreichbar? Was mir gerade noch kommt: Ist jeder Punkt von jedem Punkt erreichbar? Bei gerichteten Pfaden wäre das nicht zwangsläufig der Fall (bzw. genau dann nicht der Fall, wenn es keinen Zyklus im Graphen gibt, wenn ich da nichts übersehe).
    7. Stelle dir vor, du teilst den Graphen so auf, dass alle von einem Startknoten Si aus möglichen Pfade, die in einem Endknoten enden zu einem Graphen Gi(Vi, Ei) zusammengefasst werden. Bei einem einzigen Startknoten ist das nicht das Problem, aber bei mehr als einem schon:
    Was passiert, wenn sich zwei Graphen überschneiden? Sprich Ei enthält eine Kante, die auch in Ej enthalten ist.
    Ein nicht-repräsentatives Beispiel:

    Orange und Lila überlappen sich nicht unter der Bedingung, dass nur Wege betrachtet werden, d.h. dass keine Wiederholungen innerhalb eines Pfades auftreten dürfen (z.B. (x0, x1, x0, x2) wäre kein Weg, da x0 zweimal besucht wird). Selbst diese Bedingung ist nicht zwangsläufig wahr.
    Für die roten Kanten gilt es eine Regel festzulegen: Was passiert bei so einer Überlappung?

    Jetzt noch eine unbequeme Frage: Ist das dein Masterarbeitsthema? Wenn ja, darf ich dir zwar Hilfestellung geben, aber nicht die Arbeit für dich machen. Es wäre ein Plagiat, würde ich nicht zitiert und vermutlich wird es nicht anerkannt, wenn jemand anderes die Arbeit für dich macht. Außerdem müsstest du vermutlich Quellen zitieren oder belegen, dass das, was du machst, das tut, was verlangt ist.
    Falls ja, kann ich dir schon sagen, wie ich's machen würde und worauf's ankommt, aber die Arbeit, den Algorithmus zu realisieren, die Beweise, dass er das tut, was er soll, usw., bleibt an dir hängen. Auf jeden Fall solltest du ganz genau wissen, was du tust. Es gibt viele allgemeingültige Algorithmen, die ein Problem möglichst allgemein lösen können, aber Probleme lassen sich im Allgemeinen weiter vereinfachen, sodass die Algorithmen noch effizienter werden.
    Was außerdem noch an Nebeninformation wichtig ist:
    - Was ist verlangt? Ist ein effizenter Algorithmus gewünscht? Wenn ja, dann wäre es durchaus auch praktisch, einen groben Überblick über effiziente Algorithmen/Datenstrukturen zu haben, bzw. zu wissen, wie man die Effizienz eines Algorithmus bestimmt
    - Welche Vorassetzungen können als gegeben angenommen werden? Da helfen dir die Regeln 1 bis 7 schon mal weiter. Was für Fälle muss der Algorithmus also schaffen, welche fallen weg?

    Viele Grüße
    ~blaze~

    Zu den Startknoten:

    zwangsläufig muss ich ja alle Knoten vom Flagtype 4 oder 5 als Start- und Endknoten betrachten, wenn ich die Leitungen eben zwischen all diesen Punkten ermitteln will, oder etwa nicht?
    ich habe in der Exceldatei ja weiter unten ein Beispiel gebracht, von einem realen Netz. Links ist davon das Schema aufgezeichnet. Ich habe einen Knoten ganz oben (schwarz, FlagType 4) und zwei darunterliegende in rot (FlagType 5).
    Wenn ich doch zwischen Schwarz und dem ersten Roten suche, wäre schwarz mein Startknoten und rot1 mein Endknoten. Im zweiten Durchlauf wäre wieder schwarz mein Startknoten und rot2 mein Endknoten.

    Nun kann es sein, dass nach einem roten, noch ein weiterer roter nachgelagert ist. Z.B. wenn an Leitung 6&7&8 einen gemeinsamen Knoten auch von Flagtype 4 hat. Dann wäre der vorherige Endknoten rot1 nun der neue Startknoten und rot 3 der neue Endknoten..?!
    Habe das Bild ergänzt und angehängt.

    Ja, der Graph ist zusammenhängend, jeder Punkt hat über irgendeinen Pfad eine Verbindung zu jedem anderen Punkt.
    Wie gesagt, die Daten liegen wie dargestellt vor. Ich habe die Zusammenhänge über die Knoten und Elemente und weiß, was mit wem verbunden ist, ohne Richtung oder irgendwas derartes.

    Dein nicht repräsentatives Beispiel ist im Stromnetz nicht existent :)
    Bzw, Einschränkung, bei den Netzen unserer Firma zumindest nicht. Ob andere Unternehmen sowas machen, weiß ich nicht. Problem: ein solches "Maschennetz" ist kaum/gar nicht abzusichern, da die Stromflüsse nicht kontrollierbar und schwer nachvollziehbar sind.

    Das Thema der Masterarbeit wäre, eine Absicherung zu automatisieren. Also ist dies nur die reine Vorarbeit und Datenaufbereitung und hat nichts mit dem fachlichen eigentlichen Teil zu tun. Wenn ich es schaffe, alle selektiven Leitungen zu erstellen in einem beliebigen Netz, dann kann ich weitergucken wie ich damit weiter verfahre, welche Berechnungen ich anstelle etc.

    Bisher verlangt noch niemand irgendetwas. Meine Motivation ist es, ein allgemeingültiges, effizientes Programm zu schreiben. Da noch viele Berechnungen (auch übergreifend in anderen Netzberechnungsprogrammen) später für die eigentliche Berechnung folgen werden, ist es mein Ziel, am Anfang nicht gleich zu schlampen und Algorithmen zu wählen die per se langsam sind. Da die Masterarbeit eine elektrotechnische ist und die Programmierung nur Mittel zum Zweck denke ich, dass der Prof, der kein Plan davon hat, nicht interessiert daran ist, ob ein Algorithmus effizient ist oder nicht. Viel mehr sind es später die Mitarbeiter und Anwender, die keine 5min auf die Berechnung warten wollen :)

    So ich melde mich dann nach meinem Urlaub wieder :)
    Danke dir!
    Grüße Tobias
    Bilder

    • schema.png

      16,11 kB, 470×334, 111 mal angesehen

    Ich hab' leider im Moment einfach keine Kapazitäten über für das Problem.
    Daher erkläre ich einfach mal den Schnelldurchgang:

    Der Fall, dass mehrere Startknoten existieren, wird nicht behandelt, dafür fehlt mir die Information darüber, was bei Kollisionen passieren soll, hab' nicht ganz verstanden, was das von dir Geschriebene bedeutet. ;) Ggf. genügt dir das aber auch als Information und du kannst das Verhalten selbst einbauen.

    Graph:
    - Definiere die Klassen Graph<TVertex, TEdge> (bitte benennen), Vertex<TVertex> und Edge<TEdge>. Edge und Vertex deklarieren eine TEdge Weight- bzw. TVertex Value-Eigenschaft. Stelle außerdem sicher, dass überprüft werden kann, ob ein Vertex/Edge zu einem bestimmten Graphen gehört.
    - Beim Hinzufügen von Knoten überprüfst du, ob diese Start- bzw. Endknoten sind und fügst sie entsprechend einer weiteren Liste hinzu oder fügst sie in eine Variablen ein (je nachdem, ob mehrere unterstützt werden oder nicht, frag' ab, ob die Variable vorher null war!)

    Algorithmus:
    Gehe beim Algorithmus einfach so vor, wie beim Dijkstra-Algorithmus auch.
    Markiere für jeden Knoten, ob er bereits besucht wurde, oder nicht (Dictionary<Vertex<TVertex>, bool> oder ähnlich arbeitendes). Starte bei einem Startknoten und besuche sukzessive alle Nachbarn eines Knoten, die noch nicht besucht wurden in aufsteigendem Gesamtgewicht des bisherigen Wegs. Vermerke zudem jedes mal den Weg, der zu einem bestimmten Ziel genommen wurde. Wird ein Endknoten erreicht, wird der Weg dorthin einer Liste hinzugefügt.

    Der Algorithmus sollte sowohl für gerichtete, als auch ungerichtete Kanten klappen. Ein iteratives Verfahren lässt sich über Stack<T> bzw. indem du eine priority queue verwendest (ich hab' da was von Fibonacci-Heaps im Kopf).

    Was du beim Algorithmus erhältst, sind alle Wege ohne Umwege von einem Startknoten.

    Viele Grüße
    ~blaze~

Facebook