Schnellsten Weg durch Checkpoints in einem Grid finden (Optimierung)

Moin,
ich stehe vor einer kleinen Herausforderung und bin mir nicht sicher, ob ich die bestmögliche Lösung gefunden habe.

Ich habe ein zufällig großes Grid, mit zufällig vielen und zufällig angeordneten Checkpoints und einer zufälligen Startposition, wobei die Startposition sich immer außerhalb des Grids befindet und nicht fix ist.
Ich möchte den schnellstmöglichen Weg durch die Checkpoints berechnen. Meine Idee dazu ist, sich zu einer der Ecken zu bewegen, um ein Feld versetzt in das Feld mit der Analyse hineingehen und dann jeweils ein Feld links und rechts nach den Checkpoints zu scannen, die dann in eine Liste eingetragen werden. Diese Liste kann ich dann einfach ablaufen (Siehe Anhang). Ist das das Optimum?

Und wenn jetzt sich mal der Fall ergibt, daß sich die Checkpoints z.B. oben konzentrieren und unten nur beim Einstieg ein paar Checkpoints sind und ich einer davon sich zwar auch unten neben dem Einstieg befindet, aber zwei Felder von mir entfernt, dann ginge ich also zuerst nach oben um dann wieder für einen Checkpoint runtergehen zu müssen, anstatt ihn gleich mit auf dem Weg nach oben mitzunehmen um dort anschließend zu bleiben.
Da bin ich mir auch nicht sicher, wie ich vorgehen soll. In Kauf nehmen, da die Wahrscheinlichkeit vielleicht so gering ist, daß sich der Aufwand die Weganalyse zu ändern nicht lohnt?

Ein anderer Punkt wäre noch der Einstieg. Das Grid kann sehr groß werden, meistens bestimmt das 10-fache von der Beispielgrafik, wenn nicht noch größer. Wenn ich in der Mitte zwischen den Ecken starte, habe ich einen weiten Weg. Den Weg zu einer der Ecken in Kauf nehmen, oder einen Weg durch die Mitte des Grids suchen und versuchen irgendwie dann alle Checkpoints mitzunehmen?

Ist das Grid vorher bekannt, bzw kannst du vorher eine Analyse laufen lassen oder ist das ein blinder Läufer, der immer nur die umliegenden Felder kennt?
Und sollen immer alle Checkpoints durchlaufen werden?

Wenn du die Checkpoints "vorher" kennst würde ich das ganze in Quadranten unterteilen und für die jeweils eine "Dichte" an Checkpoints berechnen.
Dann erstellst du eine Hierarchie der Quadranten beginnend mit dem Startpunkt. Und begibst dich dann zu dem nächstgelegenen größten Quadranten und durchläufst diesen.

Das könnte ein Fall für den A*-Algorithmus sein.

Eine C# Implementierung von mir existiert hier im Forum
Spiel in minimaler Anzahl Zügen erreichen

Das könnte ein Fall für den
> sein.

Eine C# Implementierung von mir existiert hier im Forum

Könntest du bitte den Link hier posten. Ich erhalte bei der Foren Suche momentan:
Fatal error: Allowed memory size of 67108864 bytes exhausted (tried to allocate 71 bytes) in /var/www/vhosts/mycsharp.de/httpdocs/wbb2/acp/lib/class_db_mysql.php on line 83

Ist der Beitrag gemeint?

Spiel in minimaler Anzahl Zügen erreichen

Edit: Sir Rufo war schneller. 😁
Edit2: Wenn ich "A*" ins Suchfeld eingebe, erhalte ich ebenfalls eine solche Fehlermeldung. Liegt evtl. am "*"?

Ja, das gesamte Spielfeld samt Checkpoints ist vorher bekannt. Ich habe blöderweise vergessen zu erwähnen, daß das Spielfeld nicht zwingen rechteckig sein muss. Es hat aber niemals Inseln.

A* war doch ein Pathfinding Algorithmus, oder habe ich was falsches in Erinnerung? Frage, da alle Checkpoints durchlaufen werden sollen.

Dies ist wohl eine Mischung aus A* und Travelling Salesman Problem, s.a. Shortest path between two points through N checkpoints in a matrix.

Da PierreDole noch erwähnt hat, dass das Problem weit aus Größer sein kann:

On a typical PC, which search algorithm would you choose, BFS, DFS, IDS, A*, or IDA*? Why? Hint: which is larger, L or the average branching factor B? (5 points) DFS is the most suitable, and actually almost all Sudoku search program use DFS. B can be in the range of 9×53 so B >> L. Hence BFS and A* will have serious memory problem on a typical PC. [...]

Siehe http://www.cs.cmu.edu/afs/andrew/course/15/381-f08/www/homework/hw1-sol.pdf Seite 2 e.