Algorithmus gesucht

[FlorianB82]

Ich habe hier gerade ein algorithmisches Problem, und mir ist verdammt danach, als gäbe es da schon was effizentes dafür. Fällt euch dazu was ein? Ich habe gerade das Gefühl, ich erfinde das Rad ein zweites Mal, und noch dazu ineffizent.

Ausganssituation:

• Gegeben ist ein Wegnetz, beschrieben als eine Liste mit einzelnen ungerichteten Wegen (das sind ganz simple Wege, auf ihnen zweigt nichts ab oder ähnliches. Einfach nur ein Weg zwischen A und B.). Jeder Weg ist mit einer Liste annotiert, an welche Wege er direkt anschliesst.
• Gesondert von den Wegen gibt es Eingänge ins und Ausgänge aus dem Netz (d.h. von Ihnen geht es nur ins Netz hinein oder nur heraus).
• Manche der Wege sind optionale Wege, die aktiv oder inaktiv sein können. Diese sind im Gegensatz zu den anderen Wegen gerichtet.
• Zyklen kommen vor (z.B. dadurch: Wenn Weg 1 auf Weg 2 verbindet, dann gilt das auch umgekehrt).

Problemstellung:
Ausgehend von einem solchen Wegnetz, und einer Liste der gerade aktiven optionalen Wege, möchte ich nun die verbundenen maximalen Teilwegnetze ermitteln, und zwar so, dass ich für jedes Teilnetz eine Liste erhalte mit den verwendeten aktiven optionalen Verbindungen, sowie den Ein-, und Ausgängen.

[Alexander Kornrumpf]

Nach dem ich lange überlegt hab was du eigentlich meinst vermute ich du suchst das:

http://de.wikipedia.org/wiki/Algorithmu ... omponenten

Die Zusatzinformationenen, die du haben willst (Ein-/Ausgänge, optionale Kanten etc) kannst du vermutlich während der Algorithmus läuft einfach mitschleifen.

Falls es das nicht war: Kannst du dein Problem nochmal in Begriffen von Graphen erläutern?

[klickverbot]

Vor allem der Teil mit den »verbundenen maximalen Teilwegnetzen« ist mir nicht ganz klar – Tarjan's algorithm wäre auch mein Tipp gewesen.

[Jaw]

Diese Weg in Graphen Probleme sind oft ziemlich hart. Für Wegfindung ist A* sehr üblich und ich habe gelesen, dass man mit A* auch ne Menge andere Lösungen finden kann, indem man die Heuristik und die Bewertungsfunktion entsprechend angibt. Das wird aber fast immer nur eine Teiloptimale Lösung finden, nie die absolut beste.

Es gibt da n professionelles Buch in meinem Schrank das lauter Algorithmen abhandelt, auch in Graphen. http://www.cs.sunysb.edu/~algorith/majo ... /1.4.shtml Wenn du oben auf "by Problem" gehst gibt es zwei Kategorien von Graph Problemen. Vielleicht ist ein Ansatz für dich dabei.

Im Moment kann ich mir das Problem nicht gut vorstellen, ist etwas konfus. Die konkrete Aufgabe oder ein Beispiel könnte helfen. Vielleicht hast du auch längst schon was.

-JAW