php-resource



Zurück   PHP-Scripte PHP-Tutorials PHP-Jobs und vieles mehr > Scripts > BRAINSTORMING PHP/SQL/HTML/JS/CSS
 

Login

 
eingeloggt bleiben
star Jetzt registrieren   star Passwort vergessen
 

 

 


BRAINSTORMING PHP/SQL/HTML/JS/CSS Ihr habt eine Idee, aber keinen genauen Ansatz? Diskutiert mit anderen Usern des Forums über eure Gedankengänge um evtl. hilfreiche Ideen zu bekommen!
Normale Fragen bitte weiterhin in die entsprechenden Foren!

Antwort
 
LinkBack Themen-Optionen Thema bewerten
  #16 (permalink)  
Alt 16-06-2009, 00:07
jmc
 PHP Junior
Links : Onlinestatus : jmc ist offline
Registriert seit: Mar 2006
Beiträge: 868
jmc befindet sich auf einem aufstrebenden Ast
Standard

Wie du die Daten speicherst ist eigentlich egal. Es muss nur möglichst schnell sein. Mit PHP ist wohl die schnellste Variante das Array, ein DB kommt da wohl aber für den mehrfachen Gebrauch sicher nicht in Frage, ausser die wolltest z.B. alle Züge vorberechnet speichern.
Zwei eindimensionale Arrays sind sehr wahrscheinlich schneller als ein zweidimensionales.

Wenn du nicht den besten Weg findest ist entweder deine Heuristik schlecht oder aber du hast den A*-Algorithmus nicht richtig umgesetzt.
Je nachdem was für eine Karte du has (wie gross und wie kompliziert aufgebaut sie ist) wäre in deinem Fall auch eine Greedy Best First Search sinnvoll.
Wenn du tatsächlich eine sehr grosse und sehr komplex aufgebaute Karte hast, sodass es schwer oder zu aufwändig ist eine genauere Heuristik zu erstellen, dann kannst du bei deinen Weg über Backtracing mit Hilfe des Bresenhams Algorithmus (den kennst du vieleicht vom Linien ziehen in Grafikbearbeitungsprogrammen; es ist das selbe Prinzip, ausser dass du jeweils die Länge der erzeugten Linie + Länge bis zum Ziel + Länge bis zum Start berechnest) noch etwas optimieren, aber der A* alleine sollte eigentlich in den meisten Fällen reichen.
Mit Zitat antworten
  #17 (permalink)  
Alt 16-06-2009, 00:16
Benutzerbild von onemorenerd onemorenerd
  Moderator
Links : Onlinestatus : onemorenerd ist offline
Registriert seit: Mar 2005
Ort: Berlin
Beiträge: 9.471
onemorenerd wird schon bald berühmt werdenonemorenerd wird schon bald berühmt werden
Standard

PHP: Datastructures - Manual

Zwischenergebnisse niemals in der DB speichern!
Mit Zitat antworten
  #18 (permalink)  
Alt 16-06-2009, 11:19
Besth
 Registrierter Benutzer
Links : Onlinestatus : Besth ist offline
Registriert seit: Mar 2006
Beiträge: 249
Besth ist zur Zeit noch ein unbeschriebenes Blatt
Standard

naja das problem ist ja - ich muss ja nach den kosten sortieren. und immer das feld als nächstes untersuchen das die geringsten kosten hat.
mein array sieht ja dann so aus:
Code:
array {
  [0]=> array {
    [x]=> 0
    [y]=> 0
    [vorgaengerx]=> 0
    [vorgaengery]=> 0
    [f]=> 0
    [g]=> 0
    [h]=> 0
  }
  [1]=> array {
    [x]=> 0
    [y]=> 0
    [vorgaengerx]=> 0
    [vorgaengery]=> 0
    [f]=> 0
    [g]=> 0
    [h]=> 0
  }
  [2]=> array {
    [x]=> 0
    [y]=> 0
    [vorgaengerx]=> 0
    [vorgaengery]=> 0
    [f]=> 0
    [g]=> 0
    [h]=> 0
  }
}
un wie ordne ich das nun nach f? weil ich brauch ja die ganzen infos von den koordinaten un kosten ...
ach mensch ich weiß grad nich mehr weiter. ich mach ma ne pause bis heut abend ^^
danke trotzdem für die hilfe hätt nich gedacht das ich überhaupt soweit komm
__________________
Mess with the Besth, die like the rest!
Mit Zitat antworten
  #19 (permalink)  
