Route mit 60 Stopps

[Phoenix3]

Wenn ich eine Route habe mit 60 Stops, wieviele Möglichkeiten gibt es dann, diese Stopps anzufahren?

 

[xornado]

Hi, ich glaube da brauchen wir ein paar mehr Infos, oder? Ich meine "Route" bedeutet für mich ja irgendwie, dass ich entlang einer Strecke "nacheinander" alle Stopps anfahre.

Ansonsten natürlich so: erster Stopp: 60 Möglichkeiten, dann verbleiben noch 59..58 also
60! verschieden Möglichkeiten. aber das wäre glaub ich zu simpel...

Best,
X

 

[gelle]

http://de.wikipedia.org/wiki/Abzählende_Kombinatorik#Zusammenfassung

in nehme mal an (die informationen sind ja nicht so ausführlich), dass du eine permutation ohne wiederholung der stops willst. aber der eine satz lässt da auch spielraum offen. bitte die frage besser formulieren und nen blick in wikipedia kombinatorik kann ein auch schnell selber helfen :P

 

[Phoenix3]

Eigentlich ist das schon eindeutig, denke ich, aber ich formuliere es gerne ausführlicher:

Ich möchte wissen, wie viele Möglichkeiten es gibt, von einem festen Startpunkt aus (z.B. Hamburg-Jungfernstieg 2; oder einfach A[mit den Koordinaten xxx/yyy]) 60 weitere Stopps (z.B. Berlich-Charlottenburg, Köln, Rom, Ludwigsburg, Frankfurt, Moskau, Ankara etc.) anzufahren.

Beispiel:

Bei drei Stopps, sagen wir Hamburg,Berlin,Hannover, gäbe es 6
Möglichkeiten(Startpunkt Kiel):


1. HH,Bl, Hann
2: HH,Hann,Bl
3. Bl,HH,Hann
4. BL,Hann,HH
5. Hann,BL,HH
6. Hann,HH,BL


Ist also bei 60 Stopps die richtige Antwort 60! ?

Danke für Aufklärung.

 

[gelle]

Ist also bei 60 Stopps die richtige Antwort 60! ?

Danke für Aufklärung.

dann ja

 

[Phoenix3]

Kann mal jemand das Ergebnis von 60! posten ?

Mein Rechner zeigt das nicht mehr an.



Bzw. irgendwo im Web muss es doch einen Rechner geben, der mit Zahlen von so ca. 30 Stellen arbeiten kann, oder? Werde da irgendwie nicht fündig.



Edit:
Habe das grade mal überschlagen, sind ca. 3 Decillionen Möglichkeiten bei 50 Stopps.

Wieviel Rechenzeit ist nötig, um die schnellste Route von 3 Decillionen möglichen Routen zu errechnen?
Ist das überhaupt noch möglich oder mit heutigen technichen Möglichkeiten nicht errechenbar?

 

[gelle]

http://www.wolframalpha.com/input/?i=60!

 

[xornado]

Kann mal jemand das Ergebnis von 60! posten ?


Wieviel Rechenzeit ist nötig, um die schnellste Route von 3 Decillionen möglichen Routen zu errechnen?
Ist das überhaupt noch möglich oder mit heutigen technichen Möglichkeiten nicht errechenbar?

Das was Du da jetzt fragst ist eine andere Frage: Du willst jetzt wissen, wie man bestimmte Knoten am besten (i.e. kürzesten) verbinden kann.

Und dafür gibt es Algorithmen und Heuristiken.

 

[Phoenix3]

Ich weiß, dass man sich der Lösung relativ gut über Algorithmen annäheren kann; soweit ich weiß kann man sie aber nicht definitiv errechnen d.h. alle (bei 50 Stopps) 3 Decillionen Möglichkeiten miteinander bezüglich der jeweiligen Streckenlänge zu vergleichen und dann eben die kürzeste zu erkennen.

Oder ist dies auch möglich, dass man also definitiv die kürzeste errechnen kann (mal abgesehen von eventuellen Streckenführungproblemen (Baustellen etc.)), wie es ja bei weniger Stopps auch möglich ist.

 

[gelle]

stell doch ma bitte deine fragen (von anfang an) ordentlich.

