php-resource



Zurück   PHP-Scripte PHP-Tutorials PHP-Jobs und vieles mehr > Jobs und Projekte > Projekthilfe
 

Login

 
eingeloggt bleiben
star Jetzt registrieren   star Passwort vergessen
 

 

 


Projekthilfe Hier könnt Ihr eine Art Projekthilfe anfordern. Unter Projekthilfe verstehen wir Angebote bei denen KEIN Geld gezahlt werden kann.

Antwort
 
LinkBack Themen-Optionen Thema bewerten
  #1 (permalink)  
Alt 02-10-2005, 11:52
ripper
 Registrierter Benutzer
Links : Onlinestatus : ripper ist offline
Registriert seit: Nov 2003
Beiträge: 224
ripper ist zur Zeit noch ein unbeschriebenes Blatt
Standard opengeodb brauche hilfe

hab mir das ganze (opengeodb) installiert und es funktioniert jetzt auch ....

so folgendes:

ich brauche eine abfrage die eine optimale route durch 3 regierungsbezirke berechnet .... optimal so heissen das eine stadt rauskommen soll die die 2 anderen regierungsbezierke verbindet also die kurzeste entfernung

ich hab mir die datenbank angeschaut und gemerkt das es sehr lange dauern wird wenn man sich da ein arbeiten muss ... wenn also einer von euch sich gut damit auskennt dann bitte erklären oder n paar snipsel dazu


danke
Mit Zitat antworten
  #2 (permalink)  
Alt 02-10-2005, 13:13
TobiaZ
  Moderator
Links : Onlinestatus : TobiaZ ist offline
Registriert seit: Jan 2001
Ort: MUC und MGL, Germany
Beiträge: 34.421
TobiaZ befindet sich auf einem aufstrebenden Ast
Standard

*verschieb* nach Projekthilfe, da hier jeder ansatz und motivation fehlt.
__________________
ERST LESEN: Unsere Regeln. | Ich hab schon Pferde kotzen sehn!

READ THIS: Strings richtig trennen/verbinden | JOINs, das leidige Thema | Wegwerf E-Mail Adressen

Ich kann und werde keinen privaten 1:1 Support leisten, außer ich biete ihn ausdrücklich an.
Mit Zitat antworten
  #3 (permalink)  
Alt 04-10-2005, 11:52
Titus
 PHP Master
Links : Onlinestatus : Titus ist offline
Registriert seit: Jan 2001
Ort: im Rodgau
Beiträge: 4.292
Titus ist zur Zeit noch ein unbeschriebenes Blatt
Standard

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.
__________________
mein Sport: mein Frühstück: meine Arbeit:

Sämtliche Code-Schnipsel sind im Allgemeinen nicht getestet und werden ohne Gewähr auf Fehlerfreiheit und Korrektheit gepostet.
Mit Zitat antworten
  #4 (permalink)  
Alt 10-10-2005, 15:19
ripper
 Registrierter Benutzer
Links : Onlinestatus : ripper ist offline
Registriert seit: Nov 2003
Beiträge: 224
ripper ist zur Zeit noch ein unbeschriebenes Blatt
Standard

das ist zu hoch für mich ...
Mit Zitat antworten
  #5 (permalink)  
Alt 10-10-2005, 15:21
TobiaZ
  Moderator
Links : Onlinestatus : TobiaZ ist offline
Registriert seit: Jan 2001
Ort: MUC und MGL, Germany
Beiträge: 34.421
TobiaZ befindet sich auf einem aufstrebenden Ast
Standard

Stuhl?
__________________
ERST LESEN: Unsere Regeln. | Ich hab schon Pferde kotzen sehn!

READ THIS: Strings richtig trennen/verbinden | JOINs, das leidige Thema | Wegwerf E-Mail Adressen

Ich kann und werde keinen privaten 1:1 Support leisten, außer ich biete ihn ausdrücklich an.
Mit Zitat antworten
  #6 (permalink)  
Alt 20-10-2005, 13:22
Titus
 PHP Master
Links : Onlinestatus : Titus ist offline
Registriert seit: Jan 2001
Ort: im Rodgau
Beiträge: 4.292
Titus ist zur Zeit noch ein unbeschriebenes Blatt
Arrow

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
__________________
mein Sport: mein Frühstück: meine Arbeit:

