Ist eine 2-dimensionale Map hier angebracht?

Hallo,

ich muss immer wieder Distanzen zwischen Städten während des Programms "nachschlagen" und will diese 1x am Anfang berechnen. Soweit kein Problem, nur in welcher Datenstruktur speichere ich die Entfernungen?

Im Prinzip ist es ja ein zweidimensionales Feld. Aber ich kann ja schlecht zwei Objekte vom Typ Stadt an einen 2-Dim Vector übergeben und den dazugehörigen Wert zurückgeliefert kriegen, oder?

Ich hab jetzt überlegt, dass ich vielleicht eine 2-Dim Map nehme.

getDistanz(Stadt& stadt1, Stadt& stadt2)

sollte dann den gesuchten Wert liefern. Ist das ok oder gibt es einfachere/sauberere Wege?

Ich hab mittlerweile überlegt, dass ich eine Datenstruktur "Schlüssel --> Wert" für geeignet halte. Also wäre es hier die Abbildung "(Städtepaar) --> double". Zufälligerweise hab ich sogar eine geeignete Klasse, die Städtepaar entspricht und sich eignet.

Eine einfache Map wäre also geeignet. Das Problem ist nur, dass ich dafür einen Vergleichsoperator für die Klasse Städtepaar definieren müsste, oder? Leider weiss ich (noch) nicht wie ich das am besten mache, aber das würd ich dann schon hinkriegen.

Andererseits brauch ich ja in meiner Datenstruktur überhaupt keine Ordnung. Ich hab mich gerade ein wenig umgeschaut und wollte evtl. hash_map nehmen. Die ist aber nicht ISO-C++. Also will ich das vermeiden.

Hat jemand evtl. 'ne bessere (saubere) Idee für eine Datenstruktur? Es werden am Anfang alle Werte 1x in die DS eingefügt und später wird sehr sehr oft auf diesen Wert mittels Schlüssel zugegriffen. Sonst muss die DS nichts leisten können.

Jester

Warum die Städte nicht einfach durchnumerieren von 1 bis n und dann eine nxn-Matrix anlegen (entweder als normales Array oder als vector<vector<double> >) und dann die Distanz von Stadt r zu Stadt s an der Stelle
Distanzen[r][s] eintragen.

MfG Jester

Ja, das war auch mein erster Gedanke. Aber die Städte befinden sich in einem Vector. Genauer gesagt gibt es unzählige Vectoren aus Städten (quasi Städtelisten). Die Städte werden übrigens auch erst zur Laufzeit angelegt und die Vektoren dauernd "geshuffelt".

Ich könnte natürlich anfangs durchnummerieren und den Wert dann jeder Stadt als ID mitgeben. Wäre 'ne Möglichkeit. Aber ich fand's irgendwie aus Modellierungsaspekten "wirklichkeitsnäher" eine Abbildung (Städtepaar) --> double vorzunehmen.

Ich hab jetzt auch meinen "<" Operator für die map fertig und werd das ganze mal durchtesten.

Jester

Ich glaub mit ner ID für die Städtepaare wäre trotzdem alles wesentlich einfacher. Und bedenke: nachschauen in der Map: O(log n) nachschauen in der Matrix: O(1). Gerade für große Anzahlen dürfte sich die Matrix also lohnen.

MfG Jester

Wieso denn nicht auch O(1)? Was soll denn der Mist . Ich adressiere doch direkt mit dem Schlüssel. Ich hab gedacht, das funktioniert so ähnlich wie bei einer Hashfunktion.

Hm. Wenn Du sagst O(log n), dann macht auch die Ordnung in der Map Sinn (den ich vorher nicht gesehen hab). Mist.

Jester

Weil die map intern nen Baum anlegt.
Auch mit ner Hashfunktion hast Du nur Erwartungswert O(1), die aktuellen Zugriffszeiten können schwanken. Weil bei ner Hashkollision halt wieder ne Liste oder ein Baum auf einer Stelle hängt. Und die kostet dann eben wieder.

MfG Jester

OK, Du hast gewonnen. Aber so wie ich's im Moment geplant hab, sind's 18 Städte, die anfangs zur Laufzeit angelegt werden und O(log 18) ist ja dann auch O(1).

Jester

Hihi, wenn Du so argumentierst kannst Du natürlich auch einen exponentiellen Lookup verwenden oder für jede Distanz kurz bei mir anrufen. Ist ja nur ne feste Anzahl an Abfragen. Da ist alles O(1).
Kannst ja mal beide Look-Up Methoden implementieren und testen welche flotter ist. Würd mich schon mal interessieren.

Du implementierst nicht zu fällig grad TSP?

MfG Jester

Dazu fällt mir ein: Ich hab mich mal vor ein paar Jahren erschrocken, als ich gedacht hab, ich hätte P=NP bewiesen. Im Endeffekt hatte ich das ganze bloss falsch verstanden. Puh...

Ich denk aber schon, dass einem bei so niedrigen Werten der Unterschied zwischen 1 und log n einigermaßen egal sein darf. Ich werd jetzt aber erstmal aufhören zu programmieren und mir das morgen nochmal in Ruhe ansehen.

Nein, das wird kein TSP. Allerdings auch ein Optimierungsproblem. Es werden viele Nebenbedingungen einfließen und an manchen Stellen eben auch die Distanz zwischen zwei Städten. Ich werd dann versuchen, die Lösung mit evolutionären Algorithmen zu "züchten".