was willst du denn jetzt? ein algorithmus zum finden des kürzesten weges zwischen mehreren definierten punkten? so richtig kenne ich mich damit nicht aus, aber ich kann mich noch den
http://de.wikipedia.org/wiki/Dijkstra-Algorithmus
erinnern. gibt aber sicherlich, wenn du mal selber google und co. bemühst, noch eine vielzahl an weiteren varianten.

 

[Phoenix3]

Es ist nicht immer möglich, Fragen so zu formulieren, dass jeder damit völlig einverstanden ist.

Der Dijkstra-Algorithmus ist in etwa das, was ich suche, jedoch ist meine eigentliche Frage, ob es möglich ist, in vernünftiger Rechenzeit 60 Dezillionen Varianten, von denen jede einzelne ja schon eine gewisse Komplexität hat, durchzuführen.

Außerdem, ob der Dijkstra-Algorithmus nur einen Näherungswert bei vielen Knoten liefert oder den tatsächlich definitiv kürzesten Pfad (also auch bei 50 und mehr Knoten - und, wie zuvor gesagt, wieviel Rechenzeit dafür notwendig ist).

 

[gelle]

Es ist nicht immer möglich, Fragen so zu formulieren, dass jeder damit völlig einverstanden ist.

Es ist aber möglich Fragen besser zu formulieren als du das hier tust

Der Dijkstra-Algorithmus ist in etwa das, was ich suche, jedoch ist meine eigentliche Frage, ob es möglich ist, in vernünftiger Rechenzeit 60 Dezillionen Varianten, von denen jede einzelne ja schon eine gewisse Komplexität hat, durchzuführen.

effektiv ist es auf jeden fall nicht (außerdem ist 60! rund 10^82. das sind viel viel mehr als dezillionen. und solche zahlen schreibt man auch nicht mehr als zahlwort, sondern als zehnerpotenz gewöhntlich btw)

Außerdem, ob der Dijkstra-Algorithmus nur einen Näherungswert bei vielen Knoten liefert oder den tatsächlich definitiv kürzesten Pfad (also auch bei 50 und mehr Knoten - und, wie zuvor gesagt, wieviel Rechenzeit dafür notwendig ist).

les halt den wikipedia artikel und die weiterführenden links

 

[Phoenix3]

Das sind meine Lieblingsantworten; Motto: Finde es doch selbst heraus.
...

 

[gelle]

Das sind meine Lieblingsantworten; Motto: Finde es doch selbst heraus.
...

Ja. Ich hab dir einen Algorithmus vorgeschlagen. Wenn man sich damit überhaupt nicht auskennt, ist es vielleicht nicht ganz so einfach einen solchen sofort zu finden.

Wenn dich das interessiert, dann lies dich ein. Wenn nicht, dann lass es und heul nicht rum.

 

[Phoenix3]

Kannst du mir nicht einfach kurz auf die Frage, ob die Algorithmen Näherungswerte oder den tatsächlich kürzesten Pfad liefern (auch bei 50 und mehr Knoten), antworten ?

Wenn du dich mit dieser Materie gut auskennst, sollte eine solche Antwort nicht schwer fallen.

 

[Albstein]

Klingt nach klassischem Problem:
http://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden

Das ist NP vollständig
http://de.wikipedia.org/wiki/NP_(Komplexitätsklasse)

Kurzgefasst: Es ist nicht sicher ob es einen Algorithmus gibt das in kurzer Zeit zu berechnen, aber es wird angenommen, dass es ihn nicht gibt und wenn wirst du ihn sehr warscheinlich nicht im vorbeigehen finden. Sprich du kannst eine Lösung angeben, aber die Berechnung dauert lang.

 

[xornado]

not sure if trolling or just stupid.

Dir wurden doch alle nötigen Antworten gegeben

 

[Phoenix3]

not sure if trolling or just stupid.

Dir wurden doch alle nötigen Antworten gegeben

Wie witzig du bist - oder einfach nur dumm?

Bis jetzt hat keiner mir die Frage, die ich in meinem vorherigen Post stellte, beantwortet.

Ich sage es nochmal:
1. Näherungswert oder 100% kürzester Weg
2. Rechendauer bei 3 Dezillionen Möglichkeiten bzw. 50 Stopps in mittelkompliziertem Gebiet (d.h. Stadtverkehr)

Bitte nur Antworten, wenn diese und keine anderen Fragen beantwortet werden.
Muss ich leider dazuschreiben, da 99,987654321 % der Leute sonst
alles beantworten- außer meiner Frage.

PS: Es waren ja teilweise hilfreiche Antworten dabei, das will ich ja nicht leugnen; jedoch eben keine, die meine Frage präzise und erschöpfend beantwortet hätten und auf eine Weise, die eben das in der Frage ausgedrückte beantworteten und nicht das, von dem der Antwortende dachte, es könnte in der Frage gesteckt haben, ist leider so.

 

[Albstein]

Dein Problem ist anscheinend Traveling Salesman. Wenn es das nicht ist, dann beschreibe bitte die Unterschiede.

 

[zoiX]

Albstein hat völlig recht - alle Fragen, die du hast sollten in dem Wikipedia-Artikel zum Traveling Salesman zu Genüge beantwortet werden.
Ich geb dir noch ne Chance den Thread hier vor der Schließung zu retten, wenn du di Unterschiede zwischen deinem Problem und dem Problem des Handlungsreisenden detailliert darlegen kannst. Sollte das nicht geschehen und du trotzdem deine Fragen weiterstellen, ohne auch nur maln bisschen Recherchearbeit selbst zu übernehmen, so stirbt der Thread den Schließungstod.

 

[mfb]

2. Rechendauer bei 3 Dezillionen Möglichkeiten bzw. 50 Stopps in mittelkompliziertem Gebiet (d.h. Stadtverkehr)

Wesentlich länger als das Alter des Universums, selbst wenn du alle Computer der Erde zur Verfügung hast. Selbst wenn du die komplette Erde in einen Supercomputer umbauen könntest, würde es vermutlich noch zu lange dauern.
Außer es gibt einen Algorithmus der Komplexität P (unwahrscheinlich) - dieser würde dann aber nicht alle Möglichkeiten durchrechnen, sondern geschickter die kürzeste finden.

Die Standorte sind dabei unerheblich, lediglich die Zeit von A nach B für alle A,B muss bekannt sein (und ist vergleichsweise extrem einfach findbar).


>> Näherungswert
Dafür gibt es gute Algorithmen, die das mit 50 Stopps extrem schnell machen und sehr gute Näherungen liefern.

>> oder 100% kürzester Weg
Um den garantiert zu finden, bleibt derzeit nur das blinde Ausprobieren.

 

[Phoenix3]

Eine Antwort. Danke für eine inhaltliche Antwort, die zumindest einen Teilbereich meiner Fragen beantwortet.

 

[Btah]

Könnte man das Problem nicht dadurch berechbar machen, dass man "unsinnige" Möglichkeiten ausschließt?

Also zumindest unter der Annahme das die Punkte halbwegs gleichmäßig verteilt sind (wenn man jetzt 40 Punkte bei Berlin, 5 bei München und 5 bei Frankfurt hat oder so, funktioniert das natürlich nicht), man könnte doch zB erstmal nur von allen 50 Punkten zu den jeweils 49 anderen Punkten die Distanz berechnen, aus dem ganzen Schmu den Mittelwert nehmen und alles was über dem Mittelwert liegt rauswerfen...denn wenn ich zB vom nordöstlichsten zum südwestlichsten Punkt fahre, kommt da sicher nicht die kürzeste Route bei rum am Ende

dann hat man zwar immer noch einige Möglichkeiten, aber man muss von jedem Punkt eben nicht immer gleich 49 (bzw pro abfahrenen Knoten halt weniger) Routen ins Auge fassen

€: oder für jeden Punkt nur die 10 Punkte zulassen als Möglichkeit, die ihm am nächsten sind

 

[Albstein]

Sagmal habt ihr geraucht?

Lest den gottverdammten Artikel da steht ALLES drin, einschließlich dem was mfb da geschrieben hat.

 

[Bootdiskette]