Alt 16-06-2009, 12:01
unset
  Moderator
Links : Onlinestatus : unset ist offline
Registriert seit: Jan 2007
Ort: Düsseldorf
Beiträge: 3.782
unset befindet sich auf einem aufstrebenden Ast
Standard

Zitat:
Zitat von Besth Beitrag anzeigen
un wie ordne ich das nun nach f?
Zur not mit usort.
Mit Zitat antworten
  #20 (permalink)  
Alt 16-06-2009, 18:56
Besth
 Registrierter Benutzer
Links : Onlinestatus : Besth ist offline
Registriert seit: Mar 2006
Beiträge: 249
Besth ist zur Zeit noch ein unbeschriebenes Blatt
Standard

ok das versteh ich leider nicht wie das auf mein beispiel passt
__________________
Mess with the Besth, die like the rest!
Mit Zitat antworten
  #21 (permalink)  
Alt 16-06-2009, 19:25
Benutzerbild von onemorenerd onemorenerd
  Moderator
Links : Onlinestatus : onemorenerd ist offline
Registriert seit: Mar 2005
Ort: Berlin
Beiträge: 9.471
onemorenerd wird schon bald berühmt werdenonemorenerd wird schon bald berühmt werden
Standard

PHP-Code:
function fsort($a$b) {
    if (
$a['f'] == $b['f']) {
        return 
0;
    }
    return (
$a['f'] < $b[f]) ? -1;
}

usort($deinArray"fsort"); 
Mit Zitat antworten
  #22 (permalink)  
Alt 16-06-2009, 19:40
Besth
 Registrierter Benutzer
Links : Onlinestatus : Besth ist offline
Registriert seit: Mar 2006
Beiträge: 249
Besth ist zur Zeit noch ein unbeschriebenes Blatt
Standard

ok danke funktioniert.
ich hatte mir bis eben das hier zusammengereimt:
Code:
function sortiere ($a, $b) {
  return $a["f"] > $b["f"];
}
usort($meinarray, "sortiere");
aber deins sieht etwas komplexer aus

rein interessehalber: wenn ich jetzt noch zusätzlich nach nem 2. feld sortieren wöllte wie müsste denn der code verändert werden?
also wenn zb erst nach "f" un dann nach "g", dann nach "h" usw. (falls f bzw g gleich ist)
hab die funktion usort leider noch nicht 100%ig verstanden udn würde es gern
__________________
Mess with the Besth, die like the rest!
Mit Zitat antworten
  #23 (permalink)  
Alt 16-06-2009, 20:04
Benutzerbild von onemorenerd onemorenerd
  Moderator
Links : Onlinestatus : onemorenerd ist offline
Registriert seit: Mar 2005
Ort: Berlin
Beiträge: 9.471
onemorenerd wird schon bald berühmt werdenonemorenerd wird schon bald berühmt werden
Standard

PHP-Code:
function fghsort($a$b) {
    if (
$a['f'] == $b['f']) {
        if (
$a['g'] == $b['g']) {
            if (
$a['h'] == $b['h']) {
                return 
0;
            }
            return (
$a['h'] < $b['h']) ? -1;
        }
        return (
$a['g'] < $b['g']) ? -1;
    }
    return (
$a['f'] < $b['f']) ? -1;
}

usort($deinArray"fghsort"); 
Mit Zitat antworten
  #24 (permalink)  
Alt 16-06-2009, 20:55
jmc
 PHP Junior
