Mini-Routenplaner ...

[PMV]

Stadt 29: 28 mal Entfernungen
Stadt 28: 27 mal Entfernungen
Stadt 27: 26 mal Entfernungen
Stadt 2: 1 mal Entfernung

du schreibst hier selber "mal", addierst es aber bei Excel?

[hiltwin]

;o)

ich war gedanklich noch gar nicht bei den berechnungen ...

ich hab erstmal die vorhandenen bzw. zu recherchierenden entfernungen errechnet. oder liege ich da etwa falsch?

deshalb hab ich ja hier nachgefragt, ob jemand in der materie drin ist.

kommt evtl. daher, dass mein gehirn bei urlaubsrundreisen so an die

8.841.761.993.739.701.954.543.615.999.996

möglichkeiten sofort ausblendet, weil ich nie von hamburg erst nach münchen fahre, um dann zurück nach hannover zu kehren ...

aber das bringt mich auf den gedanken, evtl. mit einer matrix und sinnvollen und schwachsinnsverbindungen zuarbeiten.

z.B.
stadt 27 kann nur mit stadt 3, stadt 26 und stadt 29 ....

dass evtl. kombiniert mit dem lösungsansatz von sylvia könnte schon in die richtige richtung gehen ...

um jetzt auf die schnelle die möglichkeiten auszurechnen, wieviele wege es bei 29 städten gibt, wenn jede der städte nur maximal 3 oder 4 mögliche Verbindungen hat, dazu ist mein Mathe-LK allerdings zu lange her ;o)

[hiltwin]

Stadt 29: 28 mal Entfernungen
Stadt 28: 27 mal Entfernungen
Stadt 27: 26 mal Entfernungen
Stadt 2: 1 mal Entfernung

du schreibst hier selber "mal", addierst es aber bei Excel?

stadt 29: muss ich 28 mal eine entfernung ermitteln.
da die verbindung von stadt 29 und 28 nach den 28 ermittelten entfernungen bekannt ist, muss ich bei der stadt 28 nur noch die entfernung zu 27 anderen städten ermitteln, bis schliesslich bei stadt 2 nur noch die entfernung zur stadt 1 zu ermitteln ist ....

[Sylvia]

>>hiltwin: um jetzt auf die schnelle die möglichkeiten auszurechnen,
>>wieviele wege es bei 29 städten gibt, wenn jede der städte nur maximal 3
>>oder 4 mögliche Verbindungen hat

29 Städte je 3 Verbindungen = 7*10^13 Möglichkeiten
29 Städte je 4 Verbindungen = 3*10^17 Möglichkeiten

[hiltwin]

29 Städte je 3 Verbindungen = 7*10^13 Möglichkeiten
29 Städte je 4 Verbindungen = 3*10^17 Möglichkeiten

Wie kommst Du zu den Lösungen?

[Sylvia]

Ganz einfach:

Verbindungen^Städte

3^29 = 3*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3 = ~7*10^13

oder

4^29 = 4*4*4*4*4*4*4*4*4*4*4*4*4*4*4*4*4*4*4*4*4*4*4*4*4*4*4*4*4 = ~3*10^17




Einfacheres Beispiel:

Du hast eine quadratische Fläche von 3m Kantenlänge.
Wieviele Quadratmeter (m2) sind das ?

Lösung: 3^2 = 3*3 = 9 m2


Aufbauend darauf:

Du hast einen Würfel mit 3m Kantenlänge.
Wieviele Kubikmeter (m3) sind das ?

Lösung: 3^3 = 3*3*3 = 27 m3


usw.


Äquivalent, nur in die andere Richtung:

Du hast einen Spielwürfel (=6 Seiten, 1-6 Augen)
Wie hoch ist die Wahrscheinlichkeit, dass du mit einem
Wurf die 3 würfelst ?

Lösung: (1/6)^1 = 16,67%

Du hast 2 Spielwürfel.
Wie hoch ist die Wahrscheinlichkeit, dass du mit einem
Wurf auf beiden Würfeln die 3 hast ?


Lösung: .................................
[hier Formel und Ergebnis eintragen. 5 min Zeit. Zeit läuft... ]



Wie hoch ist die Wahrscheinlichkeit, dass du mit einem
Wurf überhaupt 2 gleiche Augenpaare hast ?


Lösung: .................................
[hier Formel und Ergebnis eintragen. Zeit läuft immer noch...]


Zacki, zacki...für mich ist es auch schon die 6.Stunde...

[Ypser]

Wärs nicht besser (viel einfacher/ weniger aufwändig), die Entfernungen links liegen zu lassen, und stattdessen mit Koordinaten zu arbeiten?

Damit das ganze sinnvoll wird, müsstest du aber die Koordinaten von jedem Kreuzungspunkt haben, weil ja bekanntlich viele Wege nach Rom führen...

[Kaeru Gaman]

@Ypser

dann müsste man die entfernungen wieder aus den koordinaten ermitteln.
k.a. was einfacher is, kommt auf den algo an, den man letztendlich verwenden will...


ich überleg die ganze zeit, ob das wirklich so schwierig wäre,
den AStar auf diese problemstellung anzuwenden.

[NicTheQuick]

Ich würde mehrere Städte, die nahe aneinander liegen gruppieren und als
eins ansehen. Jetzt sucht man erstmal alle möglichen Verbindungen
zwischen diesen Gruppen und sucht die kürzeste Route aus, die man sich
merkt. Jetzt geht man die einzelnen Gruppen in der kürzeste-Route-
Reihenfolge durch und macht darin wieder das selbe, also alle
Möglichkeiten ausknobeln und die kürzeste rausfinden. Dabei sollte man
dann natürlich möglichst als erste Stadt die auswählen, die der letzten
Stadt der vorigen Gruppe am nächsten ist.

So hat man dann nicht z.B. nicht mehr 27! Möglichkeiten, sondern nur
noch 3! * 9! = 2177280. Dann sollten die Gruppen allerdings auch gut
gruppierbar sein. Wenn man eine Start-Stadt hat, dann ist die
Entscheidung auch wieder einfacher.

[otto]

@hiltwin


Das Problem des Handlungsreisenden ist meiner
Einbildung nach noch ungelöst. Nach den
vielen Google-Treffern zu urteilen, wird es
aber gerne an Unis durchgekaut.

Es gibt wohl einige brauchbare Näherungslösungen.

Wenn Du einen schnellen Algorithmus findest,
werden die gesamte Logistikbranche (DHL,Bahn usw.),
Speditionsunternehmen oder Vertreteragenturen,
Dich mit Geld zuschütten.

bei Suchmaschinen mit folgenden Suchworten:

Travelling Salesman Problem
Handels-Reisenden-Problem
Problem des Reisenden
Problem des Handlungsreisenden

Vielleicht studierst Du gerade Informatik und willst das
Forum mal testen?