| Autor |
Beitrag |
    
Frederike Zorro (Frederike03)
| | Veröffentlicht am Mittwoch, den 27. Juni, 2001 - 18:29: | 
|
Ich habe ein Gitternetz vorliegen, an der linken unteren Ecke ist Punkt A, an der rechten oberen Ecke Punkt B. Das Gitternetz ist m=3 Strecken hoch und n=5 Strecken lang. Eine Strecke ist die Linie zwischen zwei Knoten. Wie viele verschiedene "kürzeste Wege" gibt es für dieses konkrete Beispiel? Wie würde die allgemeine Formel für dieses Problem aussehen? |
Frederike Zorro (Frederike03)
| | Veröffentlicht am Mittwoch, den 27. Juni, 2001 - 19:29: |
|
Ich habe mir folgendes überlegt: Wenn ich einen "kürzesten Weg" wähle, muß ich genau 8 Knoten passieren. Wenn ich "ideal" gehe (bezogen auf die Anzahl d. Möglichkeiten) habe ich 2^7 mal die Wahl zwischen rechts und oben, bei der letzten Strecke ist der Weg vorgegeben, ich hab also nur eine Möglichkeit. Ich würde so also zu der allgemeinen Formel 2^(m+n-1) kommen. Mir kommt die Lösung aber falsch vor. Kann mir jemand helfen? |
Matroid (Matroid)
| | Veröffentlicht am Mittwoch, den 27. Juni, 2001 - 19:56: |
|
Gitter 3 hoch, 5 breit. Start links unten (A).
Zu zaehlen kuerzeste Wege von A nach rechts oben (B).
Welches sind die kürzesten Wege? Diejenigen bei denen man nie nach unten oder nach links geht.
An jedem Punkt hat man also die Wahl nach oben oder nach rechts zu gehen. Alle Wege, die man auf diese Art findet sind gleich lang (und am kürzesten).
Um überhaupt von A nach B zu kommen muß man insgesamt 3 mal hoch und 5 mal nach rechts gehen.
Etwa so: Hoch Rechts Rechts Hoch Rechts Hoch Rechts Rechts
Statt Hoch schreibe ich 1, statt Rechts eine 0.
Also 1 0 0 1 0 1 0 0
Man kann jeden der gesuchten Wege durch eine 0-1-Folge beschreiben, und umgekehrt ergibt jede 0-1-Folge mit genau 3 Einsen einen Weg von A nach B. Verschiedene 0-1-Folgen dieser Art ergeben verschiedene Wege.
Die Anzahl der kürzesten Wege ist also gleich der Anzahl der 0-1-Folgen mit Länge 8 und genau 3 Einsen.
Wieviele verschiedene solche 0-1-Folgen gibt es:
Man kann unter den 8 Plätzen, die zu belegen sind, genau 3 aussuchen und dort eine 1 schreiben.
Wieviele Möglichkeiten gibt es dafür: 8 über 3.
Gruß
Matroid |
Frederike (Frederike03)
| | Veröffentlicht am Mittwoch, den 27. Juni, 2001 - 20:54: |
|
Danke Matroid! |
|
