| |
| Autor |
 Graphalgorithmen |
|
lapper
Junior 
Dabei seit: 10.01.2021
Mitteilungen: 7
 |
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
|
 Notiz  Profil
 Quote
 Link |
StrgAltEntf
Senior 
Dabei seit: 19.01.2013
Mitteilungen: 6785
Herkunft: Milchstraße
 |      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?
|
Notiz Profil
Quote
Link |
Kitaktus
Senior 
Dabei seit: 11.09.2008
Mitteilungen: 6758
Herkunft: Niedersachsen
| 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.
|
Notiz Profil
Quote
Link |
lapper
Junior 
Dabei seit: 10.01.2021
Mitteilungen: 7
| 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.]
|
Notiz Profil
Quote
Link |
lapper
Junior
Dabei seit: 10.01.2021
Mitteilungen: 7
| 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 v 1 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.
|
Notiz Profil
Quote
Link |
StrgAltEntf
Senior
Dabei seit: 19.01.2013
Mitteilungen: 6785
Herkunft: Milchstraße
| 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.
|
Notiz Profil
Quote
Link |
lapper
Junior
Dabei seit: 10.01.2021
Mitteilungen: 7
| 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.
|
Notiz Profil
Quote
Link |
StrgAltEntf
Senior
Dabei seit: 19.01.2013
Mitteilungen: 6785
Herkunft: Milchstraße
| 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.
|
Notiz Profil
Quote
Link |
lapper
Junior
Dabei seit: 10.01.2021
Mitteilungen: 7
| Beitrag No.8, vom Themenstarter, eingetragen 2021-01-24
|
Notiz Profil
Quote
Link |
StrgAltEntf
Senior
Dabei seit: 19.01.2013
Mitteilungen: 6785
Herkunft: Milchstraße
| Beitrag No.9, eingetragen 2021-01-24
|
Bei 2 gibt es sehr einfache Gegenbeispiele.
|
Notiz Profil
Quote
Link |
lapper
Junior
Dabei seit: 10.01.2021
Mitteilungen: 7
|  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:
|
Notiz Profil
Quote
Link |
StrgAltEntf
Senior
Dabei seit: 19.01.2013
Mitteilungen: 6785
Herkunft: Milchstraße
| 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?
|
Notiz Profil
Quote
Link |
lapper
Junior
Dabei seit: 10.01.2021
Mitteilungen: 7
| 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.
|
Notiz Profil
Quote
Link |
|
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]
|
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
