Die Mathe-Redaktion [Home] - Neues auf einen Blick 25.02.2021 20:21 [Neues] [Forum] [Suche] - Registrieren/Login
 
Matroids Matheplanet Forum Index
Moderiert von matroid
Informatik » Algorithmen / Datenstrukturen » Graphalgorithmen		Druckversion
Druckversion		Antworten
Antworten
Autor
Universität/Hochschule Graphalgorithmen
lapper
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 10.01.2021
Mitteilungen: 7
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2021-01-10


Hallo,

leider mein Studiom ist schon länger her und jemand gab mir diese Aufgabe. Dijkstra selber könnte ich anwenden, aber die Aufgabe Stellung ist für mich etwas seltsam.
Könnte mir jemadn helfen bzw. Tipps geben? ich wäre sehr dankbar





Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 6663
Herkunft: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2021-01-10


Hallo lapper,

willkommen auf dem Matheplaneten!

könntest du bitte erläutern, was mit "lexikographisch kürzesten Wegen" gemeint ist?

Diese Aufgabe steht wahrscheinlich aus einem Lehrbuch.  Was macht denn die Funktion ExtractMin und was sind diese Heaps?

Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6697
Herkunft: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, eingetragen 2021-01-10


Um hier effektiv helfen zu können, muss man den konkreten Algorithmus kennen. Was in den Heap eingetragen werden soll, ist sonst unklar.
Anscheinend soll er verwendet werden, um jeweils den (noch nicht abgearbeiteten) Knoten zu bestimmen, der zu v1 den kleinsten Abstand hat.

Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
lapper
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 10.01.2021
Mitteilungen: 7
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, vom Themenstarter, eingetragen 2021-01-10


2021-01-10 18:03 - StrgAltEntf in Beitrag No. 1 schreibt:
Hallo lapper,

willkommen auf dem Matheplaneten!

könntest du bitte erläutern, was mit "lexikographisch kürzesten Wegen" gemeint ist?

Diese Aufgabe steht wahrscheinlich aus einem Lehrbuch.  Was macht denn die Funktion ExtractMin und was sind diese Heaps?
haha, das sind eben meine Fragen, aber ich versuche 😉 wobei es kann auch ein Versuch sein, mich zu animieren diese Aufgabe selbst zu lösen 😉

"lexikographisch kürzesten Wegen" ist Vermutlich dieser Weg: V1, V2, V3, V4, V5.
Laut Dijkstra habe ich sowas rausbekommen:

Knoten    Distanz vom Start-Knoten
1                  0
2                  10
3                  1
4                  4
5                  6

Also, die Wege nach Dijkstra zu berechnen ist nicht das Problem, aber dann kommt: Heaps und ExtractMin. damit ist vermutlich Min Heap gemeint. So, das macht mir Probleme, wie ich ich die Bäume befüllen (berechnen) soll...
Die Aufgaben 2 und 3 machen mir noch mehr Probleme, leider 🙁
 
Der Algo könnte folgende sein:



[Die Antwort wurde nach Beitrag No.1 begonnen.]

Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
lapper
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 10.01.2021
Mitteilungen: 7
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2021-01-11


2021-01-10 18:26 - Kitaktus in Beitrag No. 2 schreibt:
Um hier effektiv helfen zu können, muss man den konkreten Algorithmus kennen. Was in den Heap eingetragen werden soll, ist sonst unklar.
Anscheinend soll er verwendet werden, um jeweils den (noch nicht abgearbeiteten) Knoten zu bestimmen, der zu v1 den kleinsten Abstand hat.
ist für Euch die Aufgabe auch unverständlich formuliert, oder? ich muss auch rätseln was damit gemaint ist. Das ist eine Prüfungsaufgabe.

Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 6663
Herkunft: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2021-01-11


Wenn die Begriffe nicht bekannt sind, ist die Aufgabe natürlich unverständlich.

Ich kann mir vorstellen, dass mit "lexikographisch kürzer" folgendes gemeint ist.

Wenn W1 und W2 zwei a-b-Wege kürzester Länge sind und vi/vj die ersten Ecken, in denen sich W1 und W2 unterscheiden, dass ist W1 lexikographisch kürzer als W2, falls i < j.

