(Twitter)
Was dir als erstes klar sein muss: Wenn du den Weg von Knoten a, über Knoten b, nach c finden willst, dann kannst du das Problem aufteilen: Finde den Weg von a nach b und danach den Weg von b nach c. Den Weg finden kannst du beispielsweise mit der Breitensuche finden. Um sicher zu gehen, dass es sich um einen "simple path" handelt, würde ich zusätzlich in einem Set, die schon besuchten Knoten speichern. Wenn du von einem Knoten zum nächsten willst, es aber keinen Nachbarknoten gibt, der nicht schon im Set auftaucht, dann gibt es diesen "simple path" nicht. Am Ende einfach die beiden Wege zusammenpacken.
Im Beispiel, das in der Aufgabe gegeben wird: Weg von b nach c, über e. Also: Finde den Weg von b nach e: Breitensuche, bis du zu e kommst, dabei alle Knoten dem Set hinzufügen, i.d.F: b, a (e noch nicht, da wir noch diesem Knoten aus jetzt weitergehen und ihn dann erst hinzufügen). Danach den Weg von e nach c: e, g, c --> Möglich, da keiner dieser Knoten im Set ist --> simple path: b, a, e, g, c
Hoffe es hilft beim Verständnis!
Schüler, Punkte: 455
Breitensuche, weil man damit in einem ungewichteten Graphen immer den kürzesten Weg zum jeweiligen Knoten findet, was bei Tiefensuche nicht der Fall ist. Bildlich gesehen, geht die Breitensuche von einem Knoten ja immer einen "Schritt" oder eine "Stufe" weiter über eine Kante ... heißt erstmal alle direkten Nachbarknoten, dann alle Nachbarknoten davon usw... wenn du also irgendwann bei dem Knoten ankommst, bei dem du sein willst, muss es zwangsweise der schnellste Weg sein, da du immer nur eine Kante weitergehst. Und ein Spanning Tree hat eigentlich nichts mit dem kürzesten Weg zu tun soweit ich weiß
─ daniel.kuenkel 12.01.2021 um 19:09https://www.youtube.com/watch?v=eey91kzfOZs&t=2977s&ab_channel=CS50
Vorlesung aus Harvard Computer Science - Artifical Intelligence ... enthält Breitensuche und Tiefensuche usw...
Finde ich persönlich eine richtig gute Vorlesung!
woow super danke dir!
─ sayuri 12.01.2021 um 19:59Kannst du bitte meine Antwort akzeptieren, dann bin ich 1. Platz :-)
─ daniel.kuenkel 12.01.2021 um 20:24ja klar :) schon gemacht!
─ sayuri 13.01.2021 um 08:37
Markdown wird unterstützt.
woow vielen Dank! Geht nur Breitensuche, woher hast du gewusst, dass es sich um eine Breitensuche handelt und nicht um eine Tiefensuche oder Minimum Spanning Tree?
─ sayuri 12.01.2021 um 19:01