Hab soeben ein möglicherweise interessantes Thema in einem anderen Forum entdeckt, und zwar im "Matheboard".

Es geht darum, wie viele mathematische Möglichkeiten ein Kurier hat, eine bestimmte Strecke zu fahren.

Hier klicken zum Thema im Matheboard

Bin ja gespannt, was dabei noch herauskommt.

Vielleicht mag sich jemand von unseren Lesern beteiligen?

ooh das hatte ich früher mal im mathe-lk.. eieiei.. aber das ist jetzt neun jahre her..

Die Anzahl der insgesamt möglichen Wege kannste bei dem Schachbrett-Modell einer Stadt mit dem Formelinstrumentarium der Kombinatorik durchrechnen. Das macht aber nicht wirklich glücklich denn Du willst ja nicht alle theoretisch möglichen Wege betrachten sondern "nur" wissen, wie viele kürzeste Wege es gibt.

Wenn Du in einer p Felder breiten und q Felder hohen Stadt von "links unten" nach "rechts oben" kommen willst darfst Du also für einen kürzesten Weg grundsätzlich nur nach rechts oder nach oben gehen in einem Schritt. Das bedeutet, daß Du so lange, wie Du noch nicht rechts oder oben angekommen bist, je Schritt zwei Wahlmöglichkeiten hast. Bist Du einmal oben oder rechts angekommen gibt es nur noch eine.

Wir brauchen aber erstmal die Länge des Weges um zu wissen wie viele Schritte überhaupt zu gehen sind. Die ist recht einfach zu bestimmen: wir müssen p-1 Felder nach rechts gehen und q-1 Felder nach oben

s = (p - 1) + (q - 1) = p + q - 2

Auf diesem Weg gibt es nun "Restschritte" und "Wahlschritte".

r = max(p-1,q-1) - min(p-1,q-1)

Das sind die Restschritte. Die haben keine Wahlalternative. Die restlichen Schritte sind Wahlschritte, also

w = s - r

Für eine quadratische Stadt sollte man einfach "n über k" rechnen können, also

(n über k) = n! / ((n-k)! * k!)

Und das dann mit der Zahl der Restschritte multiplizieren, die ja an beliebiger Stelle in den Laufweg eingestreut werden können.

Damit wird vermutlich irgendetwas der Art

z = ((p-1)! / ((p-q-2)! * (q-1)!)) * r

mit z als Zahl der möglichen Wege herauskommen.

Hmm, nett. Leider muß ich gleich nochmal los und kann das Ding gerade nicht zu Ende basteln...

0_0

Is das nicht das allseits beliebte "traveling salesman" Problem ?

_________________
"Variable gears are only for people over forty-five. Isn't it better to triumph by the strength of your muscles than by the artifice of a derailleur? We are getting soft. As for me, give me a fixed gear!" - Henri Desgrange - 1902

@tumor:

Beim TSP muß jedes Feld einmal besucht worden sein. Ist also was anderes.

ich fahr immer diagonal

_________________
Wenn du denkst es passt nicht mehr, kommt von irgendwo ne Lücke her!!