pathfinder script .. ideen oder anregungen

[Biesterfeld]

Hej,

ich suche alle möglichen strecken zwischen A und B und nehme dann die kürzeste

Dein Problem ist ein wohl bekanntes Problem der theoretischen Informatik und gehört in das Gebiet der Graphentheorie.

Jenachdem wie dein Graph aufgebaut ist, wirst du einige Fallunterscheidungen treffen müssen, wie z.B. ob die Kanten gewichtet oder ungewichtet, gerichtet oder ungerichtet sind oder ob dein Graph zyklisch oder azyklisch ist.

Soweit ich das sehe handelt es sich um einen ungerichteten, ungewichteten zyklischen Graphen. In dem Fall suchst du also wahrscheinlich nach der Iterativen Tiefensuche. Eigentlich ziemlich leicht zu implementieren.

.. aber da brauch ich ja für jeden move 1 woche rechnerleistung denn es gibt insgesamt 1 mio felder ...

Zugegeben, 10^6 Knoten is schon etwas viel, insbesondere dann wenn fast alle von ihnen einen Grad von 6 haben. Da aber die iterative Tiefensuche immer zuerst den kürzesten Weg sucht, berechnest du nicht alle möglichen Pfade sondern wirklich nur bis du den ersten kürzesten gefunden hast.

Weiterhin kannst du die Laufzeit drastisch reduzieren, indem du von vornherein Knoten von der Suche ausschließt. Immrhin scheint es sich ja in deinem Fall um Punkte auf einer Karte zu handeln, die also auch Koordinaten haben. Du kannst also z.B. nur solche Felder auf der Landkarte zulassen die innerhalb eines bestimmten Radius um A und B liegen. Und steckst nur diesen Sub-Graphen in die Suche. Achte aber darauf, dass du den Radius nicht zu klein wählst, insbesondere dass sich die beiden Umreise um A und B auch überschneiden müssen.

Zuletzt ist anzumerken, dass der Algo mit einer Komplexität von [latex]O( | V | + | E | )[/latex] läuft, wobei [latex]V[/latex] die Anzahl der Knoten ist (in deinem Fall 1000000) und [latex]E[/latex] die Anzahl der Kanten (in deinem Fall maximal 3000000). Das ist eigentlich noch in einem überschaubaren Rahmen. Bei guter Implementierung sollte das schon passen.

Beste Grüße
Biesterfeld