gelöschter Benutzer

Der Weg ist das Ziel

am 30.11.2010, 10:51 Uhr eröffnete folgenden Thread
PHP & MySQL    1600 mal gelesen    5 Antwort(en).

Hallo @ All,

ich steh gerade vor einem kleinen Problem, denn ich muss einen Weg berechnen.
Dabei könnte ich eure Hilfe gebrauchen.

Man kann es sich wie ein Koordinaten System vorstellen in dem viel Punkte angegeben sind (ca. 100 - 400). Nun muss ich diese Punkte miteinander verbinden über den kürzesten Weg der möglich ist. Der Startpunkt ist gleich der Endpunkt.

Wie kann ich das am besten umsetzen?

Ich hab zwar schon einen Versuch gemacht aber das Ergebnis ist noch nicht optimal.
Dabei geht es immer nur zu dem Punkt der am nächsten ist. Zu beginn geht das ganz gut aber zum Ende hin, wenn nur noch wenige Punkte da sind, ist es sehr Ineffektiv.

Ich weis auch nicht so recht nach was ich da Googln könnte.

Habt Ihr vielleicht eine Idee?


Viele Grüße Thomas


seitenreport
Avatar seitenreport
Inhaber
TYPO3 Senior Developer
Content Gott (1771 Beiträge)
am 30.11.2010, 11:01 Uhr schrieb seitenreport

Hallo Thomas,

der Dijkstra-Algorithmus sollte das sein, was Du suchst.

Gruß,
Matthias


SEO Analyse und Website-Check mit Seitenreport


gelöschter Benutzer
am 30.11.2010, 11:34 Uhr schrieb

Hallo Matthias,

danke für den Tipp aber der Dijkstra-Algorithmus hilft mir leider nicht, denn bei mir ist Startpunkt gleich Endpunkt und ich habe auch negative Kantenlängen.
Es ist aber trotzdem ein sehr interessanter Algorithmus.

Danke & Gruß Thomas


seitenreport
Avatar seitenreport
Inhaber
TYPO3 Senior Developer
Content Gott (1771 Beiträge)
am 30.11.2010, 11:41 Uhr schrieb seitenreport

Ultima schrieb:

danke für den Tipp aber der Dijkstra-Algorithmus hilft mir leider nicht, denn bei mir ist Startpunkt gleich Endpunkt und ich habe auch negative Kantenlängen.


Okay, kannst Du vll. dem Thread noch einen Screenshot / eine Skizze o.ä. anhängen? Dann wird das Problem etwas plastischer.

Danke und Gruß,
Matthias


SEO Analyse und Website-Check mit Seitenreport


gelöschter Benutzer
am 30.11.2010, 11:57 Uhr schrieb

Ja, auf deinem Tipp hin sehe ich mir gerade auch die anderen Algorithmen an.
Dabei hab ich diese Grafik gefunden.

[IMG]http://upload.wikimedia.org/wikipedia/commons/thumb/d/d6/Prim_Algorithm_0.png/200px-Prim_Algorithm_0.png[/IMG]

D = Start und Endpunkt
der Optimale Weg wäre: D, A, B, C, E, G, F, D
meine Berechnung liefert aber: D, A, B, E, C, F, G, D
Da immer zum Knoten gesprungen wird der am nächsten ist.


klaus_b
Avatar klaus_b
Er ernährt mich ;-)
Content Meister (328 Beiträge)
am 30.11.2010, 13:30 Uhr schrieb klaus_b

Der Klassiker hierfür sollte doch "traveling salesman" oder Königsberger Brückenproblem, wie er im Original heist, sein.

Servus,
Klaus


klaus_b@.NET über alles was an .NET und C# Spass macht.

  • 1


« zurück zu: PHP & MySQL

Das Seitenreport Forum hat aktuell 5267 Themen und 36090 Beiträge.
Insgesamt sind 48174 Mitglieder registriert.