A* und Dijkstra-Algos in PHP

[TobWen]

Schniff, dann sind meine Ferien schon wieder zu Ende :-(

Naja, in der Zeit kann ich ja die Datenbank mit den Koordinaten fertig machen.

[Lennie]

gegen den 10. enden meine ferien. bis dahin muss ich aber meine kapazitätenn anders nutzen. zum einen wäre es ja zu überlegen wie es dieses programm genau macht und was dagegen spräche den algorythmus einfach zu übernehmen bzw. in php zu implementieren.

[TobWen]

EVENTUELL könnte man den Code ja auch nach C für Linux portieren und im Hintergrund ausführen.

Aber in PHP ausführen wäre schon genial, vorallem, weil ich die Sprache verstehe :-))

[Lennie]

Ich glaube das mit der umwandlung auf linux wäre eine ganz gute idee, wobei man auch einfach einen windows server nutzen könnte, und sich damit die ganze arbeit spart ^^. könnte aber ein problem werden was ich noch garnicht betrachtet habe. timeout.

wo wir grad dabei sind, wieso nicht gleich den routenplaner von db.de nutzen?!?

[TobWen]

Dazu müsste man aber Zugang zum Server haben ... lokal auf meinem klappt das, mein Hoster würde mir in den Hinter treten :-)

[closure]

Hi,

oder in c++ implementieren mit der unterstützung der wunderbaren
bgl.

A* wird nicht out of the box angeboten aber das ist leicht zu modellieren
mit dem was man hat.

Von php würde ich bei vielen daten absehen.

greets

[Lennie]

Original geschrieben von closure
Von php würde ich bei vielen daten absehen.

Wieso? spricht was ausser dem timeout dagegen? das wäre ja noch zu umgehen. ich denke es geht um eine webanwendung, und ich weis nicht ob das umlagern der abfrage auf ein linux script die sache beschleunigt.

[TobWen]

Von C++ hab ich noch weniger Plan, als von C.
Allerdings sieht BGL ziemlich geil aus. Darf ich dich PMen?

[Lennie]

den normalsterblichen oder denen den ein kasten bier zuviel kostet (oder vor der übergabe leer) ist das pm versenden hier untersagt

[TobWen]

Original geschrieben von Lennie
Wieso? spricht was ausser dem timeout dagegen? das wäre ja noch zu umgehen. ich denke es geht um eine webanwendung, und ich weis nicht ob das umlagern der abfrage auf ein linux script die sache beschleunigt.

Die Sache ist: jede gefundene Strecke kann ja von mir aus in der Datenbank gespeichert werden.

Aber ALLE möglichen Strecken im Vorfeld auszurechnen und zu speichern ist nicht sooo effizient - bezogen auf das Speichermanagment. Bezogen auf die Suchgeschwindigkeit wäre es natürlich effizient.

Aber wie gesagt, mir fehlen 9-13 Semester Informatikstudium, um Algo-Effizienz zu bewerten :-(

[TobWen]

Original geschrieben von Lennie
den normalsterblichen oder denen den ein kasten bier zuviel kostet (oder vor der übergabe leer) ist das pm versenden hier untersagt

Ich habe hier noch einen Kasten Hansa (bin Dortmunder).

[Lennie]

dazu kann ich eben nicht viel sagen. hatte momentan weder informatikstudium noch überhaupt das thema algorythmen in der schule. alles muss man selber machen.

[closure]

Hi,

@lennie
weil php bei derartigen algorithmen sehr lahm wird
Da wo du in c/c++ locker mit zeigern hantieren kannst
musst du in php mit referenzen arbeiten und dich drauf
verlassen dass der interpreter weiss was du willst.

@tobwen
ok, dann fällt c++ flach.
PM schicken geht hier nicht, bzw. nicht so ohne weiteres.

greets

[closure]

Man ihr posted ja wie die wilden.

Die komplexität von dijkstra und A* hängen vom konkreten
graphen und der darauf aufbauenden repräsentation des selben
ab. Aber für das gegebene* problem haben beide ~ optimale laufzeit.

greets


*hiermit ist nicht das problem es OP gemeint
sondern das finden des kürzesten pfades zwischen
zwei knoten.

[penizillin]

es ist immer noch ein "Algorithmus".

tobi, hast du eine konkrete aufgabe? oder willst du einfach über _eine mögliche_ implementierung sprechen?

wenn du konkreter wirst, erhält die diskussion u.u. einen sinn.