Ich wüsste gerne in welchem Rahmen einem eine solche Aufgabe gestellt wird. Immerhin scheint sie zu sein "Löse eines der großen Probleme im Bereich Numerik/Algorithmenkram als Hausaufgabe".
Dass das Traveling-Salesman Problem nicht mal einfach so lösbar ist und der TE trotzdem recht vehement eine Lösung fordert ist dagegen sehr unterhaltsam

 

[TealC]

Sagmal habt ihr geraucht?

Lest den gottverdammten Artikel da steht ALLES drin, einschließlich dem was mfb da geschrieben hat.

Witzigerweise ist das was mfb geschrieben hat ja auch noch voellig falsch.

 

[mfb]

... was du sicher noch genauer erläutern möchtest, um zu verhindern, dass diese völlig falschen Desinformationen nicht noch weiter verbreitet werden.
Richtig?

Falls sich "völlig falsch" lediglich auf das "blinde Ausprobieren" bezieht: Sicher muss man nicht jede Möglichkeit probieren, aber viel zu viele um das mal eben so dem Computer zu geben.

 

[TealC]

Steht alles im Wiki Artikel. Ich kenne mich in dem Thema noch nicht einmal aus, sondern habe nur den Artikel gelesen. Wohlgemerkt den Englischen, es steht auch im Deutschen, aber im englischen ist es ausfuehrlicher. http://en.wikipedia.org/wiki/Travelling_salesman_problem

Aber gut, ich erklaere es Dir gerne, wenn Du es nicht selbst nachlesen moechtest.

Du behauptest es gibt nur 2 Loesungen, blindes Ausprobieren und Heuristik. Des weiteren implizierst Du, da Ausprobieren zu lange dauern wuerden, dass es nicht moeglich ist, mit den heutigen technischen Moeglichkeiten, das Traveling Salesman Problem fuer 50 Stops exakt zu loesen.

Laut Wiki gibt es jedoch zahlreiche andere Ansaetze, die den exakt kuerzesten Weg finden und sehr viel schneller sind als blindes Ausprobieren. Es werden "branch and bound", "progressive improvement algorithms" und spezialisierte Implementierungen von "branch and bound" genannt. Mit letzteren ist es Cook et al. gelungen das Problem der kuerzesten Route exakt fuer 85900 Stops zu loesen.

 

[xornado]

Tealc, du hast die zeitdimension dabei vergessen

"...taking over 136 CPU-years"

 

[TealC]

Ach, dieses kleine Detail. Damit ist es aber immer noch innerhalb der heutigen technischen Moeglichkeiten

Wenn man mal drueber nachdenkt sind 136 CPU Jahre auch gar nicht mal so viel. Das Zeug kann man ja problemlos parallelisieren. 400 Quadcores, die nen Monat rechnen und schon ist man da. So viel Computing Power kriegen wir ja sogar hier im Forum noch zusammen, wenn wirs drauf anlegen.

 

[mfb]

Ok, ich hatte den Vorfaktor für kleine Städtezahlen deutlich überschätzt.
Die Aussage mit dem Ausprobieren verstehen wir aber eindeutig unterschiedlich.

Der Wikipedia-Artikel gibt für allgemeine Städtezahlen eine Komplexität von O(2^n) an, die derzeitigen Rekorde basieren aber auf "and problem-specific cut generation", was bereits Spezialfälle (~reale Karten) oder menschliches Eingreifen impliziert.
Insbesondere: Reale Karten haben ein naheliegendes Konzept räumlicher Nähe, es gilt beispielsweise die Dreiecksungleichung.

 

[Gelöschtes Mitglied 160054]

Insbesondere: Reale Karten haben ein naheliegendes Konzept räumlicher Nähe, es gilt beispielsweise die Dreiecksungleichung.

Nicht, wenn man hierbei die zeit berücksichtigt haben will(etwa baustelle auf strecke a nach b, welche durch fahren über c vermieden werden kann)

 

[Ronschk]

Wesentlich länger als das Alter des Universums

ich meine wir hätten mal in Mathe ne Aufgabe gehabt die von der Berechenbarkeit der Determinante einer 100*100 Matrix geht, welche man mit Hilfe des Laplace'schen Entwicklungssatz berechnen soll. Also 100! Dafür kam glaub ich 15mrd Jahre mit einem handelsüblichen Computer raus... nur so am Rande

 

