H5 6.2

Stumpf.Alex
Nerd
Nerd
Beiträge: 643
Registriert: 1. Okt 2007 12:40
Wohnort: Darmstadt
Kontaktdaten:

Beitrag von Stumpf.Alex »

Ok..
Du hast ja zwei Akkumulatorlisten: eine Restliste A der noch NICHT traversierten Kanten und eine Liste B der bereits besuchten Kanten.
Wenn deine Restliste A irgendwann mal leer ist, dann sollte man in der Liste B der besuchten Kanten einen vollständigen Pfad durch das Haus des Nikolaus haben.

Du gehst also von einem Startpunkt a aus und überprüfst über welchen Kanten in deiner Restliste A man von a aus benachbarte Knoten erreichen kann. Dann muss dein Programm einen möglichen Weg wählen, die gewählte Kante aus der Liste A entfernen und gleichzeitig in der List B eintragen. Dann muss das Programm die gleichen Schritte bei dem neuen Punkt mit der modifizierte Liste A und B wieder machen, bis nichts mehr geht. Entweder Liste A ist dann leer, dann hast du einen Pfad gefunden, andernfalls ist es halt nicht möglich das Haus auf die Weise zu zeichnen. Das Ergebnis der Rekursion ist also die Liste B bzw. empty, wenn halt kein Weg gefunden wurde. Dann muss dein Programm in der Rekursionstiefe soweit zurückspringen bis es eine Stelle erreicht, an der es zuvor die Möglichkeit hatte mehrer Wege zu wählen. Dort muss es nun einfach den nächsten möglichen Weg durchprobieren bis nichts mehr geht.
Schau dir dazu die Folien über das traversieren von Graphen an.
Viel Erfolg!

Mojito Mix
DON'T PANIC
Beiträge: 42
Registriert: 10. Okt 2007 18:28

Beitrag von Mojito Mix »

ich hab auch nochmal eine frage...
geht wieder ums problem nikolaushaus mit startknoten d...
habt ihr da ne schöne ausgabe? bei mir kommt ne ellenlange liste mit emptys raus...
sieht halt hässlich aus, wenn ich die letzte prozedur aufrufe (generate-all-paths)



[(list (list (list empty empty empty) (list empty empty empty)) (list (list empty empty) (list empty empty) empty))
(list (list (list empty empty empty) (list empty empty empty)) (list (list empty empty) (list empty empty) empty))
(list (list (list empty empty) (list empty empty)) (list (list empty empty) (list empty empty)) empty))

Stumpf.Alex
Nerd
Nerd
Beiträge: 643
Registriert: 1. Okt 2007 12:40
Wohnort: Darmstadt
Kontaktdaten:

Beitrag von Stumpf.Alex »

Ich bekomme eine schöne Liste mit jeden möglichen Pfad als Unterliste heraus. Und gar kein empty. Benutze einfach hin und wieder mal append. :wink:

Christian.
Mausschubser
Mausschubser
Beiträge: 56
Registriert: 6. Aug 2007 22:38

Beitrag von Christian. »

