Hallo zusammen,
ich habe mal ne Frage zur oben genannten Aufgabe:
Kann ich davon ausgehen, dass bei get-distance immer nur Weglängen abgefragt werden, ausgehend von einem Knoten der höher im Graphen steht als der Zielknoten?! Mit anderen Worten ist nur so etwas erlaubt:
(get-distance 'E 'G mygraph)
oder soll unsre Prozedur auch diese Abfrage abarbeiten können:
(get-distance 'G 'E mygraph)
Bei der letzten Abfrage ist nämlich das Problem, dass ich durch meinen rekursiven Durchlauf des Listen-Graphen diesen Weg nicht finden kann, da er ja nicht weiss, wenn er bei G angelangt ist, dass über ihm Knoten stehen, die auch zu E führen.
Sonst kann das ganze beliebig ekelhaft werden, da ich mir meinen Graphen nochmal in einen Akkumulator speichern und diesen danach nochmal überprüfen müsste.
Danke im voraus
Hausübung 5 Aufgabe 7 Graphen
- MisterD123
- Geek
- Beiträge: 811
- Registriert: 31. Okt 2006 20:04
- Wohnort: Weiterstadt
er meint was anderes .. es gibt in dem gegebenen graphen sowohl einen weg von E nach G wie auch einen Weg von G nach E
dein Programm sollte auch BEIDE Wege finden können.
Wenn dein Prog. das nicht kann ist es falsch. Das Problem was du beschreibst macht dein Programm praktisch nutzlos da es Glückssache ist ob ein Weg gefunden wird oder nicht.
Ein Graph ist durch seine Kanten beschrieben und die beiden Graphen:
(list (make-edge 'A 1 'B)
(make-edge 'B 1 'C)
(make-edge 'C 1 'A))
(list (make-edge 'B 1 'C)
(make-edge 'A 1 'B)
(make-edge 'C 1 'A))
sind gleich .. oder besser gesagt äquivalent. (man spricht auch von isomorph)
ob dein Programm einen weg von A nach C findet ist dann von der Reihenfolge abhängig, das kanns nicht sein da es in dem Graphen von jedem Knoten zu jedem anderen einen Weg gibt.
Schaut mal auf das Bild im Attachment. Alle wege welche ihr per Hand finden könnt in dem Graphen sollte euer Prog auch finden (check aber bitte vorher das ich mich nicht vertan hab beim erstellen der grafik)
dein Programm sollte auch BEIDE Wege finden können.
Wenn dein Prog. das nicht kann ist es falsch. Das Problem was du beschreibst macht dein Programm praktisch nutzlos da es Glückssache ist ob ein Weg gefunden wird oder nicht.
Ein Graph ist durch seine Kanten beschrieben und die beiden Graphen:
(list (make-edge 'A 1 'B)
(make-edge 'B 1 'C)
(make-edge 'C 1 'A))
(list (make-edge 'B 1 'C)
(make-edge 'A 1 'B)
(make-edge 'C 1 'A))
sind gleich .. oder besser gesagt äquivalent. (man spricht auch von isomorph)
ob dein Programm einen weg von A nach C findet ist dann von der Reihenfolge abhängig, das kanns nicht sein da es in dem Graphen von jedem Knoten zu jedem anderen einen Weg gibt.
Schaut mal auf das Bild im Attachment. Alle wege welche ihr per Hand finden könnt in dem Graphen sollte euer Prog auch finden (check aber bitte vorher das ich mich nicht vertan hab beim erstellen der grafik)
Ist mit Nachbarknoten wirklich Nachbarknoten gemeint oder doch Nachfolgerknoten? Da es sich um einen gerichteten Graphen handelt macht dies ja einen Unterschied.
Nachbarknoten d(V) ist die Vereinigung der Menge der Vorgängerknoten d+(V) und der Menge der Nachfolgerknoten d-(V). So ähnlich habe ich das jedenfalls gelernt.
Nachbarknoten d(V) ist die Vereinigung der Menge der Vorgängerknoten d+(V) und der Menge der Nachfolgerknoten d-(V). So ähnlich habe ich das jedenfalls gelernt.
es ist in der Vorlage für die hausübung ja ein Beispiel gegeben. Dieses Bsp. ist korrekt! - Das sollte deine Frage beantworten 
.. ich will euch noch nen Tip geben .. welche art von Nachbarknoten ist denn sinnvoller? ... denkt mal darüber nach wie man die nachbarfunktion so für die nächste Aufgabe nutzen könnte ..

.. ich will euch noch nen Tip geben .. welche art von Nachbarknoten ist denn sinnvoller? ... denkt mal darüber nach wie man die nachbarfunktion so für die nächste Aufgabe nutzen könnte ..
kann mir mal jemand auf die sprünge helfen
Hey kann mir mal einer helfen? Es geht um die 7.2 Ich bin glaube ich nah dran, nur funktioniert der Akkumulator noch nicht, bzw. ist vielleicht an der falschen Stelle:
Phil
Wär cool, wenn sich einer mal das anschauhen könnte. contains? hab ich jetzt mal weggelassen. Bin ich denn nah drann? Den ganzen rest hab ich schon, es kommt nur noch auf diese Funktion an.(define-struct edge (start length end))
(define mygraph
(list (make-edge 'B 2 'I)
(make-edge 'B 3 'C)
(make-edge 'I 3 'J)
(make-edge 'J 3 'B)
))
(define (neighbors node mygraph)
(cond
[(empty? mygraph) empty]
[(not (symbol? node)) 'kein_Knoten]
[(symbol=? (edge-start (first mygraph)) node) (cond
[(equal? (edge-start (first mygraph)) (edge-end (first mygraph)))(neighbors node (rest mygraph))]
[else(cons (edge-end (first mygraph)) (neighbors node (rest mygraph)))])]
[else (neighbors node (rest mygraph))]
)
)
(define (find-route orgination destination mygraph)
(local(
(define (find-route1 orgination destination mygraph accu)
(cond
[(equal? orgination destination) (list destination)]
[else (local((define possible-route (find-route2 (neighbors orgination mygraph) destination mygraph (cons orgination accu))))
(cond
[(boolean? possible-route) false]
[(contains? orgination accu) 'keine_Route_moeglich]
[else (cons orgination possible-route)]))]
))
(define (find-route2 lo-Os destination mygraph accu)
(cond
[(empty? lo-Os) false]
[else (local((define possible-route (find-route1 (first lo-Os) destination mygraph accu)))
(cond
[(boolean? possible-route) (find-route2 (rest lo-Os) destination mygraph accu)]
[else possible-route]))]
))
)
(find-route1 orgination destination mygraph empty)))
Phil
- MisterD123
- Geek
- Beiträge: 811
- Registriert: 31. Okt 2006 20:04
- Wohnort: Weiterstadt