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

Inhaber
TYPO3 Senior Developer
Content Gott (1772 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

Inhaber
TYPO3 Senior Developer
Content Gott (1772 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