Links : Onlinestatus : jmc ist offline
Registriert seit: Mar 2006
Beiträge: 868
jmc befindet sich auf einem aufstrebenden Ast
Standard

Wenn $a['f'] == $b['f'] und $a['g'] == $b['g'] dann muss $a['h'] == $b['h'] sein

Benutzt du nun A*? Warum nimmst du als Index nicht z.B. ($a << 16 | $b)? Der Zugriff wäre dadurch einiges schneller (die zwei Bitoperationen sind vernachlässigbar im Vergleich).
Sonst müsstest du ja immer alle geschlossenen und geöffneten Knoten durchsuchen, so hast du direkten Zugriff.
Mit Zitat antworten
  #25 (permalink)  
Alt 16-06-2009, 22:29
PHP-Desaster
 PHP Expert
Links : Onlinestatus : PHP-Desaster ist offline
Registriert seit: Mar 2006
Beiträge: 3.105
PHP-Desaster befindet sich auf einem aufstrebenden Ast
Standard

Zitat:
Zitat von jmc Beitrag anzeigen
Sonst müsstest du ja immer alle geschlossenen und geöffneten Knoten durchsuchen, so hast du direkten Zugriff.
Premature Optimization ist die Wurzel allen Übels oder wie war das Zitat noch gleich!

EDIT:
Ah hier: http://en.wikipedia.org/wiki/Optimiz...en_to_optimize
Mit Zitat antworten
  #26 (permalink)  
Alt 16-06-2009, 23:14
Besth
 Registrierter Benutzer
Links : Onlinestatus : Besth ist offline
Registriert seit: Mar 2006
Beiträge: 249
Besth ist zur Zeit noch ein unbeschriebenes Blatt
Standard

Zitat:
Zitat von jmc Beitrag anzeigen
Benutzt du nun A*? Warum nimmst du als Index nicht z.B. ($a << 16 | $b)? Der Zugriff wäre dadurch einiges schneller (die zwei Bitoperationen sind vernachlässigbar im Vergleich).
Sonst müsstest du ja immer alle geschlossenen und geöffneten Knoten durchsuchen, so hast du direkten Zugriff.
ja ich benutze A*. Bzw versuche ich noch es umzusetzen.
Ich versteh leider nicht was du mit Index ($a << 16 | $b) meinst.
Sry bin nich so der krasse Freak
Ich programmier gern ma in meiner Freizeit aber so das es richtig zum Programmierer reicht fehlt mir die Zeit/Lust
__________________
Mess with the Besth, die like the rest!
Mit Zitat antworten
  #27 (permalink)  
Alt 16-06-2009, 23:56
jmc
 PHP Junior
Links : Onlinestatus : jmc ist offline
Registriert seit: Mar 2006
Beiträge: 868
jmc befindet sich auf einem aufstrebenden Ast
Standard

Damit kannst du folgenden Pseudocode etwas abkürzen:
PHP-Code:
for each neighbour of node
   
if neighbour in closed
   
/*du hast einen zufälligen index also musste du alle Element in closed
     durchsuchen bis du neighbour findest (oer auch nicht) */
      
...
   else if 
neighbour in open
   
/*du hast einen zufälligen index also musste du alle Element in open
     durchsuchen bis du neighbour findest (oer auch nicht) */
      
... 
Den Index könntest du aber auch durch x und y bestimmen lassen. Da PHP bei Arrays automtisch maps erstellt haben Index und Reihenfolge im Array nicht viel miteinander zu tun. Das ist normalerweise ein Nachteil bei der Performance, hier aber kannst du das vorteilhaft nutzen.
Du baust deine Nodes in closed und open entweder so auf:
PHP-Code:
$open = Array();
...
$open[$x][$y] = Array( // Zugriff bei bekanntem x, y über $open[x][$y]
 
4// --> g
 
23// --> h
 
27// --> f
 
3// --> parent x
 
// parent y
); 
oder so:
PHP-Code:
$open = Array();
...
$open[($x << 16) | $y] = Array( // Zugriff bei bekanntem x, y über $open[($x << 16) | $y]
 
4// --> g
 
23// --> h
 
27// --> f
 
3// --> parent x
 
// parent y
); 
Und das oberer Beispiel würde zu:
PHP-Code:
for each index -> neighbour of node
   