[TealC]

Ok, ich hatte den Vorfaktor für kleine Städtezahlen deutlich überschätzt.
Die Aussage mit dem Ausprobieren verstehen wir aber eindeutig unterschiedlich.

Der Wikipedia-Artikel gibt für allgemeine Städtezahlen eine Komplexität von O(2^n) an, die derzeitigen Rekorde basieren aber auf "and problem-specific cut generation", was bereits Spezialfälle (~reale Karten) oder menschliches Eingreifen impliziert.
Insbesondere: Reale Karten haben ein naheliegendes Konzept räumlicher Nähe, es gilt beispielsweise die Dreiecksungleichung.

1. Du zitierst ja selbst das Ergebnis der O(n!) und grenzst Dich nicht davon ab.
2. Branch und Bound ist ein weit verbreiteter Algorithmus in der diskreten Optimierung. Diesen als simples ausprobieren zu bezeichnen ist einfach falsch. Schliesslich ändert sich die Komplexität auch von O(n!) in O(2^n).
3. Das Problem, wie es vom TE gepostet ist, ist spezifisch. Insofern sehe ich kein Problem mit Problem spezifischen Algorithmen und erst recht keins mit menschlichem Eingreifen.
4. Die Dreiecksungleichung ist Teil der Definition der Distanz. Ohne Distanz macht die Problemstellung aber keinen Sinn.



@ Kingcools: Die Dreiecksungleichung gilt natürlich immer nur innerhalb einer Definition der Distanz. Du kannst die doch nicht zwischendrin ändern und dann behaupten die Dreiecksungleichung würde nicht mehr gelten. Selten so nen Unsinn gelesen.


Edit:
@Ronschk: Wie seid ihr darauf gekommen? Mir scheint das extrem wenig. Um es mal grob zu ueberschlagen:
100! = 6 * 10^139
Ein moderner Computer hat ca. 50 GFLOPS also 5 * 10^10 Floating Point operations / second http://www.intel.com/support/processors/sb/cs-023143.htm
Ein Jahr hat 365*24*60*60 = 3 * 10^7 Sekunden

Wenn ich das durcheinander teile komme ich auf irgendwas in der Dimension von 10^121 Jahren. Wo irre ich mich? Oder sind die 100! nicht einzelne Operationen? Der Laplace'sche Entwicklungssatz ist bei mir schon ein wenig her.

 

[mfb]

Nicht, wenn man hierbei die zeit berücksichtigt haben will(etwa baustelle auf strecke a nach b, welche durch fahren über c vermieden werden kann)

Das ist doch gerade das Beispiel, wieso in Straßennetzen d(a,b) <= d(a,c)+d(c,b): Selbst wenn keine schnellere direkte Verbindung vorhanden ist, kann man immer noch durch c fahren.


>> Die Dreiecksungleichung ist Teil der Definition der Distanz.
Ich kann auch Graphen mit Kanten entwerfen, bei denen die Dreiecksungleichung nicht erfüllt ist.

>> Du zitierst ja selbst das Ergebnis der O(n!)
Mache ich das? Ich sage, dass n! für n=50 sehr groß ist.



100! sollte schon passen beim Laplace'schen Entwicklungssatz. Sollte die Matrix viele Nullen haben, kann der Aufwand ggf. wesentlich geringer ausfallen. Aber wer so die Determinante ausrechnet (genauer gesagt: anfängt, es zu tun), ist selbst schuld *g*.

 

[Ronschk]

Wenn ich das durcheinander teile komme ich auf irgendwas in der Dimension von 10^121 Jahren. Wo irre ich mich? Oder sind die 100! nicht einzelne Operationen? Der Laplace'sche Entwicklungssatz ist bei mir schon ein wenig her.

hast recht also genau die zahlen haben wir nicht raus gehabt, es war sogar noch etwas mehr. (wir haben aber auch mit anderen Rechenleistungen gerechnet. Als vergleichswert stand da das Alter des Universums ^^
Die Lösung bei uns war 3*10^142 Jahre (da steht aber auch, dass 100!=9*10^157..)
anyway... dauert ganz schön lang :P