Problem-/Lösungsname gesucht

[dedlfix]

Tach!

Ich denke, hierfür wird man wohl mit Brute Force alle Kombinationen durchprobieren müssen.

Du möchtest also unter Einbeziehung bestimmter Randbedingungen (Gegenstände, Punkte, etc.) einen Weg finden.

Dazu zwei Fragen:

• Möchtest Du den besten oder einen optimalen Weg finden?
• Soll die Route in einem Durchlauf feststehen oder können mehrere, voneinander abhängige Runden gespielt und daraus die Route berechnet werden?

Also, die zuerst zitierte Vermutung betrifft das zweite Teilproblem, die bestmögliche Vorgehensweise an den Stationen zu finden. Wenig Punkte einstecken, oder aber einen neuen Gegenstand gewinnen, dann kann man eventuell auch mehr Punkte in Kauf nehmen. Es muss die beste Kombination der Gegenstände gefunden werden. Was die beste ist, kann sich auch aus dem weiteren Weg des ersten Teilproblems ergeben, denn man kann nicht auf dem Weg liegende Stationen trotzdem besuchen, wenn sich strategisch ein Vorteil ergibt, sei es durch gewonnene Gegenstände oder weitere (bisher noch nicht erwähnte) Kleingewinne, die für die Lösung des Problems zwar keine Rolle spielen, aber trotzdem erstrebenswert sind. Da dieser Aspekt der Kleingewinne nicht direkt wichtig ist, kann man ihn auch erstmal aus der Aufgabenstellung raushalten.

Die Stationenaufgabe muss rundenbasiert bis zum Abschluss gebracht werden, wenn die Station den Weg zum Ziel behindert. Oder zumindest muss eine der Stationen abgearbeitet werden, wenn mehrere davon alternative Wege blockieren.

Es gibt keinen zweiten Versuch. Weder beim Lösen einer Station noch beim Weg an sich. Es muss in einem Durchlauf erfüllt werden. Je nach Szenario und auch nach den mitgenommen Gegenständen, um die Aufgaben an den Stationen zu erfüllen (zweites Teilproblem), gibt es verschiedene Randbedingungen. Einige Gegenstände können verloren werden, die sind ersetzbar. Andere dürfen nicht kaputtgehen und müssen repariert werden, wobei die Reparatursets ebenfalls ein knappes Gut sind.

Im Prinzip reicht es, überhaupt einen Weg zu finden, ohne gänzlich auf der Strecke zu bleiben, wobei beim Verlieren der unwiederbringlichen Gegenstände quasi die gesamte Aufgabe unerfüllt ist und an der Stelle diese Lösung verworfen werden kann. Im Hinblick auf die Kleingewinne ist es aber durchaus sinnvoll, den bestmöglichen Weg zu finden.

Ansonsten bist Du doch mit dem "Problem des Handlungsreisenden" schon ganz nah dran. Das ist ein klassisches und schön anschauliches Optimierungsproblem und lässt sich auch auf viele andere Optimierungsprobleme übertragen.

Wenn ihr das sagt, dann werde ich mich da auch umstimmen lassen. Es sieht mir nur auf den ersten Blick nicht so ganz passend aus, weil mein Problem keine Rückkehr zum Ausgangspunkt nötig hat und auch optionale Sackgassen und Alternativen enthalten kann. Wenn das aber alles in vom TSP abgeleiteten Problemstellungen berücksichtigt wird, dann wäre das ja gut.

Ansonsten solltest Du Dir für den Anfang die beiden oben stehenden Fragen beantworten und zusätzlich, welches Verhältnis aus Laufzeit und Ergebnis Dir am liebsten wäre.

Hab ich das hinbekommen? Wenn nicht, dann einfach nochmal nachhaken.

Den Rest der Antwort hab ich erstmal zur Kenntnis genommen, kann ihn aber aufgrund meiner Wissenslücken noch nicht bewerten. Auch woodfighters Posting hab ich dankend gelesen, werde es aber nicht extra beantworten. Es sieht jedenfalls so aus, als ob ich genug Futter zum verdauen habe. Wenn euch aber nochwas einfällt, immer her damit.

dedlfix.