Hallo ich stehe vor einem verzwickten Problem.
Ich habe eine Strassenkarte, ähnlich einem Stadtplan gegeben. Ich möchte
die Strassenteile wie Kurven, Kreuzungen als Knoten darstellen. Jeder
Knoten hat eine Bezeichnung und eine Position. Um später vielleicht eine
Strecke zu finden, möchte ich die Knoten so benennen, dass ich aus der
Bezeichnung schliessen kann, welcher der Vorgängerknoten ist.
Einfaches Beispiel - eine Straße:
------------------
[1] [2] [3] [4] ...
------------------
hier ist klar: wenn ich an Position 3 bin kann ich zu Position 2 oder 4.
Beispiel - eine Kreuzung zweier Straßen:
...
|[2a2]|
| |
|[2a1]|
| |
|[2a0]|
| |
| |
------| |---------
[1] [2] [3]
------| |---------
| |
| |
|[2b0]|
| |
|[2b1]|
| |
|[2b2]|
...
Wenn ich in 2b0 bin kann nach 2b1 laufen oder nach 2
Mit dieser Methode kann ich auf jeden Fall mögliche Nachfolger und den
Vorgänger bestimmen.
Aber Probleme machen wir Zyklen. Wenn bereits bestehende Bezeichnungen
zweier Straßen aufeinander treffen, ist nicht mehr klar, dass zwischen
ihnen beiden eine Verbindung besteht. Siehe folgendes Beispiel
--------------------------------------|
|[2a2] [2a3]|
| |-------------------------| |
|[2a1]| | |
| | | |
|[2a0]| | |
| | |[2a4]|
| | | |
------| |-------------------------| |-------------
[1] [2] [3] [4] [5] [???]
------| |---------------------------------------------
| | /\
| | ||
|[2b0]| Problem
| |
|[2b1]|
| |
|[2b2]|
...
Gibt es da eine Lösung oder Ideen? Stichwort ist Zyklen in
Baumstrukturen. Ich nehme auch gerne andere Datenstrukturen.
>, dass ich aus der>Bezeichnung schliessen kann, welcher der Vorgängerknoten ist.
Man könnte eventuell ein- und denselben Knoten mehrfach benennen
(Alias), dass könnte das Zyklen-Problem entschärfen.
Aber das typische Vorgehen wäre doch, dass man einfach zu jedem Knoten
alle direkten Nachbarn speichert, d.h. die Datenstruktur Knoten enthält
die Felder left, right, top, bottom (Zeiger auf andere Knoten oder
Indizes in einer Matrix).
Ja, das ist Graphentheorie. Da kann man sich vertun. Knoten & Pointer.
Da kann man dann mit Backtracking drueber. Der Weg muss bei jedem neuen
Punkt nachschauen, ob er da schon war.
Hallo Otto,
auf die Gefahr hin, dass ich Dir Sachen sage, die Du schon kennst:
Solche Probleme werden eigentlich unter dem Aspekt 'Graphentheorie'
betrachtet. D.h.: die einfache Benennung der Strecken wird Dir nicht
weiterhelfen, um die Beziehungen für die Knoten zu charakterisieren.
Die Knoten selbst müssen explizit durch Tupel der Form (A, B) erfasst
werden, um eine Verbindung A <-> B zu kennzeichnen. Eigentlich ist die
Beschreibung der Knoten der Dreh- und Angelpunkt - die Strecken/Wege
ergeben sich dann von selbst (bzw. lassen sich parametrisieren (Länge &
weitere Eigenschaften)).
Siehe z.B.:
B. Breutmann, Data and Algorithms, Fachbuchverlag Leipzig
H. Reß, G. Viebeck, Datenstrukturen und Algorithmen, Hanser-Verlag
Hilfreich?
Gruß
Nils
Gut, die Mehrfachnennung mit Alias ist letztendlich auch eine Liste.
Darauf läuft es ja sowieso hinaus, egal ob extra abgelegt oder in der
Namesbezeichnung.
Ideal für Zugriffe wäre natürliche eine Implementierung einer nxn
Adijazensmatrix. Das ganze soll mal schätzungsweise für n = einige
hundert Knoten laufen und auf einem einfachen webspace über php
verarbeitet werden. Es sollen kleine Strecken berechnet werden bzw. als
Bild ausgegeben werden. Bei 500 Knotenpunkten sind das bereits eine
viertel Millionen Felder. Mit einer Adijanzensliste sinkt zwar der
Speicherbedarf, aber der Rechenaufwand steigt. Ich weiß nicht, ob mir
Provider nicht das skript vorher abwürgt, ob nun aus Speicher- oder
Performancegründen.
Daher suche ich effizientere Algos.
Der einfachste Weg, so eine Aufgabe zu modellieren, besteht darin den
Kreuzungen knoten zuzuweise, und die Strassen als pointer zur naechsten
Kreuzung zu nehmen. Die Struktur gibt dann kein Baum und keine Matrix,
sondern ein dynamisches Netz, Graph genannt.
> Ideal für Zugriffe wäre natürliche eine Implementierung> einer nxn Adijazensmatrix
ah, ok - wie gesagt, der Witz ist der, dass in der Matrix-Darstellung
nur die Knoten auftauchen. Der gesamte Graph (d.h. die Menge der Tupel)
steckt dann in der Adjazensmatrix. Die Diagonalisierung ist dann der
Schlüssel zum effizienten Lösen des EW-Problems.
Siehe hier:
http://www.geoinformatik.uni-rostock.de/einzel.asp?ID=2046926980
Gruß
Nils