Bei dieser Aufgabe würde das aber keine Rolle spielen, da die kürzesten Wege alle eindeutig sind.

Was mit Heap/BuildHeap gemeint ist, habe ich auch noch nicht verstanden.

Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
lapper
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 10.01.2021
Mitteilungen: 7
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, vom Themenstarter, eingetragen 2021-01-17


ok, wenn diese Aufgabe unklar ist, vielleicht könnt ihr mir helfen bei den anderen? ich müsste pdf hochladen, wobei kann ich es machen?

ich wäre seeehr dankbar.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 6663
Herkunft: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2021-01-17


2021-01-17 14:20 - lapper in Beitrag No. 6 schreibt:
ich müsste pdf hochladen, wobei kann ich es machen?
Wenn es nicht zu viel ist, könntest du mit dem Snipping-Tool unter Windows 10 einen Screenshot vom PDF erstellen, als PNG-Graphik abspeichern und ganz normal als Bild im Thread hochladen.

Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
lapper
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 10.01.2021
Mitteilungen: 7
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, vom Themenstarter, eingetragen 2021-01-24


2021-01-17 15:51 - StrgAltEntf in Beitrag No. 7 schreibt:
2021-01-17 14:20 - lapper in Beitrag No. 6 schreibt:
ich müsste pdf hochladen, wobei kann ich es machen?
Wenn es nicht zu viel ist, könntest du mit dem Snipping-Tool unter Windows 10 einen Screenshot vom PDF erstellen, als PNG-Graphik abspeichern und ganz normal als Bild im Thread hochladen.
Dann kann mir jemand bei diesen Aufgaben helfen?


Wegen der Aufgabe ganz oben, habe ich diese Seite gefunden: www.geeksforgeeks.org/dijkstras-algorithm-for-adjacency-list-representation-greedy-algo-8/

aber noch nicht gelöst.

Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 6663
Herkunft: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, eingetragen 2021-01-24


Bei 2 gibt es sehr einfache Gegenbeispiele.

Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
lapper
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 10.01.2021
Mitteilungen: 7
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, vom Themenstarter, eingetragen 2021-01-24


2021-01-24 15:14 - StrgAltEntf in Beitrag No. 9 schreibt:
Bei 2 gibt es sehr einfache Gegenbeispiele.
könntest Du mir min.1 Besipeil geben, bzw. link senden. Danke

Aufgabe 3 ist schon schwer, muss ich sagen :/

Zurück zu Aufgabe 1, so sind die Methoden beschrieben, was f und l ist, kann ich nur rätseln:



und hier ein Beispiel, wie es aussehen könnte:
















Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 6663
Herkunft: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.11, eingetragen 2021-01-24


2021-01-24 15:49 - lapper in Beitrag No. 10 schreibt:
2021-01-24 15:14 - StrgAltEntf in Beitrag No. 9 schreibt:
Bei 2 gibt es sehr einfache Gegenbeispiele.
könntest Du mir min.1 Besipeil geben, bzw. link senden. Danke

Nimm ein Dreieck, bei denen die Kanten die Längen 2, 2 und 3 haben. Wie sieht ein minimaler Spannbaum aus und welches sind die kürzesten Wege?

Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
lapper
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 10.01.2021
Mitteilungen: 7
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.12, vom Themenstarter, eingetragen 2021-01-24


2021-01-24 16:04 - StrgAltEntf in Beitrag No. 11 schreibt:
2021-01-24 15:49 - lapper in Beitrag No. 10 schreibt:
2021-01-24 15:14 - StrgAltEntf in Beitrag No. 9 schreibt:
Bei 2 gibt es sehr einfache Gegenbeispiele.
könntest Du mir min.1 Besipeil geben, bzw. link senden. Danke

Nimm ein Dreieck, bei denen die Kanten die Längen 2, 2 und 3 haben. Wie sieht ein minimaler Spannbaum aus und welches sind die kürzesten Wege?
danke, klingt logisch.

Also noch die erste Aufgabe ist offen, da die dritte schon zu heftig wäre, man müsste sehr tief in die Materie eintauchen.

Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
lapper hat die Antworten auf ihre/seine Frage gesehen.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]