Seite 1 von 4

H5 6.2

Verfasst: 23. Nov 2007 00:10
von scowli
habe ein problem in der übung 5. und zwar geht es hierbei um die aufgabe 6.2 (pfade und backtracking), genauer um die hilfsprozedur 4 (eine prozedur, die für eine liste benachbarter kanten eines knotens alle möglichen pfade zurückgibt)
mir stellt sich jetzt die frage:
ich habe als paramater der funktion nur eine liste von kanten zu übergeben, von denen ein knoten bei allen kanten gleich ist und eine liste aller kanten, oder? also wenn ich mich auf das haus des nikolauses beziehe:

z.b. (define (procedure '((a b) (a c) (a e) )E ) ...).

kann mir einer helfen und sagen, was die prozedur für dieses beispiel ausspucken müsst, damit ich verstehe, was sie genau tun soll?!?!?

Verfasst: 23. Nov 2007 08:51
von Schalli
Ich stehe vor genau dem selben Problem.

Allerdings heißt es in der Aufgabenstellung
Eine Prozedur, die für eine Liste benachbarter Kanten eines Knotens alle möglichen Pfade
zurückgibt (wechselseitige Rekursion)
was bedeutet, dass die Prozedur nur die Liste aller benachbarten Kanten eines Knotens übergeben bekommt, und nicht noch die Liste aller Kanten (im Fall Haus des Nikolaus die Liste E)

Also so in etwa:
(define (procedure '((a b) (a c) (a e)) ) ...).

Verfasst: 23. Nov 2007 09:22
von Stumpf.Alex
Also ich habe das so verstanden: Du sollst eine Prozedur schreiben die einen Knoten und eine Liste von benachbarten Kanten des Knoten erhälst und dann alle Wege als Liste ausspuckt. Das ergibt auch nur dadurch Sinn, da der Graph ungerichtet ist.

So kannst du zum Beispiel als Liste der banchbarten Kanten des Knotens c die Liste '( (a c) (b c) (c e) (c d) ) erhalten. Nun sollen wir daraus die Pfaden generieren, also folgendes Ergebnis produzieren:

'( (c a) (c b) (c e) (c d) )

Also soll der Inhalt einer Kante so geändert, dass ein Knoten (hier c) von jeder Kante aus ein Startpunkt ist.

Verfasst: 23. Nov 2007 10:18
von Demmi
@Stumpf.Alex: Das hab ich genau so verstanden, allerdings finde ich das ein bisschen sinnfrei, weil ja laut Definition diese beiden equivalent sind:

Code: Alles auswählen

'((a b)(c b)(c a)) == '((a b)(b c)(c a))
Das zweite sieht halt nur besser (logischer) aus.

Meins funktioniert übrigens schon, allerdings muss ich flatten-once aus der dritten (?) Übung nehmen, damit es hübsch aussieht ;)

Verfasst: 23. Nov 2007 12:35
von Dominik
ja, meins funtkioniert auch schon... nur siehts katastrophal aus und mein letzer schritt bleibt auf der strecke... jetzt muss ich nur noch rausfinden, wo du flatten-once benutzt hast :P

Verfasst: 23. Nov 2007 13:28
von scowli
ah ok, ich probiers gleich mal aus :wink:

Verfasst: 23. Nov 2007 14:13
von s!mon
Demmi ich hab dir mal ne PN Geschickt..

Bei mir funktioniert das ganze auch schon so halb. Krieg aber ohne flatten-once ungefähr eine Milliarden Unterlisten und mit hängt er mir seltsamerweise die letzte Kante ab und setzt sie in eine neue Liste:

(list
(list (list (list empty (list 'a 'b)) (list 'b 'c)) (list 'c 'd))
(list 'b 'd)
(list (list (list empty (list 'a 'b)) (list 'b 'd)) (list 'c 'd))
(list 'b 'c))

Das ist jetzt das Ergebnis von generate-path wenn ich das Beispiel aus dem Template nehme (mit a b c d e) und es mit 'a aufrufe..

Und das empty am Anfang muss ich auch noch rausfiltern..

Verfasst: 23. Nov 2007 23:36
von der Interpeter
Ich krieg eine ziemlich eigenartige Liste mit insgesamt 54 Pfaden für den Anfangsknoten A heraus. Kann das stimmen?
Ich hab jetzt mal 10 Pfade davon handisch nachvollzogen und es war immerhin keine Kante doppelt und (noch) kein Pfad doppelt.

Wenn ich jetzt alle Pfade für alle möglichen Anfangsknoten suchen lasse wird das ja riesig, wer will denn die Liste kontrollieren?

Wie prüft ihr ob euer generate-path bzw. generate-all-paths macht was es soll?

Verfasst: 24. Nov 2007 00:26
von Stumpf.Alex
Also ich habe für generate-all-paths 88 raus ^^.

Verfasst: 24. Nov 2007 00:35
von taufrisch
der Interpeter hat geschrieben:Ich krieg eine ziemlich eigenartige Liste mit insgesamt 54 Pfaden für den Anfangsknoten A heraus. Kann das stimmen?
Nein. :|

Verfasst: 24. Nov 2007 03:53
von s!mon
http://de.wikipedia.org/wiki/Haus_vom_Nikolaus

44 Lösungen laut Wikipedia, bzw 88 wenn spiegelbildliche Lösungen zugelassen sind ^^

Verfasst: 24. Nov 2007 14:41
von s!mon
Ich hätte auch mal noch ne Frage. Wie ist das Haus vom Nikolaus definiert:

1.Durchlaufe alle Kanten des Graphes ohne eine zwei Mal zu durchlaufen.
2.Durchlaufe alle Kanten des Graphes ohne eine zwei Mal zu durchlaufen und komme am Ende wieder am Ursprung raus.

Wenn man das Haus vom Nikolaus zeichnet trifft ja das zweite zu. Auf dem Aufgabenblatt steht davon nichts. Ich frage wegen folgendem: Wenn man den Beispielgraph aus dem Template nimmt, gibt es, wenn man vom Knoten b ausgeht 2 Lösungen bei Definition 1, aber keine bei Definition 2. Was ist richtig?

Verfasst: 24. Nov 2007 17:06
von Krümelmonster
Kann mir jemand sagen, was bei Aufgabe 6.2
die vierte Hilfsprozedur machen soll?

Wenn es einige schon fertig haben,
wissen sie ja bestimmt was sie machen
soll.

Verfasst: 24. Nov 2007 20:25
von taufrisch
s!mon hat geschrieben:Ich hätte auch mal noch ne Frage. Wie ist das Haus vom Nikolaus definiert:

1.Durchlaufe alle Kanten des Graphes ohne eine zwei Mal zu durchlaufen.
Genau :D
s!mon hat geschrieben:2.Durchlaufe alle Kanten des Graphes ohne eine zwei Mal zu durchlaufen und komme am Ende wieder am Ursprung raus.
Das geht nicht. :wink:
s!mon hat geschrieben:Wenn man das Haus vom Nikolaus zeichnet trifft ja das zweite zu.
Das mußt du mir mal zeigen... :shock:

Verfasst: 24. Nov 2007 21:02
von s!mon
http://upload.wikimedia.org/wikipedia/c ... kolaus.gif

Links oben zb

Du fängst rechts unten an das Haus zu zeichnen und kommst am Ende wieder rechts unten an..