Suche schnellsten und preisgünstigsten Weg in einem 2D Array!

[Robbylein]

Hallo erstmal,

ich quäle mich jetzt schon bis zur Verzweiflung an diesem Algorithmus vielleicht hat ja wer eine Lösungsidee :confused: , wäre super nett.

Aufgabe:

Gegeben ist ein n x n Array a, welches mit gleichverteilten Zufallszahlen aus dem Bereich [ -9, ..., -1, 1, ..., 9] (also ohne 0) gefüllt ist. Ein Arrayeintrag a[j] = k bedeutet, dass dem Punkt (i, j) der Preis k zugeordnet ist. Es gilt stets a[n-1][n-1] = -9. Gesucht ist der preiswerteste Weg von links oben nach rechts unten, also vom Punkt (0, 0) zum Punkt (n-1, n-1). Dieses Array wird meiner Klasse die ich schreiben soll übergeben.

Der Preis eines Weges berechnet sich wie folgt:

Beginnend mit (0,0) werden die Preise der durchlaufenen Punkte zunächst addiert, d.h., eine negative Zahl entspricht bei ihrem ersten Auftreten einem Bonus. Allerdings kann jeder Bonus nur einmal in Anspruch genommen werden. Sobald man eine negative Zahl passiert hat, sagen wir als Beispiel die -3, verkehren sich alle Bonus-Zahlen bis zur -3 in ihr Gegenteil, d.h., jede weitere -3, die auf dem Weg durchlaufen wird (egal wo sie in a steht), wird zur 3, jede weitere -2 zur 2 und jede weitere -1 zur 1. Die übrigen Zahlen bleiben unverändert. Trifft man später auf eine -5, so werden ab sofort auch die -5 zur 5 und die -4 zur 4. Sobald man eine -9 passiert hat, zählen also alle weiteren Zahlen positiv.

Die Wege dürfen sich beliebig durch das Array schlängeln, wobei man jeweils nach links, rechts, oben oder unten gehen darf, aber nicht schräg. Es ist zulässig, mehrmals an der gleichen Stelle vorbeizukommen. Dies lohnt sich allerdings nur, wenn man dadurch einen zusätzlichen Bonus aufsammeln kann.

Daraus folgt das Endlosschleifen also im preiswertesten Weg nicht vorkommen, auch lohnt es sich nicht, zweimal durch das Ziel zu laufen.

Ausgabe in dem Format: (7,0) (0,0) (1,0) (1,1) (2,1) (2,0) (2,1) (2,2) mit Preis = -10 ( = 4 + (-2) + 2 + (-4) + (-5) + (+4) + (-9) ) (im ersten Eintrag des Weges steht kein Knoten, sondern die Weglänge)

Ich danke schonmal im vorraus

[Muadibb]

Mein erster Gedanke ist der Bellmann-Algorithmus.

Allerdings besteht das Problem, dass sich die Kosten einzelner Kanten verändern können, so dass Du beim erreichen negativer Kosten an dieser Stelle Deinen Weg neu berechnen musst.

Eventuell hilft Dir das für den Ansatz

[Robbylein]

Dankeschön für den guten Tipp !!

Ich habe es jetzt hinbekommen

[Robbylein]

Gibt es vielleicht in Java etwas womit man alle möglichen Zahlen in einem Array umändern kann?? z.B. alle Zahlen die -4 sind in +4 zu ändern.

Ich habe das jetzt durch sehr viele if abfragen hinbekommen, dadurch wird das Programm aber ziemlich unübersichtlich.

[geloescht_Newlukai]

Gibt es vielleicht in Java etwas womit man alle möglichen Zahlen in einem Array umändern kann?? z.B. alle Zahlen die -4 sind in +4 zu ändern.

Ich habe das jetzt durch sehr viele if abfragen hinbekommen, dadurch wird das Programm aber ziemlich unübersichtlich.

Wenn Du eine Klasse meinst, der Du ein Array und eine Regel gibst: sowas ist mir nicht bekannt. Warum aber iterierst Du nicht einfach drüber und multiplizierst mit -1?