opengeodb brauche hilfe

**TobiaZ** · 02.10.2005, 11:13

*verschieb* nach Projekthilfe, da hier jeder ansatz und motivation fehlt.

**Titus** · 04.10.2005, 09:52

Solange es nur um Luftlinie geht ... denn mehr Informationen als die geographische Lage ist in der geodb afaik nicht drin ... easy.

Ein bißchen Backtracking, ein bißchen Trigonometrie (Satz des Pythagoras) und fertig ist die Laube.
Vorsicht - bei größeren Datenmengen braucht Backtracking eine Weile, da die Komplexität O(n!) ist.
2 Punkte: max. Rekursionstiefe 2 (2+2*1 = 4 Durchläufe)
3 Punkte: max. Tiefe 3 ... 3*(1+2*(1+1)) = bis zu 15 Durchläufe
4 Punkte: max. Tiefe 4, 4*(1+3*(1+2*(1+1))) = bis 64 Durchläufe
5 Punkte: 64*(1+5) = bis 376 Durchläufe
...

Wie funktioniert Backtracking? Backtracking ist ein rekursiver Algorithmus, der alle Kombinationen durchrechnet. Ist ein Weg länger als der bisher kürzeste vollständige Weg, kann die Rekursion vorzeitig abgebrochen werden.

Du hast ein Array mit mehreren Koordinaten-Paaren und suchst die kürzeste Strecke, die alle Punkte miteinander verbindet.
Die drei Stationen seien $a[0] bis $a[2], jedes Element bestehend aus ['x']- und ['y']-Korrdinaten sowie einem Namen.
einige zusätzliche Variablen:
$weg: ein Array mit dem Weg, den du gerade durchrechnest
$km: die aktuelle Wegstrecke
$kurz_weg: ein Array mit dem bisher kürzesten Weg
$kurz_km: die bisher kürzeste Wegstrecke
Initialisiere diese vier Variablen mit 0 bzw als leeres Array.
Laufe durch alle möglichen Startpunkte, merke dir den Punkt: array_push($weg, $index)
und dann starte die Rekursion
1. Suche einen Punkt, der noch nicht im Weg enthalten ist (Schleife über alle Punkt, in_array)
2. Ermittle den Abstand zum vorhergehenden Punkt (Satz des Pythagoras)
3. Um spätere Rechnerei zu sparen, kannst Du dir den Abstand in einem weiteren (zweidimensionalen) Array merken.
4. ist $kurz_km>0 && $km+$abstand >= $kurz_km: nächsten Punkt versuchen (continue)
5. Merke dir den Punkt: array_push($weg, $i), erhöhe die Strecke um den Abstand ($km += $abstand)
6. Sind noch Punkte nicht auf dem Weg ( count($weg)<count($a) )?: Iteration
7. Am letzten Punkt angekommen: $weg und $km in $kurz_weg und $kurz_km speichern
8. Rekursionsabbruch ( count($weg)<count($a) ): array_pop($weg), $km-= $abstand
Jetzt steht in $kurz_weg der kürzeste Weg, der alle Punkte genau einmal durchläuft; $kurz_km enthält die gesamte Weglänge.

**ripper** · 10.10.2005, 13:19

das ist zu hoch für mich ...

**TobiaZ** · 10.10.2005, 13:21

Stuhl?

**Titus** · 20.10.2005, 11:22

Die Uni Wuppertal hat da ein tolles Tutorial zu, mit Java-Demos ... nicht direkt zum Problem "kürzester Weg", aber zu einem anderen grundlegenden Backtracking-Problem.

Schau mal rein: http://www.matheprisma.uni-wuppertal...ckTr/index.htm

**yakuzza** · 26.10.2005, 12:02

Original geschrieben von Titus

ein bißchen Trigonometrie (Satz des Pythagoras) und fertig ist die Laube.

Ich weiß gar nicht was ihr alle mit dem Satz des Pythagoras habt. Das ist die vollkommen falsche Formel!

Der Satz des Pythagoras gilt nur in rechtwinkligen Dreiecken und ist für entfernungsbestimmungen vollkommen unnütz.

Normalerweise macht man sowas mit einem der folgenden Sätze:

Sinus, Cosinus oder Tagenssatz..

auf der HP von Opengeodb ist die formel auch nochmals erläutert, bzw. ist in der Klassendatei von opengeodb unter formula verfügbar.

**yakuzza** · 26.10.2005, 12:07

mal was anderes.. wenn die entfernungsberechnungen alle funktionieren z.b. von ort a nach b, wie kann ich es anstellen das die datensätze nach entfernung sortiert ausgegeben werden?

Hab das ganze mal mit nem formular verbunden indem ich eine plz eigeben kann.. danach wird eine abfrage mit adressen gestartet bei denen die plz mit der eingabe verglichen werden und dann ausgegeben werden.

Hat jmd. ne Ahnung wie ich diese ausgabe nun nach entfernung sortieren kann?

**Titus** · 26.10.2005, 15:51

Original geschrieben von yakuzza
Der Satz des Pythagoras gilt nur in rechtwinkligen Dreiecken und ist für entfernungsbestimmungen vollkommen unnütz.

Normalerweise macht man sowas mit einem der folgenden Sätze:

Sinus, Cosinus oder Tagenssatz..

Pythagoras gilt für rechtwinklige Dreiecke in der Ebene. Hier geht es eigentlich um Kugeldreiecke - aber auch um rechtwinklige!

Natürlich kann man die Erdkrümmung mit in die Entfernung einberechnen, wie es die Formel aus getDistanceFormula macht.
Aber bei Entfernungen innerhalb Deutschlands ist der durch Reduzierung auf die Ebene entstehende Fehler wohl vernachlässigbar; insbesondere im Hinblick auf die Performance bei einer großen Punktmenge. Viel entscheidender ist da schon die Straßenführung. Und um an Daten zu kommen mit denen man den Fehler verringern kann, muss man tief in die Tasche greifen.

Oder hast Du mal den maximalen Fehler durch Pythagoras in unseren Breitengeraden ermittelt? Bei mir ist zugegebenermaßen bisher alles Vermutung.

auf der HP von Opengeodb ist die formel auch nochmals erläutert

hab ne Weile suchen müssen ... wirklich übersichtlich ist die Seite ja nicht.
Für diejenigen, die sich nicht genauso den Wolf suchen wollen wie ich:
http://opengeodb.hoppe-media.com/ind...?FAQEntfernung

... nach entfernung sortiert ausgegeben ...

array (geodb_locations.id => entfernung)
asort(...)

opengeodb brauche hilfe