Pfad in int[][] finden

[michel126]

Hallo,

ich möchte in einem zweidimensionalen Array, welches mit Kosten befüllt ist, den Pfad mit den geringsten Kosten finden.

Gestartet wird in der letzten "Zeile" mit den geringsten Kosten (sollten mehrere "Felder" in der letzten Zeile die gleichen Kosten haben, wird die mit dem kleinsten Index ausgewählt.
Von diesem Feld ausgehend kann der Pfad jetzt rückwärts von unten nach Oben rekonstruiert werden. Das nächste Feld im Pfad ist das Nachbarfeld darüber minimalen Kosten. Haben mehrere Nachbarfelder dieselbe Kosten, wird nach folgender Prorität ausgewählt: mitte-links-rechts (vertikal) bzw. mitte-unten-oben (horizontal).

Zurückgegeben wird ein int[], das für jede Zeile den Index des auszuwählenden Feldes des Pfades speichert.

Aktuell fange ich alle "Randfälle" ab. Hat jemand eine Idee, wie das elegant zu lösen ist?

Danke und Grüße

michel126

 

[Marcinek]

Poste deine Lösung und wir sagen dir, was man verbessern kann.

Ansonsten

Single Source Shortest Path

Generischer Kürzeste Pfade Algorithmus

Dijekstra

 

[Gast2]

A* Implementierungen die du dir mal ansehen kannst:
AStar.java - a-star - Project Hosting on Google Code
Koders Code Search: AStar.java - Java

 

[Andi_CH]

Was ist ein Pfad durch einen 2D Array? Soll ich mir das als Spielfeld vorstellen? so immer von einem Feld auf das Andere?
Die Anzahl möglicher Wege ist im allgemeinen Fall unendlich gross.
Wo ist der Anfang
Wo das Ende?

Ist das Problem so überhaupt lösbar? Die Antwort kann ich gegen: NEIN

Ausserdem ist das wohl (noch?) kein Java spezifisches Problem

 

[Marcinek]

Was ist ein Pfad durch einen 2D Array? Soll ich mir das als Spielfeld vorstellen? so immer von einem Feld auf das Andere?
Die Anzahl möglicher Wege ist im allgemeinen Fall unendlich gross.
Wo ist der Anfang
Wo das Ende?

Ist das Problem so überhaupt lösbar? Die Antwort kann ich gegen: NEIN

Ausserdem ist das wohl (noch?) kein Java spezifisches Problem

Das Problem ist natürlich nicht unendlich 😉 Und natürlich ist es Lösbar ==> Floyed All Pair shortest Path in n^3 wenn naiv programmiert.

(Vorrausgesetzt es ist kein Spielfeld mit einem Springer drauf. Oder einer anderen Schachfigur ;P

Und ich denke das ist eine Adjazenzmatrix.


Es ist natürlch kein Javaspeifisches Problem.

Ich denke, dass sich der TO nicht mehr hier melden wird ^^, weil wir keine Lösung präsentieren ^^