Rekursion in C

Hallo,

ich habe ein so ähnliches Programm geschrieben!
Allerdings findet es den Weg durch ein Labyrinth...

Es funktioniert bei mir mittels Backtracking.

Mein Programm probiert also einen Weg, führt der nicht zum Ziel, wird der nächste probiert, ist der ebenfalls nicht der gewünschte Weg, wird zur Kreuzung davor zurückgegangen und da der nächste Weg probiert usw..

Vielleicht hilft es dir was...

Es ist unter folgender Quelle zu haben:
http://www.stefanbredl.de/proggs.html

Allerdings ist das Programm älter und ist vom Stil her mit Grundkenntnissen programmiert.

mfg ByteDigger
 
Also das beste ist du machst dir selber Gedanken dazu.

Stichpunkte oder Anhaltspunkte wären das Erreichbarkeitsproblem bei Nichtdeterministischen Automaten.
Ich hab sowas schonmal programmiert allerdings in Java. Ich werd dir das mal mit hinten dranhängen....

Also am besten du machst dir eine Skizze.

Als Anfangsknoten zeichnest du dir deinen Startbahnhof auf.
Von diesem dann machst du die verschieden Pfeile weg welche zu deinen Zielbahnhöfen führen. Diese bilden dann wieder einen Knoten und von diesem gehen dann wieder Pfeile zu dem nächsten Zielbahnhof weg.

In C könnte dieser Graph dann folgender Massen ausschauen:

int stations[5][5] = {{2,1},{2,0},{3,1},{2,0}}

Die Indezes der ersten Dimension entspricht deinem Aktuellen Bahnhof, die Inhalte deren
Felder entsprechen den Zielbahnhöfen wo man hinkommen könnte.

Jetzt musst du dieses Feld Systematisch durchsuchen und dir in einem anderen Feld merken welche Stationen schon alle erreicht wurden.


Für das Programm guckst du hier

Gruß

RedWing

P.S Uups da war ich wohl mal wieder nich der schnellste ;)
 
Töff, töff die Eisenbahn

Also ich persöhnlich würde als Datenstruktur einen Baum verwenden, wenn dieser Baum vernünftig implementiert ist (in C Stichpunkt struct), dann kann auch eine Suche sehr schnell von staten gehen.
Wichtig bei dieser Aufgabe wäre noch zu wissen, benötigst du nur einen Weg von A nach B.
Oder benötigst du den kürzesten Weg von A nach B?
Wobei letzteres dann natürlich etwas länger dauert, da ja alle möglichen Wegkombinationen gesucht werden müssen.
Generell würde ich das so in etwa machen, wie es ByteDigger grob angesprochen hat.

Die Datenhaltung ansich würde ich mir folgendermaßen vorstellen:
Du hast für jeden Bahnhof eine struct, die die Eigenschaften beschreibt (Name, usw...).
Desweiteren dann hast du noch ein Array, das Zeiger auf wiederum structs vom Typ Bahnhof enthält, das wären die Nachbarn. Evtl könnte man das Array auch 2-dimensional machen um noch die Entfernung mit zu speichern, was für die Berechnung der kürzesten Wegstrecke sehr hilfreich wäre.
So jetzt kannst du dann mit entsprechenden Funktionen dein Netz/Baum aufbauen.
Wenn der Baum "steht", dann musst du ihn "nur" noch ablatschen, also vom Knotenpunkt A anfangen bis nach Knotenpunkt B.

Übrigens:
Wenn man das ganze in C++ machen würde, dann könnte man den Vorteil von Klassen nutzen und sich hierzu eine Basisklasse bauen, mit der man dann x-beliebige Fälle nachbilden kann.
Denn das ganze Schema kann man nicht nur auf Bahnhöfe anwenden, sonder auch wie ByteDigger gesagt hat auf Labyrinthe usw...

Gruß Homer

P.S.:
Das Ganze wäre doch ein tolles Tutorial-Thema oder?
Evtl. hat ja jemand Lust dazu ein Tutorial zu machen.
 
Danke Danke für die großartige Unterstützung.

Habe jetzt sicher genug Ansätze. Wenn man das nicht nur als Aufgabe sieht sondern weiterspinnt, könnte glatt ein Routenplaner draus werden. :p Aber dazu müßte man sich ja noch um mehrere Linien, Uhrzeiten etc. kümmern und dafür sorgen, dass die Bahn nicht im Kreis fährt...

Gruß
René
 
Um antworten zu können musst du eingeloggt sein.

Neue Beiträge

Zurück