Komplexe Algorithmen implementieren

[Guest]

Hallo an alle,

ich habe schon öfter kleinere Fragen in diesem Forum gestellt und war immer begeistert von der Lebendigkeit dieses Forums. Darum wende ich mich auch diesmal an euch, in der Hoffnung, dass mir jemand vielleicht ein paar Impulse, Ideen oder sonst was geben kann.

Und zwar habe ich etwa 3 bis 4 Monate Zeit, und muss in dieser Zeit 3 oder 4 teilweise sehr komplexe
Algorithmen implementieren. In Java habe ich mich ein bisschen eingearbeitet und benutze Eclipse. Diese Algorithmen, die ich nun zu bearbeiten habe, sind alle Algorithmen auf Graphen. Es geht dabei darum auf so genannten Spielgraphen für unendliche Spiele Gewinnregionen für den einen, sowie für den anderen Spieler zu finden, und zusätzlich die "perfekten" Strategien für beide Spieler. Da solche Spiele determiniert sind, also jeder Knoten eindeutig als Gewinnknoten für den einen oder anderen Spieler gewertet werden soll, sind diese Algorithmen zwar eindeutig aber es macht die Sache umso schwerer. Dies führt dazu, dass ich nach längerer Einarbeitungszeit nun die Algorithmen -sagen wir halbwegs- überschaue. Jedoch sind sie wirklich äußerst komplex, und leider habe ich kaum Programmiererfahrung und inzwischen auch immer weniger Hoffnung sowas zu schaffen. :-(
Meine Frage ist nun, ob mir jemand Tipps geben kann, zum Einen, wie man eine solche Sache allgemein angehen soll, zum Anderen was es da schon an fertigen Sachen gibt vielleicht, und last but not least: Soll man wirklich mit Klassendiagrammen anfangen, bzw. wie starte ich nun am besten wenn diese Algorithmen schon im Pseudocode gegeben sind??????
Ich hoffe jemand kann mir ein bisschen weiterhelfen. Ich wäre euch mehr als dankbar.

Beste Grüße,

Stephan

 

[Marco13]

Eine pauschale Antwort ist schwierig. "Ideal" wäre eine abstrake Graphen-Bibliothek. Dort könnte man für jeden Algorithmus genau die Implementierung verwenden, die dafür am besten geeignet ist. Da "Graphen an sich" nicht unbedingt so eine komplexe Klassenstruktur bedeuten (Node, Edge, Graph - und gut) bräuchte man nicht unebdingt ein Klassendiagramm. Bei einer abstrakten Basis und mehreren konkreten Implementierungen könnte das aber hilfreich sein.

Das wäre aber alles ziemlich aufwändig. Evtl. kannst du auch eine vorgefertigte Graphen-Implementierung verwenden, wo du nurnoch die Algorithmen drauf anwenden mußt? Häufig bieten solche Bibliotheken auch Funktionen an, die in "komplexen Algorithmen" gerne mal nebenbei in einer Zeile abgehandelt werden

    build the MST
    compute the maximum flow
    compute a 4-coloring
    compute the final result from the in-flow of all equally colored nodes of the MST... (danke!)

Und wenn es wirklich komplexe Algorithmen sind, wirst du derartige Funktionen mit Sicherheit brauchen! Schonmal eine Websuche gemacht, was es da für fertige Lösungen gibt?

 

[Guest]

Vielen Dank erstmal für die Antwort.
Also, ich will kurz meinen aktuellen Stand zeige. Derzeit benutze ich eine selbst gebaute Klasse Graph, in der ich quasi ArrayList aus Knoten verwalte. Diese Knoten, die auch von mir selbst gebaut sind, können dann ihren Nachfolger, ihre Vorgänger, ihre ID, ihre Farbe, etc liefern.
Die Algorithmen haben tatsächlich alle eine sehr hohe Komplexität, sodass man mit weniger eleganten Implementierungen wenigstens daran recht wenig kapuut machen kann...
Dennoch sollte das Ganze natürlich halbwegs sauber gelöst sein.
Genau wie du geschrieben hast, benutzen diese Algorithmen gerne MST oder Reach Sets eines Knoten, etc. Dies sind zwar Sachen, die ich in der Theorie kenne, aber wie man das nun letzten Endes implementiert, da hab ich doch sehr meine Probleme.
Leider finde ich einfach keine absolut passende vorgefertigte Graph Lib. mit der ich all das machen kann, was ich brauche.
Vielleicht hat noch jemand ne Idee.?
Noch kurz eine letzte Frage: DIese Algorithmen bauen ständig neue Knotenmengen aus dem Graphen mit irgendwelchen Eigenschaften. Bisher löse ic das so, dass ich jedes Mal wenn ein solch neues Set bestimmt wird einfach eine ArrayList baue mit den entsprechenden Knoten. Wie schlimm ist sowas, wenn ich eine Funktion rekursiv aufrufe, also wie speicherlastig wird sowas sein?

 

[Marco13]

Naja - eine passende Lib, die "alles" kann, ist vielleicht auch ein bißchen viel verlangt. Aber irgendeine, die die wichtigsten (am häufigsten benötigten) Operation für Graphen anbietet, müßte sich doch finden lassen!?

Zur Frage mit der ArrayList: Rekursive Aufrufe sind meistens weniger effizient als eine iterative Lösung - nur manchmal lassen sich bestimmte Sahcen damit viel einfacher und eleganter implementieren. Also im Zweifelsfall die (einfachere und) schönere Lösung nehmen. FALLS sich dann irausstellt, dass das zu langsam wird, kanst du auch iterativ arbeiten. "Große" Objekte erzeugen (d.h. ArrayLists mit vielen Knoten) ist zwar i.a. recht aufwändig, allerdings macht man das ja nicht zum Spaß - man sollte es vermeiden, wenn das ohne Verrenkungen möglich ist, aber ... manchmal ist es eben notwendig.

 

[s-markus]

Ich habe mal eine Zeit lang mit der Graphen und Algorithmen Bibliothek jGABL gearbeitet.
Kannst ja dort in der API mal nachsehen wieviele nuetzliche Sachen fuer deine Projekt dabei sind.
www.math.tu-berlin.de/jGABL/
Was heisst denn dass die Algoithmen sehr komplex sind?
Meinst du dass sie aufwendig und schwierig zu implementieren sind oder handelt es sich bei dem darunterliegenden Problem um ein sehr komplexes (also ob es zB in NPC liegt)?

Fuer wirklich aufwendige Sachen in Bezug auf die Komplexitaet des Problems wuerde ich die C++ Bibliothek Boost empfehlen.
Aber das ist halt nicht Java und teilweise auch sehr sehr kryptisch.

Viele Gruesse,

Markus