also ich sitze auch schon tage dran und bekomme leider nur mist raus.
wahrscheinlich gehe ich wohl falsch an die aufgabe ran...irgendwie frustrierend :(

Benutzeravatar
Krümelmonster
Geek
Geek
Beiträge: 767
Registriert: 17. Okt 2007 13:58
Wohnort: Jossgrund

Beitrag von Krümelmonster »

@Christian.
Sitzt du alleine dran oder
bist du in einer Lerngruppe?

In einer Gruppe kommt man
meistens schneller zum Ziel.
Stell deinen Fuß auf einen hohen Sockel
Mach dir ein Haar aus tausend Locken
Du bleibst doch immer, was du bist!

Christian.
Mausschubser
Mausschubser
Beiträge: 56
Registriert: 6. Aug 2007 22:38

Beitrag von Christian. »

@Krümelmonster
Sitz alleine dran.
In einer Gruppe waere schon besser, aber da ich leider noch nicht in DA wohne, hab ich auch noch kein anschluss gefunden etc.

Benutzeravatar
Krümelmonster
Geek
Geek
Beiträge: 767
Registriert: 17. Okt 2007 13:58
Wohnort: Jossgrund

Beitrag von Krümelmonster »

Da würde ich mich mal um
Anschluss kümmern.
Kannst ja mal im Forum
nachfragen.

Dass das Lernen in einer
Gruppe leichter fällt, kann
ich jedenfalls nur bestätigen.
Stell deinen Fuß auf einen hohen Sockel
Mach dir ein Haar aus tausend Locken
Du bleibst doch immer, was du bist!

saba
Windoof-User
Windoof-User
Beiträge: 36
Registriert: 17. Jan 2007 19:58

Beitrag von saba »

hallo

meine frage wäre ,ob die funktion generate-paths eine pfad zurück geben soll oder mehrere pfade ,weil ich glaube ,wenn es mehrere pfade wäre ,dann braucht man insgesamt mehr als 2 akkumulatoren oder habe ich falsch verstanden ??

Stumpf.Alex
Nerd
Nerd
Beiträge: 643
Registriert: 1. Okt 2007 12:40
Wohnort: Darmstadt
Kontaktdaten:

Beitrag von Stumpf.Alex »

generate-paths soll alle möglichen Pfade von einem Punkt aus ausgeben. Und es geht problemlos mit zwei Akkumulatoren.

niklas
Mausschubser
Mausschubser
Beiträge: 45
Registriert: 1. Okt 2007 15:39

Beitrag von niklas »

Stumpf.Alex hat geschrieben:Ok..
Du hast ja zwei Akkumulatorlisten: eine Restliste A der noch NICHT traversierten Kanten und eine Liste B der bereits besuchten Kanten.
Wenn deine Restliste A irgendwann mal leer ist, dann sollte man in der Liste B der besuchten Kanten einen vollständigen Pfad durch das Haus des Nikolaus haben.

Du gehst also von einem Startpunkt a aus und überprüfst über welchen Kanten in deiner Restliste A man von a aus benachbarte Knoten erreichen kann. Dann muss dein Programm einen möglichen Weg wählen, die gewählte Kante aus der Liste A entfernen und gleichzeitig in der List B eintragen. Dann muss das Programm die gleichen Schritte bei dem neuen Punkt mit der modifizierte Liste A und B wieder machen, bis nichts mehr geht. Entweder Liste A ist dann leer, dann hast du einen Pfad gefunden, andernfalls ist es halt nicht möglich das Haus auf die Weise zu zeichnen. Das Ergebnis der Rekursion ist also die Liste B bzw. empty, wenn halt kein Weg gefunden wurde. Dann muss dein Programm in der Rekursionstiefe soweit zurückspringen bis es eine Stelle erreicht, an der es zuvor die Möglichkeit hatte mehrer Wege zu wählen. Dort muss es nun einfach den nächsten möglichen Weg durchprobieren bis nichts mehr geht.
Schau dir dazu die Folien über das traversieren von Graphen an.
Viel Erfolg!
Ja, soweit wars mir auch klar. War nur an der Implementierung irgendwie gescheitert. Hatte mich dann mit meiner Gruppe zusammengesetzt und jetzt gehts. Danke aber trotzdem!

lg, Niklas

saba
Windoof-User
Windoof-User
Beiträge: 36
Registriert: 17. Jan 2007 19:58

Beitrag von saba »

Stumpf.Alex hat geschrieben:generate-paths soll alle möglichen Pfade von einem Punkt aus ausgeben. Und es geht problemlos mit zwei Akkumulatoren.
und soll am ende die zwite akkumulator als ausgabe von generate-paths zurückgegeben werden ??

Stumpf.Alex
Nerd
Nerd
Beiträge: 643
Registriert: 1. Okt 2007 12:40
Wohnort: Darmstadt
Kontaktdaten:

Beitrag von Stumpf.Alex »

Nicht ganz. Der zweite Akkumulator enthält ggf. zwar einen vollständigen Weg für das Haus des Nikolauses, aber du musst bedenken, dass du durch die wechselseitige Rekursion ja zwischenzeitig mehrmals generate-paths automatisch aufrufst und von denen die Akkumulatorlisten sind halt deine Ergebnisse. Das heißt du musst die Ergebnisse aller generate-paths (mit Ausnahme derjenigen, die keinen vollständigen Pfad bilden konnten) in einer Liste aufzählen.

Sry..aber das ist echt nicht einfach zu durchschauen und dementsprechen schwierig zu erklären.

saba
Windoof-User
Windoof-User
Beiträge: 36
Registriert: 17. Jan 2007 19:58

Beitrag von saba »

und was ist bitte mit wechselseitige rekursion gemeint ?
und meinst du dass man das ergebnis von jede generate-paths irgendwie muss mit hilfe append zusammen fügen

Stumpf.Alex
Nerd
Nerd
Beiträge: 643
Registriert: 1. Okt 2007 12:40
Wohnort: Darmstadt
Kontaktdaten:

Beitrag von Stumpf.Alex »

Hmm..es ist echt schwierig zu erklären und ehrlich gesagt, habe ich die 4. Hilfsprozdure nicht mit wechselseitige Rekursion implementiert, wie vorgeschlagen. Dafür habe ich halt die wechselseitige Rekursion im generate-paths drin, was aus meiner sicht mehr Sinn macht. Habe das nämlich mal für die 4. Hilfsprozedure ausprobiert.

BTP: generate-paths braucht bei mir eine lokal definierte Hilfsfunktion, die eine Liste aller benachbarten Knoten desjenigen Knoten enthält, der gerade von generate-paths betrachtet wird. Also ist das beim Startzustand der Knoten a. Für diesen Knoten wird wie gesagt eine Liste aller Nachbarkanten zusammengestellt. Mit dieser Liste aus Kanten muss nun deine Hilfsprozedur wiederum für jeden Nachbarknoten des vorhin betrachteten Knoten generate-pahts aufgerufen werden und dann geht alles von vorne los.
Bei dem rekursiven Aufruf von generate-paths muss natürlich wie in der Aufgabe beschrieben die besuchte Kante aus der ersten Akkumulatorliste entfernt und der zweiten angefügt werden.
Irgendwann wird ein generate-path rekursiv aufgerufen, dass entweder keinen weiteren Weg nehmen kann, aber nicht alle Kanten abgearbeitet sind. Das heißt wir haben eine Sackgasse und keinen möglichen Weg gefunden. Dann erfolgt das Backtracking, dass bis zum letzten Knoten zurück springt, bei dem deine Hilfsprozedure die Möglichkeit hatte einen andere Nachbarkante zu besuchen. Andernfalls kann es sein, dass ein generate-paths rekursiv aufgerufen wird, dessen erste Akkumulatorliste leer ist.
Das heißt dann, du hast in der zweiten Liste einen Weg abgespeichert, der beschritten werden kann, um das Haus zu zeichen. Ergo, dann muss das rekurisv aufgerufenen generate-paths die Akkumulatorliste als Ergebnis ausspucken. Danach erfolgt trotzdem wieder ein Backtracking bis zu dem Punkt an der deine Hilfsprozedur die Möglichkeit hatte noch eine anderen Weg zu wählen, da wir nicht nur ein mögliches Ergebnis sondern alle haben wollen. Damit das Ergebnis aber nicht verloren geht, musst du daher immer das Ergebnis deiner Hilsprozedur mit dem rekursiven Aufruf von generate-paths appenden.

Hui..so kompliziert ist das leider und ich habe keinen Weg gefunden, wie das noch trivialer zu lösen bzw. leichter zu erklären ist. Sry.

EDIT: Ich glaube der Trick an der Sache ist, dass die 4. Hilfsprozedure keine eigenständige ist, sondern als lokale Hilfsprozedure im generate-paths implementiert werden muss. Weil meine lokal definierte Hilfsprozedure im generate-paths erfüllt zufälligerweise genau die Anforderung, wie sie im Text steht, ist mir gerade aufgefallen. ^^

Benutzeravatar
Skylo
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 149
Registriert: 7. Nov 2006 20:08
Wohnort: Darmstadt (Woogsviertel)
Kontaktdaten:

Beitrag von Skylo »

(generate-paths 'a '( (a b) (b c) (c a)) '())
ergibt derzeit
(list (list 'a 'b (list 'b 'c (list 'c 'a))) (list 'c 'a (list 'b 'c (list 'a 'b))))
Was aber widermal scheiss Darstellung ist ;)

Aber richtig isses doch erstmal oder?
Junge, geh kacken! Echt jetzt!

Antworten

Zurück zu „Archiv“