Die letzten 9 Beiträge |
Erstsemester |
Besten Dank :-) |
eulerscheZahl |
Immer erst das mit dem geringsten Wert, vielleicht findet man ja für die anderen eine noch bessere Lösung (siehe C, das geht von 4 auf 3). |
Erstsemester |
Und warum wird dann im dritten Bild B ausgewählt? Ausgehend von der Entfernung von D würde ja B und C gehen? |
eulerscheZahl |
Es gibt 2 Möglichkeiten, auf B zu kommen:
Einmal über D, dann sind es 1+2=3. Aber es geht auch direkt von A, daher die 2. Man nimmt immer das Minimum. |
Erstsemester |
Hey eulerscheZahl,
ich muss das Thema nochmal aufgreifen. Warum hat beim zweiten Durchlauf (zweites Bild oben rechts) B eine zwei? Muss da nicht auf die 1 von D aufaddiert werden? |
ed209 |
Vergiss youtube videos.
Theoretische Informatik ist abstrakt und du solltest sie auch versuchen abstrakt zu verstehen.
Skizzen können dir zur veranschauchlichung dienen, aber sind viel effektiver wenn Du sie selber anfertigst
Die englische Wikipedia hat recht gute Erklärungen zu vielen Standardalgorithmen.
Gruß,
ED |
Erstsemestler |
Super, klasse. Danke dir. Du schaffst es in 7 Zeilen mir das zu erklären, was ich brauche. Die YouTube-Videos dauern zwischen 10 und 15 Minuten und durchsteigen tue ich überhaupt nicht :-) |
eulerscheZahl |
Das Vorgehen ist folgendes:
Der Startknoten A erhält der Wert 0. Alle von ihn aus erreichbaren Knoten erhalten den Wert des Pfads. Du suchst nun den Knoten (bzw. die Knoten) mit dem geringsten Wert. Jetzt gehst du wieder alle Punkte im Graphen durch, die noch nicht verwendet sind und gibst ihnen als Wert den des bereits erreichten Nachbarknotens plus dem der Verbindung. Kannst du einen Knoten auf verschiedenen Wegen erreichen, nimmst du das Minimum. Kannst du einen Knoten gar nicht erreichen (er grenzt an keinen bereits erreichten an), ignorierst du ihn, dann es er eben im nächsten SChritt dran.Das wiederholst du, bis keine Knoten mehr übrig sind.
Im Anhang sind die bereits festen Werte grün, die zu prüfenden rot.
eulerscheZahl hat dieses Bild (verkleinerte Version) angehängt:
|
Erstsemestler |
Dijkstra - Algorithmus
Meine Frage:
Hi Leute,
da die Videos auf YouTube wieder einmal unbrauchbar sind, müsstet ihr mir weiterhelfen.
Das Problem findet sich im Anhang :-)
Meine Ideen:
Besten Dank :-)
Erstsemestler hat dieses Bild (verkleinerte Version) angehängt:
|