Aufsammeln Algorithmus oder try and error

Neue Frage »

lenny1234 Auf diesen Beitrag antworten »
Aufsammeln Algorithmus oder try and error
Meine Frage:
Ich soll ein Programm schreiben, in dem ein Roboter in einem n * m Feld zufällig dort in den Kästchen verteilte Gegenstände aufsammelt. Der Roboter kann nur nach rechts oder nach unten gehen, es soll der Weg gefunden werden, wo er die meisten Gegenstände aufsammeln kann.

Meine Ideen:
Ich weiß, dass es (n+m) über m Möglichkeiten gibt, Wege zu gehen. Muss ich jetzt jeden dieser Millionen Wege abtesten, oder gibt es einen Algorithmus, um den besten Weg zu finden, bzw untaugliche Wege von vorneherein auszuschließen?
HAL 9000 Auf diesen Beitrag antworten »

Sei die Maximalanzahl an aufsammelbaren Gegenständen in einem Feld mit Zeilen und Spalten.

Schauen wir uns mal die Gegenstände letzten -ten Spalte an, die seien in den Zeilen (also von unten nach oben) zu finden. Dann besteht die Rekursion



wobei man setzt: Klar, je mehr Gegenstände wir in der letzten Spalte "erwischen" wollen (Anzahl ), desto weiter oben muss der Eintrittspunkt in diese Spalte liegen, und desto weniger Nach-unten-Schritte darf es vorher bis einschließlich -te Spalte geben. Iterationsgleichung (*) gilt auch für keinen Gegenstand in dieser letzten Spalte, dann ist einfach sowie dann .

Startpunkt der Rekursion ist einfach für alle .


Ist vom Aufwand her jedenfalls drastisch geringer als .


Ach ja, zum optimalen Weg: Die ermittelte Maximumstelle von (*) bedeutet, dass ein Wegpunkt eines möglichen optimalen Weges ist.



EDIT: Ach Quatsch, geht viel leichter - es ist

mit Startwerten ,

dabei kennzeichnet , dass auf Feld ein Gegenstand liegt - sonst (ohne Gegenstand) sei
lenny1234 Auf diesen Beitrag antworten »
Aufsammeln Algorithmus
Ich habe jetzt einige Zeit darüber nachgedacht, und obwohl ich deine Lösung nicht ganz verstehe, hat sie mich auf eine Idee gebracht:

Ich stehe, wie du gesagt hast, auf dem Feld 0 = f(m,0)

dann habe ich 2 Möglichkeiten, nach rechts oder nach unten.

Ich wähle diejenige, die mir mehr j, also mehr Gegenstände bringt.

Also: f(m,n) = max( f rechts, f unten) + (j bisdahin)

So gehe ich durch das Feld bis zum Ziel, jedes belegte Feld wird markiert und im nächsten Durchlauf nicht mehr verwendet.

Dann kommt der nächste Durchlauf: Ich wähle nun am Start den 2. Weg, da der erste bereits benutzt wurde. Wieder alles durch bis zum Ziel.

Im 3. Durchlauf beginne ich auf dem Feld, welches dem Zielfeld am nächsten ist und noch nicht benutzt wurde. Dann wieder dasselbe bis Ziel usw.

Die jeweiligen Ergebnisse und Wege werden gespeichert und immer nur das beste behalten.

Ist das in etwa der Algorithmus, den du gemeit hast?
lenny1234 Auf diesen Beitrag antworten »
RE: Aufsammeln Algorithmus
Habe jetzt noch deinen Nachtrag gelesen, ich glaube, ich habe deinen Algorithmus verstanden, dann kanns jetzt losgehen mit dem Programmieren Big Laugh
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »