Optimale Route ?

Hallo an Alle,

ich bin auf der Suche nach einem Programm mit dessen Hilfe man eine optimale Route nach Eingabe von mehreren Adressen, welche angefahren werden müssen, ausgespuckt bekommt. Ich brauch es im Moment zumindest noch nichtmal zum Cachen, sondern beruflich. Daher wäre es wichtig, das es mit Eingabe von Adressen funktioniert und nicht nur mit Wegpunkten. Ich meine bei den Dosenfischern schonmal von soetwas gehört zu haben. Danke für Eure Tips im Voraus, wäre eine riiiiiesen Hilfe!

Was Du suchst heißt »MS Autoroute«.

Frohes Jagen

fette ware. gigabytes. werd ich gleich heute noch auf tauglichkeit testen. herzlichen dank für´s auf die sprünge helfen!

Gegebene Reihenfolge (z.B. Google Maps) oder Traveling Salesman-mäßig? (... :-o)

Robin(888)

Traveling Salesman war das erste, was wir an der Uni in der Graphentheorie gelernt haben. Kurz: Es gibt (noch) keinen schnellen Algorithmus um einen idealen Weg zu berechnen. Ob es überhaupt einen gibt, darüber streiten sich die Mathematiker.

Jetzt mag man vielleicht denken "probieren wir alle Möglichkeiten durch", leider steigen diese so schnell an, dass da sehr schnell Schluss ist. Am besten mit ein bisschen Bauchgefühl die Reihenfolge selbst festlegen.

SammysHP schrieb:

Kurz: Es gibt (noch) keinen schnellen Algorithmus um einen idealen Weg zu berechnen. Ob es überhaupt einen gibt, darüber streiten sich die Mathematiker.

Zum Vergrößern anklicken....

Wie meinst Du das?

SammysHP schrieb:

Jetzt mag man vielleicht denken "probieren wir alle Möglichkeiten durch", leider steigen diese so schnell an, dass da sehr schnell Schluss ist.

Zum Vergrößern anklicken....

Praktisch schon. Aber es ist definitiv ein Algorithmus um die Lösung zu berechnen, der in endlicher Zeit terminiert.

Zum Topic: Es gibt Näherungslösungen, aber wie schnell/genau die sind, weiß ich nicht.
Um wieviele Adressen handelt es sich denn?

Robin(888)

Die "endliche Zeit" ist das Problem, die kann nämlich ziemlich schnell für unsere Verhältnisse unendlich werden. (Wobei es bei 5 oder 10 Zielen noch kein Problem ist).

Wo hast Du denn Grapentheorie gehört?
Zunächst mal ist es Mathematiker erstmal schnurz wie lang oder groß das Universum ist.
Alles ausprobieren ist ein Lösungsalgorithmus der mit Sicherheit in endlicher Zeit die richtige Lösung hervorbringt. Da streitet kein Mathematiker darüber, ob es einen solchen Algorithmus gibt.

Und selbst darüber ob es einen "schnellen" Algorithmus gibt streitet wohl kein Mathematiker.
Das Problem ist nämlich NP-äquivalent.
Es gibt polynomielle Algorithmen für das Problem, von denen der Christofides-Heuristik wohl die besten Werte liefert (max. 50% Abweichung von der exakten Lösung).
Aber wie effizient der tatsächlich ist, weiß ich jetzt auch nicht.

Also: Wenn Mathematik, dann richtig. ;-)

@OP: Konnte Dir MS Autoroute nun helfen?
Robin(888)

Robin888 schrieb:

Das Problem ist nämlich NP-äquivalent.
Es gibt polynomielle Algorithmen für das Problem, von denen der Christofides-Heuristik wohl die besten Werte liefert (max. 50% Abweichung von der exakten Lösung).

Zum Vergrößern anklicken....

Ööööhm, wenn Du einen polynomiellen Lösungsalgorithmus für ein NP-Äquivalentes Problem hast, verrate ihn bitte nur mir!!!
Dann hättest Du gleich mal P=NP bewiesen!
Eine Heuristik ist ja nur eine Approximation (wie Du selbst schon schreibst).

Robin888 schrieb:

Alles ausprobieren ist ein Lösungsalgorithmus der mit Sicherheit in endlicher Zeit die richtige Lösung hervorbringt. Da streitet kein Mathematiker darüber, ob es einen solchen Algorithmus gibt.

Zum Vergrößern anklicken....

Auch das ist Humbug.
Zum einen muss der Suchraum zumindest abzählbar sein.
Zum anderen braucht man auch in unendlich abzählbaren Suchräumen eine geeignete Strategie, um jedes Element zu erreichen. Das "einfach alles ausprobieren" ist dann schon nicht mehr ganz so einfach (aber möglich).

Machen wir das Problem mal etwas konkreter:

Wir nehmen als Algorithmus: "Probiere alle Möglichkeiten und wähle die kürzeste."
Dieser Algorithmus ist ziemlich naiv und probiert auch völlig unsinnige Möglichkeiten. "Alle Möglichkeiten" ist demnach die Anzahl der Permutationen von Punkten, also n!. Für jede Wegberechnung braucht man eine gewisse Zeit. Der Einfachheit halber setzen wir die Zeit für die Berechnung einer Route zwischen zwei Punkten (k) proportional zu der Anzahl der Punkte. Für eine Komplette Route zwischen n Punkten sind das also (n - 1) * k.

Zusammengefasst: t = n! * (n - 1) * k

Setzen wir dort einfach mal ein paar Zahlen ein und wählen k = 1s:

t(5) = 480 s = 8 m
t(10) = 32659200 s = 378 d
t(20) = 46225138155356160000 s = 1465789515327,... y

Ich hoffe, ich habe mich nirgends verrechnet.

SPonGER schrieb:

Robin888 schrieb:

Das Problem ist nämlich NP-äquivalent.
Es gibt polynomielle Algorithmen für das Problem, von denen der Christofides-Heuristik wohl die besten Werte liefert (max. 50% Abweichung von der exakten Lösung).

Zum Vergrößern anklicken....

Ööööhm, wenn Du einen polynomiellen Lösungsalgorithmus für ein NP-Äquivalentes Problem hast, verrate ihn bitte nur mir!!!

Zum Vergrößern anklicken....

Sorry, ich meinte damit natürlich Näherungslösungen. (Wie meiner Meinung nach eigentlich aus meiner Antwort erkennen kann.)

SPonGER schrieb:

Zum einen muss der Suchraum zumindest abzählbar sein.

Zum Vergrößern anklicken....

Wieso ist n!/2 nicht abzählbar?

SPonGER schrieb:

Zum anderen braucht man auch in unendlich abzählbaren Suchräumen eine geeignete Strategie, um jedes Element zu erreichen.

Zum Vergrößern anklicken....

Wieso ist n!/2 unendlich?

SPonGER schrieb:

Das "einfach alles ausprobieren" ist dann schon nicht mehr ganz so einfach (aber möglich).

Zum Vergrößern anklicken....

Eben, darauf kommt es bei der *Existenz* eines Algorithmus doch bloß an, oder?
Und dadurch, dass eben *keine* unendlich vielen Fälle zu untersuchen sind, wird das Problem nur "leichter".

Robin(888)

SammysHP schrieb:

t(20) = 46225138155356160000 s = 1465789515327,... y
Ich hoffe, ich habe mich nirgends verrechnet.

Zum Vergrößern anklicken....

Nein, vermutlich hast Du Dich nicht verrechnet. Ich weiß nur nicht, was Du damit zeigen willst.

Dass dieser Algorithmus - harmlos ausgedrückt - nicht effizient ist, das ist wohl allen Beteiligten klar. (Mir jedenfalls ist es.)
Aber das behauptet hier auch niemand. (Ich zumindest tue es nicht.)

Aber Du stützt mit Deiner Berechnung, dass es maximal n! unterscheidbare Routen gibt, meine Behauptung dass es für jeden endlichen (gewichteten) Graphen mit n Ecken eine endliche Anzahl (nämlich n!) von Pfaden gibt.

Und eine endliche Anzahl von Werten zu vergleichen ist wiederum eine Aufgabe, die in endlichen Schritten lösbar ist.

Natürlich lässt sich zu jedem Zeitraum ziemlich schnell ein n finden für das die Lösung diesen Zeitraum überschreitet. Aber "Zeit" ist halt kein mathematischer Begriff.

Es *gibt* einen *exakten* Algorithmus, der *garantiert* in *endlicher* Zeit endet.
Nur das das Universum diese Zeit momentan noch nicht zur Verfügung stellt.

(Mit schnelleren Rechnern lässt sich auch der "kritische" Wert für n weiter in die Höhe treiben. Aber für diesen Algorithmus wird es immer ein "kritisches" n geben.)

Also vielleicht könntest Du nochmal genauer formulieren was Du eigentlich behauptest, ja?

Robin(888)

Dass das Teil in endlicher Zeit ein vernünftiges Ergebnis erzeugt, bezweifelt ja niemand (hoffe ich doch).

http://de.wikipedia.org/wiki/NP-Vollst%C3%A4ndigkeit schrieb:

NP-Vollständigkeit

[...] NP-vollständige Probleme lassen sich vermutlich nicht effizient lösen. [...]

Zum Vergrößern anklicken....

http://de.wikipedia.org/wiki/Problem_des_Handelsreisenden schrieb:

Problem des Handlungsreisenden

