Verfasst: 11.12.2005 19:00
du schreibst hier selber "mal", addierst es aber bei Excel?Stadt 29: 28 mal Entfernungen
Stadt 28: 27 mal Entfernungen
Stadt 27: 26 mal Entfernungen
Stadt 2: 1 mal Entfernung
Seite 2 von 5
Verfasst: 11.12.2005 20:42
;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)
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)
Verfasst: 11.12.2005 20:55
stadt 29: muss ich 28 mal eine entfernung ermitteln.PMV hat geschrieben:du schreibst hier selber "mal", addierst es aber bei Excel?Stadt 29: 28 mal Entfernungen
Stadt 28: 27 mal Entfernungen
Stadt 27: 26 mal Entfernungen
Stadt 2: 1 mal Entfernung
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 ....
Verfasst: 12.12.2005 10:13
>>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
>>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
Verfasst: 12.12.2005 13:05
Wie kommst Du zu den Lösungen?Sylvia hat geschrieben: 29 Städte je 3 Verbindungen = 7*10^13 Möglichkeiten
29 Städte je 4 Verbindungen = 3*10^17 Möglichkeiten
Verfasst: 12.12.2005 15:04
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...
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...
Verfasst: 12.12.2005 16:44
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...
Damit das ganze sinnvoll wird, müsstest du aber die Koordinaten von jedem Kreuzungspunkt haben, weil ja bekanntlich viele Wege nach Rom führen...
Verfasst: 12.12.2005 17:09
@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.
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.
Verfasst: 12.12.2005 17:45
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.
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.
Verfasst: 12.12.2005 18:50
@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?
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?