if exists closed[index// du hast exakt einen Index zu prüfen
      
...
   else if 
exists open[index// du hast exakt einen Index zu prüfen
      
... 
Wenn man nicht optimieren soll warum nicht gleich Dijkstra oder eine IDDFS? Dann brauchst du nicht unbedingt eine genaue Heuristik und der erste Weg den du findest ist auch der nächste.
Mit Zitat antworten
  #28 (permalink)  
Alt 17-06-2009, 09:26
PHP-Desaster
 PHP Expert
Links : Onlinestatus : PHP-Desaster ist offline
Registriert seit: Mar 2006
Beiträge: 3.105
PHP-Desaster befindet sich auf einem aufstrebenden Ast
Standard

Zitat:
Zitat von jmc Beitrag anzeigen
Wenn man nicht optimieren soll warum nicht gleich Dijkstra oder eine IDDFS? Dann brauchst du nicht unbedingt eine genaue Heuristik und der erste Weg den du findest ist auch der nächste.
Das sehe ich auch so. Wenn ich mich nicht mit dem Thema auskenne, würde ich erstmal vorne anfangen.
Mit Zitat antworten
Antwort

Lesezeichen


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

Ähnliche Themen
Thema Autor Forum Antworten Letzter Beitrag
[Script] Automatisches Eintragen von Videos auf Seite Pitchriddick Apps und PHP Script Gesuche 0 19-05-2007 00:16
[Script] automatisches ausfüllen eines externen formulars crok74 Apps und PHP Script Gesuche 4 22-11-2006 10:11
[Perl] Automatisches script / dateien umbenennen radio-dreamwave Apps und PHP Script Gesuche 0 30-11-2005 23:03
automatisches script mastahjay PHP Developer Forum 9 23-11-2002 12:26
automatisches Löschen Argus SQL / Datenbanken 1 26-10-2001 21:41

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

ebiz-trader 7.5.0 mit PHP7 Unterstützung veröffentlicht
ebiz-trader 7.5.0 mit PHP7 Unterstützung veröffentlichtDie bekannte Marktplatzsoftware ebiz-trader ist in der Version 7.5.0 veröffentlicht worden.

28.05.2018 | Berni

Wissensbestand in Unternehmen
Wissensbestand in UnternehmenLebenslanges Lernen und Weiterbilden sichert Wissensbestand in Unternehmen

25.05.2018 | Berni


 

Aktuelle PHP Scripte

PHP Server Monitor

PHP Server Monitor ist ein Skript, das prüft, ob Ihre Websites und Server betriebsbereit sind.

11.09.2018 Berni | Kategorie: PHP/ Security
PHP WEB STATISTIK ansehen PHP WEB STATISTIK

Die PHP Web Statistik bietet Ihnen ein einfach zu konfigurierendes Script zur Aufzeichnung und grafischen und textuellen Auswertung der Besuchern Ihrer Webseite. Folgende zeitlichen Module sind verfügbar: Jahr, Monat, Tag, Wochentag, Stunde Folgende son

28.08.2018 phpwebstat | Kategorie: PHP/ Counter
Affilinator - Affilinet XML Produktlisten Skript

Die Affilinator Affilinet XML Edition ist ein vollautomatisches Skript zum einlesen und darstellen der Affili.net (Partnerprogramm Netzwerk) Produktlisten und Produktdaten. Im Grunde gibt der Webmaster seine Affilinet PartnerID ein und hat dann unmittelb

27.08.2018 freefrank@ | Kategorie: PHP/ Partnerprogramme
 Alle PHP Scripte anzeigen

Alle Zeitangaben in WEZ +2. Es ist jetzt 06:33 Uhr.