[...] Komplexitätstheoretisch gehört das TSP zur Klasse der NP-äquivalenten Probleme. Es wird daher sehr stark angenommen, dass die Worst-case-Laufzeit jedes deterministischen Algorithmus, der für dieses Problem stets optimale Lösungen liefert, im besten Fall exponentiell von der Anzahl der Städte abhängt. Schon für wenige Städte kann die benötigte Laufzeit eines solchen Algorithmus also unpraktikabel viel Zeit beanspruchen. [...]

Zum Vergrößern anklicken....

SammysHP schrieb:

Dass das Teil in endlicher Zeit ein vernünftiges Ergebnis erzeugt, bezweifelt ja niemand (hoffe ich doch).

Zum Vergrößern anklicken....

Das behaupte ich sogar.

Du hast hingegen die Behauptung aufgestellt, dass Mathematiker stritten, ob es einen Algorithmus für dieses Problem gibt. Das wollte ich widerlegen.

Einen endlichen Algorithmus *gibt* es und dass es keinen *effizienten* Algorithmus gibt (falls Du das gemeint haben solltest), dass nehmen Mathematiker (um den von Dir herangezogenen Wikipedia-Artikel zu zitieren "sehr stark an".
Ich glaube kaum, dass da wirklich ernsthaft drüber gestritten wird. (Klar ein paar Querulanten gibt es immer. Aber es gibt ja auch Leute die Cantors Diagonalbeweis zur Überabzählbarkeit der reellen Zahlen ablehnen.)

Robin(888)

Ich habe von all dem keine Ahnung, habe das aber so verstanden, dass es natürlich möglich ist, man aber nicht unbedingt in praktikabel erlebbarer Zeit das Ergebnis erwarten kann.

Nun hat halt hier in der Diskussion der eine den Fokus auf dem Zeitfaktor und der andere den Fokus auf dem theoretisch machbaren.
Sprich der eine sagt: "Es geht nicht!" (Und meint damit: "nicht in praktikabler Zeit")
und der andere sagt: "Es geht!" (Und meint damit, dass es überhaupt geht)

Robin888 schrieb:

SPonGER schrieb:

Zum einen muss der Suchraum zumindest abzählbar sein.

Zum Vergrößern anklicken....

Wieso ist n!/2 nicht abzählbar?

SPonGER schrieb:

Zum anderen braucht man auch in unendlich abzählbaren Suchräumen eine geeignete Strategie, um jedes Element zu erreichen.

Zum Vergrößern anklicken....

Wieso ist n!/2 unendlich?

Zum Vergrößern anklicken....

OK, für das TSP auf (endlichen) Graphen trifft natürlich beides zu.
Ich hatte die Aussage allgemeiner verstanden ...

Ist halt schon eine Frage wieviele Adressen verknüpft werden, weil es das Ziel ist sie zu besuchen bzw. wieviele Adressen miteinander verknüpft werden müssen um den kürzesten Weg zu bestimmen.
Zunächst kann man alle Verknüpfungen von einer Adresse zu anderen vernachlässigen wenn sie doppelt soweit entfernt sind wie die kürzeste Strecke zu einer zweiten Adresse, eventuell muß die Strecke als Ausschlusskriterium nicht einmal doppelt genommen werden - müsste man halt mal untersuchen, weitere Kriterien wären, das sich Strecken - wenn möglich - nicht kreuzen, keine Adresse doppelt besucht wird, es also abgesehen von Start und Ziel (Ziel kann hierbei auch der Start sein) maximal zwei Verknüpfungspfade pro Adresse gibt und natürlich auch keine "Sackgasse" (unnötiger Um-/Rückweg) entsteht. Als Beginn neben der Festlegung von Start/Ziel würde man erstmal die minimalen Strecken zwischen zwei Adressen bestimmen und verbinden, dann bleibt nicht mehr viel übrig zum probieren, bei 20zig Adressen müsste man unter normalen Umständen weniger als 100 Strecken bestimmen, einfach davon ausgehend das es selten mehr als 5 sinnvolle Möglichkeiten gibt überhaupt von einer Adresse zu einer anderen benachbarten zu kommen (Infrastruktur) und könnte das sicher auf 50 minimieren, damit ist das dann schon überschaubar und lösbar, man darf auch nicht vergessen, das die exakte optimale Lösung nicht erzwungen werden muß, eine Lösung die derer sehr nahe kommt reicht für die Praxis vollkommen aus. In der Praxis kommen weiter Einschränkungen hinzu, etwas was an einem Tag überhaupt erfahrbar ist, dann möchte man Übernachten und das natürlich auch optimal ohne großen Zeitverlust und ohne allzu tief in die Tasche greifen zu müssen, damit kommen zwar weitere mögliche Ziele (Hotel) hinzu, aber meistens sind diese doch fix, weiters werden bestimmte Ziele nur zu bestimmten Tageszeiten besucht werden können, so das auch noch die Reihenfolge der Stationen in gewissen Grenzen fix ist.