Sie sind aktuell nicht angemeldet.

Funktionen: Einloggen  |  Neu registrieren  |  Suchen

Re: Grosse Mengen an Daten schnell vearbeiten
Autor: Snof
Datum: 19.04.09 14:44
> Ist das nun die absoulut optimale Tour? Wahrscheinlich ja. Sicher? Nein. Aber selbst wenn nicht, wird sie nur gering vom Optimum abweichen. Das Problem dabei ist, dass ich keinen Algorithmus für ein minimales Matching gefunden habe. Um mit einem Pfad jede Kannte des Graphen genau ein Mal abzufahren, müssen zu jedem Knoten genau so viele Kanten hinführen, wie von ihm weg führen. Ist dies nicht der Fall, muss man den Graphen um ein paar Kanten erweitern. Es gibt genau so viele Knoten mit zu wenig wegführenden Kanten, wie Knoten mit zu wenig hinführenden Kanten (eigentlich ist die Anzahl der Kanten gleich, aber wenn man Knoten, bei denen mehr als eine Kante "fehlt" mehrfach zählt, ist auch die Anzahl der Knoten gleich). Es ist also relativ einfach eine Kombination zwischen den Knoten zu finden. Das nennt man dann Matching. Komplizierter ist es, ein Minimales zu finden. Einfach durchprobieren ist dabei eine äußerst schlechte Idee. Für n benötigte Kanten gibt es n! mögliche Matchings. Das wird sehr schnell sehr viel. Ich habe deshalb eine Heuristik implementiert. Böse Zungen würden behaupten ich rate Aus den n² möglichen Kanten suche ich mir einfach die Kürzeste raus, da diese vermutlich auch zum minimalem Matching gehören würde. Danach sind es nur noch (n-1)² mögliche Kanten, bei denen ich wieder so vorgehe. Es ist also nicht garantiert, dass das Ergebniss immer optimal ist. Für deine Strecke ist es aber optimal. Die möglichen Matchings hab ich alle (ja, alle 6 ) mal durchgerechnett. PS: Studieren tue ich in Rostock.

Grosse Mengen an Daten schnell vearbeiten	1.465	vista08	15.04.09 16:55
Re: Grosse Mengen an Daten schnell vearbeiten	911	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	904	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