Sie sind aktuell nicht angemeldet.

Funktionen: Einloggen  |  Neu registrieren  |  Suchen

Re: Grosse Mengen an Daten schnell vearbeiten
Autor: Snof
Datum: 18.04.09 21:39
So, hier schon mal der Code. Erklärung kommt morgen Nagut, ne kurze Erklärung: Als Vorbereitung lass ich einmal FloydWarshal über den gesammten Graphen laufen, um die kürzesten Wege zu ermitteln. Djikstra wär vermutlich schneller, aber hatt ich jetzt keine Lust zu implementieren. Hauptsächlich wird nur der rote Teil des Graphen betrachtet. Der Schwarze dient nur zum "füllen". Aus dem Roten wird Versucht ein Eulergraph zu machen. Falls das nicht klappt, werden ein paar Kanten hinzugefügt (deshalb die kürzesten Wege). Die Wahl, wie ich die Kanten einfüge, ist nur heuristisch, da ich kein Minimal-Matching-Algorithmus gefunden habe und Max.-Matching alle nur für positive Kantengewichte funktionierten. Als nächstes wird ein Euler-Pfad gesucht, also ein Pfad über alle Kanten. Grundlage dafür ist der Algorithmus von Hierholzer. Gesammtkomplexität ist O(|V|³). Grund dafür ist FloydWarshal. Mit Djikstra wäre O(|V|²) möglich, wenn nur wenige zusätzliche Kanten nötig sind. Naja, viel Spaß damit und probiers ruhig mit nem größeren Graphen aus, wenn du einen hast Code gibts hier, is leider etwas groß fürs Forum: code.txt

Grosse Mengen an Daten schnell vearbeiten	1.465	vista08	15.04.09 16:55
Re: Grosse Mengen an Daten schnell vearbeiten	912	vista08	15.04.09 17:17
Re: Grosse Mengen an Daten schnell vearbeiten	818	Maas	15.04.09 17:19
Re: Grosse Mengen an Daten schnell vearbeiten	890	DaveS	16.04.09 08:42
Re: Grosse Mengen an Daten schnell vearbeiten	884	Snof	15.04.09 17:23
Re: Grosse Mengen an Daten schnell vearbeiten	842	vista08	16.04.09 07:11
Re: Grosse Mengen an Daten schnell vearbeiten	925	DaveS	16.04.09 08:42
Re: Grosse Mengen an Daten schnell vearbeiten	836	vista08	16.04.09 17:57
Re: Grosse Mengen an Daten schnell vearbeiten	922	Snof	16.04.09 20:12
Re: Grosse Mengen an Daten schnell vearbeiten	776	vista08	16.04.09 20:51
Re: Grosse Mengen an Daten schnell vearbeiten	905	Snof	18.04.09 21:39
Re: Grosse Mengen an Daten schnell vearbeiten	845	DaveS	19.04.09 09:51
Re: Grosse Mengen an Daten schnell vearbeiten	834	Snof	19.04.09 10:00
Re: Grosse Mengen an Daten schnell vearbeiten	816	vista08	19.04.09 12:45
Re: Grosse Mengen an Daten schnell vearbeiten	959	Snof	19.04.09 14:44
Re: Grosse Mengen an Daten schnell vearbeiten	757	vista08	20.04.09 22:18
Re: Grosse Mengen an Daten schnell vearbeiten	875	Snof	20.04.09 23:11

Sie sind nicht angemeldet! Um auf diesen Beitrag zu antworten oder neue Beiträge schreiben zu können, müssen Sie sich zunächst anmelden. Einloggen  |  Neu registrieren

Funktionen:  Zum Thema  |  Gesamtübersicht

Suchen