Kürzeste Wege von A nach B in einem 2-dimensionalen Gitter

Neue Frage »

Harl3kin Auf diesen Beitrag antworten »
Kürzeste Wege von A nach B in einem 2-dimensionalen Gitter
Also man hat ein 2-dimensionales Gitter aus n x m Quadraten (n = Anzahl der Quadrate in x-Richtung / m = Anzahl der Quadrate in y-Richtung).

Man hat einen Startpunkt A am Quadrat links oben und einen Zielpunkt B rechts unten. Gesucht wird die Anzahl der kürzesten Wege von A nach B, wenn man die Kanten abläuft.

Ich hab ewig rumprobiert aber keine allgemeingültige Formel herausbekommen. Anfangs hab ich versucht für kleinere Felder (z.B. 2x2, 4x2, 3x3) die Wege zu zählen und dann Zusammenhänge zu erkennen. Aber das klappte nicht. Ich denke mal die Anzahl wird mit zunehmender Größe exponentiell steigen. Nur wie hab ich nicht rausbekommen. Kann mir jemand helfen?

MfG

Harl
irre.flexiv Auf diesen Beitrag antworten »

Versuch mal eine Formel für Gitter der Form 1 x n zu finden.
Danach für 2 x n usw.
Ich bin sicher dir wird was auffallen.
irre.flexiv Auf diesen Beitrag antworten »

Du kannst die Sache aber auch gleich kombinatorisch angehen und dich fragen: Wenn der Weg n+m lang ist, auf wieviele verschiedene Weisen kann man m Schritte nach unten bzw. n Schritte nach rechts gehen. Augenzwinkern
Harl3kin Auf diesen Beitrag antworten »

Formeln zu finden hab ich schon ausprobiert (ohne erfolg)
Für 1xm ist die Anzahl: m+1
Für 2xm geht es schon nicht mehr so leicht:
3 - 6 - 11 - 19 (wenn ich mich recht erinnere).

Und je größer n wird desto schwieriger ist es eine Formel zu finden. Das Problem ist der allgemeine Fall.
Ich finde da einfach keine Lösung.

Hatte mal für m > n: m^n + n aber das klappte nicht.
Bin im Moment einfach ratlos.

Hmm kombinatorisch ist denk ich nicht unbedingt die einfachste Lösung (zumindest für mich Augenzwinkern ) Ich seh mal wie weit ich komme.
AD Auf diesen Beitrag antworten »

Gehört zur Kombinatorik, deswegen Verschoben nach Stochastik.


Schreibe x für einen Schritt nach rechts, und y für einen Schritt nach unten. Dann ist ein Weg eine Folge aus (n+m) Buchstaben x,y mit genau n-mal x und genau m-mal y, z.B.

yxxxxxyyxyyyxxxyx

für n=10 und m=7. Dann überleg dir mal, auf wieviel verschiedene Möglichkeiten man die n x-Symbole auf die (n+m) Positionen positionieren kann.
Harl3kin Auf diesen Beitrag antworten »

Das wäre dann bei deinem Beispiel (n=10, m=7):

anzahl = (17 über 10) * (7 über 7)

oder formal: ((m+n) über n) * (m über m)

kann das sein? bin ein wenig eingerostet in kombinatorik.
 
 
AD Auf diesen Beitrag antworten »

Ist richtig, wobei du aber den rechten Faktor (m über m) weglassen kannst - der ist immer gleich 1.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »