Weg finden

Aufrufe: 226     Aktiv: 13.01.2021 um 08:37

0

Hallo zusammen

Um dieses Problem zu lösen, brauche ich hier ebenfalls Prims oder Kruskal Algorithmus?

Vielen Dank!

enter image description here

Diese Frage melden
gefragt

Student, Punkte: 64

 
Kommentar schreiben
1 Antwort
1

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!

Diese Antwort melden
geantwortet

Schüler, Punkte: 385

 

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

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:09

https://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!

  ─   daniel.kuenkel 12.01.2021 um 19:14

woow super danke dir!

  ─   sayuri 12.01.2021 um 19:59

Kannst du bitte meine Antwort akzeptieren, dann bin ich 1. Platz :-)

  ─   daniel.kuenkel 12.01.2021 um 20:24

ja klar :) schon gemacht!

  ─   sayuri 13.01.2021 um 08:37

Kommentar schreiben