Wie Strassenkarte modellieren

[Otto Gral (Gast)]

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.

[Stefan Salewski (Gast)]

>, 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).

[Null (Gast)]

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.

[Nils (Gast)]

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

[Otto Gral (Gast)]

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.

[Otto Gral (Gast)]

@ Nils
ja hilfreich. Danke für die Literaturtipps

[Otto Gral (Gast)]

>Der Weg muss bei jedem neuen Punkt nachschauen, ob er da schon war.

@Null
Ja das kommt im nächsten Schritt, das wird auch nochmal interessant.

[Null (Gast)]

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.

[Nils (Gast)]

> 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

[Heiko (Gast)]

Wikipedia hat noch zwei Artikel zum Thema:

1.) Dijkstra-Algorithmus 
(http://de.wikipedia.org/wiki/Dijkstra-Algorithmus) Ein Algorithmus, der 
den kürzesten Weg in einem Graph berechnet.

2.) Repräsentation von Graphen im Computer 
(http://de.wikipedia.org/wiki/Repr%C3%A4sentation_von_Graphen_im_Computer) 
Informationen darüber, wie man einen Graph im Computer speichern kann.

Viele Grüße