hallo alle miteinander:

ich habe ein problem, und bevor ich es löse, wollte ich fragen, ob es da schon nützliche module zu gibt.
ich habe eine karte mit verschiedenen knoten. jeder knoten ist im moment über eine bidirektionale verbindung mit mind. einem weiteren knoten verbunden. die verbindungen sind alle gleichwertig, allerdings können die knoten unterschiedliche wertigkeiten haben (je nach nutzervorgabe). ich möchte nun den kürzesten weg zwischen zwei punkten finden. das problem daran ist, dass es > 5.000 knoten sind die mit > 13.000 verbindungen untereinander verbunden sind (ungeordnet).
hat jemand schon mal mit so was zu tun gehabt? ich bin in dem zusammenhang auf den begriff graphentheorie gestossen, habe aber zu wenig mathematischen/informatischen background um das genauer verfolgen zu können.

mein erster ansatz war. dass ich mich abwechselnd vom start und vom ziel aus in einzelnen schritten sternförmig ausbreite, um dann die route über den ersten, gemeinsam gefundenen knoten zu nehmen, das währe schon mal ein anfang. allerdings habe ich die befürchtung, dass das bei weit auseinander liegenden punkten sehr viel rechenzeit in anspruch nehmen könnte.

Du koenntest dir mal Bio::Coordinate::Graph angucken. Ansonsten such mal nach Dijkstra, von dem gibts nen Algorithmus zum Berechnen des kuerzesten Pfades.

Ich würde gerne noch einige Randbedingungen kenne. Ist der Graph statisch oder ändert der sich laufend. Wie oft sollen die kürzesten Wege berechnet werden (selten oder oft)?

Bei statischem Graphen und häufigen Abfragen würde es sich vermutlich lohnen, alle kürzesten Wegstrecken im Voraus zu berechnen und in einer großen DB-Tabelle (ca. 12,5 Millionen Wege) abzulegen. Eine konkrete Wegabfrage kann dann schnell per DB-Lookup beantwortet werden.

Bei dynamischem Graphen wird wohl ein aufwändiger iterativer Ansatz (Breitensuche) notwendig sein. Bereits besuchte Knoten (merhrfach erreichbar) können dabei ausgelassen werden, da sie ja über Umwege gefunden wurden.

der graph an sich ist statisch. allerdings kann der benutzer festlegen, dass er nur knoten ab einem gewissen schwellwert benutzen möchte.

nachdem ich jetzt mal breitensuche bei wiipedia nachgeschaut habe, weiss ich auch, dass das wohl mein erster ansatz war. wobei es doch imho schneller gehen müsste, wenn ich mich nacheinander vom start und vom ziel ausbreite. dann müssten die beiden bäume ja irgendwann aufeinander treffen.

[quote=Taulmarill,19.10.2005, 13:47]wobei es doch imho schneller gehen müsste, wenn ich mich nacheinander vom start und vom ziel ausbreite. dann müssten die beiden bäume ja irgendwann aufeinander treffen.[/quote]
Im Prinzip sollte Dein outside in Verfahren schneller sein. Das hängt konkret aber von der Topologie des Graphen ab. Außerdem bin ich nicht sicher, ob der erste Knoten, der die beiden Suchgraphen verbindet wirklich das Optimum darstellt - vermutlich muss dort noch etwas weiter gesucht werden.

Da die Suche von einer Seite algorithmisch einfacher ist, würde ich zunächst einmal damit beginnen.

Paths::Graph biete eine flexiblere Datenstruktur als das oben genannte BIO::... Modul.
Der Dijkstra-Algorithmus steht als shortest_path-Methode zur Verfügung.

[quote=Taulmarill,19.Oct..2005, 13:47]allerdings kann der benutzer festlegen, dass er nur knoten ab einem gewissen schwellwert benutzen möchte.[/quote]
Man kann das als Veränderung des Graphen interpretieren/implemetieren. (oder man patched die vorgefertigte Methode in diesem Sinne)

danke für eure hilfe, ich werde mir die module noch alle mal näher anschauen, aber das bioperl modul sieht schon mal gar nicht schlecht aus. wichtig währe mir noch zu wissen, ob die algorithmen immer den besten weg finden, oder sich nur annähern.

achja, damit in zusammenhang währe es interessant zu wissen, ob ihr ein modul kennt, mit dem ich das handlungsreisenden-problem näherungsweise lösen kann. also die beste route für eine reise mit einigen wegpunkten berechnen.

Ich benutze in BBBike den A*-Algorithmus, der meiner Meinung nach Dijkstra überlegen ist. Du könntest theoretisch den Code verwenden, aber ich fürchte, er ist zu wenig allgemein gehalten.

Eine primitive Version des Handlungsreisendenproblem kann man unter Verwendung von Algorithm::Permute oder List::Permutor recht schnell schreiben. Allerdings funktioniert dieser Brute-Force-Ansatz nur für wenig Zwischenpunkte (9 oder 10 oder so).