[-] Der Weg ist das Ziel
-
Ich schau's mir später an. Wenn Du Lust hast, ich bin oft im IRC, da können wir auch mal ne Runde drüber reden. Ich hab noch ein paar Kleinigkeiten entdeckt.
Ich hoffe Du hast nicht das Gefühl, dass ich Deinen Artikel schlechtmachen möchte.
-
Was mir nebenbei mal aufgefallen ist: Hast Du mal drüber nachgedacht, warum Dein Dijkstra wie ne normale Breitensuche aussieht?
-
Guter Artikel soweit
jedoch müssen da noch ein Paar Schlitzer raus :- Wegfindalgorithmen im realen Leben
Du redest von kürzestem Weg und meinst schnellsten. Dies ist schon ein Unterschied auf welchen man bei diesem Thema aufpassen sollte. - Voraussetzungen eines Wegfindalgorithmus'
Kannst du das Wort Graph nicht hier durch etwas anderes ersetzen? Beim Wort Graph denke ich immer direkt an Knoten und Kanten. Aussagen wie "wie der Graph über Achsen verfügt" ergeben dann gar keinen Sinn. Vielleicht Ebene oder Raum. Wieso nicht einfach bei Landkarte bleiben?
Hier eine Beispiel von dem was ich mir bei einem Graph vorstelle:
http://de.wikipedia.org/wiki/Dijkstra-Algorithmus#BeispielLeser die ganz neu sind und noch nicht wissen was ein Graph ist werden sich darunter eine Ebene vorstellen was falsch wäre und die Leser denen es bereits ein Begriff ist werden verwirrt sein.
- Das Prinzip des Dijkstra-Algorithmus
Dazu teilen wir unsere Landkarte zunächst in eine x- und eine y-Achse ein, welche wir anschließend jeweils in beliebig große, jedoch allesamt gleich große Teilstrecken unterteilen.
Tut mir leid aber bei dem Satz kann ich dir nicht folgen. Du gibst dir ein Koordinatensystem und was du mit den Teilstrecken meinst verstehe ich nicht.
Sollen die Farben im Hintergrund des Bildes vielleicht die Höhe des Bodens darstellen also wie auf einer topologischen Karte? Wäre dann vielleicht besser eine richtige Karte zu nehmen.
* Zwischen dem Start- und dem Zielpunkt liegen n weitere Punkte, von denen ebenfalls ein jeder mit einem Koordinatentupel eineindeutig beschrieben werden kann.
Du hast vorher gesagt, dass jeder Punkt eindeutig durch ein Koordinatentupel beschrieben werden kann. Dies ist keine besondere Eigenschaft der n Punkte. Welche n Punkte eigentlich?
- Man muss halt differenzieren …
Die Antwort ist natürlich die, dass uns der Algorithmus in etwa so zuverlässig den kürzesten Weg von A nach B berechnet kann, wie wir sagen können, ob Schrödingers Katze noch immer am Leben ist oder nicht
Du kannst nicht sagen, ob seine Katze lebt aber du kannst mit Sicherheit sagen, der kürzste Weg von A nach B die Luftlinie ist. Wieso ist der Algo also unzuverlässig? Du widersprichst dir übrigens selbst da du sagst der Algo würde immer den kürzten Weg finden.
- Von Feldern, Nullen und Einsen! Oder auch Arrays …
Unsere Datenstruktur weißt Ähnlichkeiten mit einer „Menge“ auf; entsprechend den Einflüssen des Englischen auf die Informatik bezeichnet man sie als „Array“ (engl. „Feld“, „Menge“).
ar·ray ['] I v/t 1. Truppen etc aufstellen.
2. (oneself sich) kleiden, (heraus)putzen.
II s
3. mil. Schlachtordnung f.
4. fig. Phalanx f, (stattliche) Reihe.
5. Kleidung f, Staat m.
2001 Langenscheidt KG, Berlin und MünchenDer Begriff kommt wahrscheinlich daher, dass man die Element im Speicher aufstellt. Mit Feld oder Menge hat es laut Langenscheidt nichts zu tun.
Eine Menge ist ein mathematischer Begriff der durch eine Vielzahl von Datenstrukturen dargestellt werden kann. Er ist selber aber keine Datenstruktur.
Wie wäre es wenn du einfach beim Begriff Landkarte bleibst dann ist ein Feld oder 2D-Array sehr nahe liegend?
(Hinweis zur Vollständigkeit: Natürlich können Graphen auch mit anderen Mitteln, z.B. Structs oder Klassen, verketteten Listen und mehr realisiert werden. Für uns reichte jedoch das Array völlig aus. Lassen Sie sich nur gesagt sein: Es stellt die Spitze des Eisberges dar.)
Structs oder Klassen sind ein Sprachmittel und keine Datenstrukturen. Verkettete Listen sind eine Datenstruktur werden aber soweit ich weiß nicht oft im Zusammenhang mit Graphen genutzt.
In der Formulierung des Algo wären Zeilenumbrüche nicht schlecht. Paragraphen helfen es dem Leser zusammenhängende Ideen besser zu erkennen.
- Zusammenfassende Beschreibung des Dijkstra-Algorithmus
1. Ermitteln des Startpunktes.
2. Ermitteln der Punkte, die am Punkt anliegen.
3. Prüfe nacheinander jeden der anliegenden Punkte, der noch nie zuvor betreten wurde, ob er 0 (begehbar) oder 1 (blockiert) ist.
4. Merken derjenigen der anliegenden Punkte, die 0 (begehbar) sind.
5. Mit jedem dieser anliegenden Punkte wieder bei 2. fortfahren, bis ein gefundener begehbarer Punkt gleich dem Zielpunkt ist; in dem Fall Berechnung abschließen, da Weg gefunden!Der Dijkstra Algo kann man auch als gewichtete Breitensuche bezeichnen. Die Beschreibung passt aber besser auf eine Tiefensuche was ein anderer Algo wäre.
Hab keine Zeit den Rest zu lesen. Mache ich vielleicht ein anderes Mal
- Wegfindalgorithmen im realen Leben
-
Danke für die Kritiken
Nun, insgesamt ist der Artikel so meiner Ansicht nach nicht wirklich veröffentlichbar. Ich werde wohl große Teile neuschreiben. Von daher lohnt ein Lesen der weiteren Teile des Artikels im Moment imho noch nicht.
Wartet bitte, bis ich eine korrigierte Version fertig gestellt habe (was aber noch dauern könnte, ich bin im Moment privat wieder sehr beschäftigt).
-
Setz den Artikel dann vielleicht auf [A] zurück. Wenn du ihn grundlegend überarbeitest dann würde ich den Namen Dijkstra nicht mehr verwenden. Sein Algo ist nun einmal ein standard Algo in der Graphentheorie und deine Version ist eher eine Variante und entspricht nicht gerade dem.
-
Zum Aufwand: Es fehlt noch, dass bei O(n) [oder eben T(n)] das n die eingabegroesse (z.B. Landkartengroesse) ist, sowie das in Klammern eine Funktion in abhaengigkeit von n ist. Also dass ein Algo der O(n) hat, bei der Verdoppelung des Input in etwa doppelt so lang laeuft, aber ein Algo der O(log n) hat, eben bei Verdoppelung nur etwas laenger (log(2) mal) braucht.
Zur Monotonie: Eigentlich heist Monotonie etwas mehr als "macht immer eine richtige Schaetzung". Die monotone Schaetzfunktion gibt umso hoehere Werte zurueck, desto weiter der Abstand ist (also eben z.b. Luftlinie bei "Weg"suche). Ist das nicht gewaehrleistet, so ist der Algo zwar nicht Optimal, terminiert aber (dank Backtracking) doch.
Etwas am Rande: Ich fand die Erklaerungen von Suchalgorithmen auf echten Graphen immer anschaulicher als auf solchen Bildern. Es lassen sich auch so schoen laengere Wege anzeigen.
Sonst aber ein schoenes Ding!
-
Ben04 schrieb:
Der Begriff kommt wahrscheinlich daher, dass man die Element im Speicher aufstellt. Mit Feld oder Menge hat es laut Langenscheidt nichts zu tun.
dict.leo.org sagt dass das schon ne gültige Übersetzung ist. Über die Wortabstammung sagtdas zwar nichts aus, aber die ist wohl hier nicht so interessant.
-
Naja, Menge würde ich eher mit set als mit Array übersetzen.
-
Der Artikel ist gecancelt.
Aber das hat sich vermutlich ohnehin jeder schon gedacht ...
-
Schade,
Falls jemand ihn zu Ende schreiben will, darf er das was du bereits hast verwenden oder nicht?
-
Inhaltlich darf gerne etwas übernommen werden, falls nötig. 1:1 kopierter Text oder die Graphiken bleiben jedoch mir vorbehalten.
Sonst möchte ich den Artikel vlt. mal auf meiner HP veröffentlichen (atm fiktiv, aber ja möglich) und bekäme dann rechtliche Probleme. Z.B. falls eine neue Regelung bezüglich der Nutzungsrechte der Artikel gefunden wird (was ja von Marc+uus schon mehrfach angesprochen wurde).
-
Schade.