Sämtliche Code-Schnipsel sind im Allgemeinen nicht getestet und werden ohne Gewähr auf Fehlerfreiheit und Korrektheit gepostet.
Mit Zitat antworten
  #7 (permalink)  
Alt 26-10-2005, 14:02
yakuzza
 Junior Member
Links : Onlinestatus : yakuzza ist offline
Registriert seit: Jul 2005
Beiträge: 108
yakuzza ist zur Zeit noch ein unbeschriebenes Blatt
Standard

Zitat:
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.
Mit Zitat antworten
  #8 (permalink)  
Alt 26-10-2005, 14:07
yakuzza
 Junior Member
Links : Onlinestatus : yakuzza ist offline
Registriert seit: Jul 2005
Beiträge: 108
yakuzza ist zur Zeit noch ein unbeschriebenes Blatt
Standard

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?
Mit Zitat antworten
  #9 (permalink)  
Alt 26-10-2005, 17:51
Titus
 PHP Master
Links : Onlinestatus : Titus ist offline
Registriert seit: Jan 2001
Ort: im Rodgau
Beiträge: 4.292
Titus ist zur Zeit noch ein unbeschriebenes Blatt
Exclamation

Zitat:
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.

Zitat:
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

Zitat:
... nach entfernung sortiert ausgegeben ...
array (geodb_locations.id => entfernung)
asort(...)
__________________
mein Sport: mein Frühstück: meine Arbeit:

Sämtliche Code-Schnipsel sind im Allgemeinen nicht getestet und werden ohne Gewähr auf Fehlerfreiheit und Korrektheit gepostet.
Mit Zitat antworten
Antwort

Lesezeichen


Aktive Benutzer in diesem Thema: 1 (Registrierte Benutzer: 0, Gäste: 1)
 

Themen-Optionen
Thema bewerten
Thema bewerten:

Forumregeln
Es ist Ihnen nicht erlaubt, neue Themen zu verfassen.
Es ist Ihnen nicht erlaubt, auf Beiträge zu antworten.
Es ist Ihnen nicht erlaubt, Anhänge hochzuladen.
Es ist Ihnen nicht erlaubt, Ihre Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are an


PHP News

Vorteile eines flexiblen ERP Systems
Vorteile eines flexiblen ERP SystemsEin flexibles ERP System bietet in allen Unternehmensbereichen die Grundlage für eine erfolgreiche Verwaltung, Organisation und Planung aller Prozesse.

01.12.2021 | Berni

Software für alle Arten von digitalen Marktplätzen
Software für alle Arten von digitalen MarktplätzenDigitale Marktplätze sind nicht nur im B2C Geschäft seit Jahren etabliert, sondern erfreuen sich mit Kleinanzeigen-Märkten auf lokaler und regionaler Ebene auch im privaten Bereich wachsender Beliebtheit.

09.11.2021 | Berni


 

Aktuelle PHP Scripte

ebiz-trader 6.0 - Das professionelle PHP Marktplatz Script ansehen ebiz-trader 6.0 - Das professionelle PHP Marktplatz Script

Mit unserer Lösungen können Sie nahezu jeden B2B / B2C Marktplatz betreiben den Sie sich vorstellen können. Ganz egal ob Sie einen Automarktplatz, Immobilenportal oder einfach einen Anzeigenmarkt betreiben möchten. Mit ebiz-trader können Sie Ihre Anforder

09.11.2021 Berni | Kategorie: PHP/ Anzeigenmarkt
PHP Newsletter Script SuperWebMailer ansehen PHP Newsletter Script SuperWebMailer

Die webbasierte PHP Newsletter Software SuperWebMailer ist die optimale Lösung zur Durchführung eines erfolgreichen E-Mail-Marketings. Zur Nutzung des PHP Script-Pakets ist eine eigene Webpräsenz/Server mit PHP 5 oder neuer, MySQL 4 oder neuer und die

28.10.2021 mirko_swm | Kategorie: PHP/ Mail
Guestbook Light ansehen Guestbook Light

Das Guestbook Light (kurz: "Gblight") ist ein kinderleichtes Gästebuch in PHP. Durch den Einsatz einer SQLite Datenbank ist es einfach, leicht portabel und schnell. Aufgrund moderner Techniken erfüllt Gblight auch die neuesten Webstandards.

28.10.2021 scripthostingnet | Kategorie: PHP/ Gaestebuch
 Alle PHP Scripte anzeigen

Alle Zeitangaben in WEZ +2. Es ist jetzt 09:31 Uhr.