Problem-/Lösungsname gesucht

[Der-Dennis]

Hallo dedlfix,

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?

Die beiden Punkte sind wichtig, um Dir passende Stichwörter geben zu können.

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 Du den besten Weg (bzw. die beste Lösung) finden möchtest, wirst Du wohl um sowas wie Brute-Force oder Branch-and-Bound nicht herumkommen. Das Problem bei dieser Art Problemstellung ist halt immer, dass man nur sagen kann, das man die beste Lösung gefunden hat, wenn alle anderen Lösungen schlechter sind (es gibt Ausnahmen, z.B. wenn aufgrund bestimmter Randbedingungen weitere Lösungen absolut sicher ausgeschlossen werden können; meist läuft es aber darauf hinaus, dass man gar keinen richtigen Algorithmus mehr braucht, weil das Problem durch die gegebenen Randbedingungen schon praktisch gelöst ist). Diese Art von Lösungsalgorithmen wird im Allgemeinen - wie an anderer Stelle schon gesagt - Solver genannt (Solver finden im Rahmen der Rechengenauigkeit die beste Lösung).

Wenn Dir eine optimale Lösung ausreicht (und mehrere, voneinander abhängige Runden zur Lösungsfindung zugelassen sind) spricht man statt von Solvern meist von Optimierern, welche Metaheuristiken verwenden. Wenn ein Optimierer nach längstens unendlicher Zeit die beste Lösung finden kann, ist es eine Mischung aus Optimierer und Solver (das ist fast immer der Fall, wenn eine beste Lösung existiert).

Ich schmeiß einfach mal ein paar Optimierungsalgorithmen in den Raum, die ich selbst schon verwendet habe und zu Deiner Prolemstellung passen könnten, vielleicht hilft es ja: Nächster Nachbar, Evolutionäre Algorithmen (dabei insbesondere Genetische Algorithmen), Ameisenalgorithmus; von den Stichwörtern und dem Stichwort "Metaheuristik" aus findet man auch sehr viel mehr.

Wenn es darüber noch hinausgehen soll helfen Dir vielleicht die Stichwörter Selbstoptimierung oder Bestärkendes Lernen (reinforcement learning) weiter. Auch bei den Algorithmen zur Künstlichen Intelligenz (artificial intelligence) findet man gute Ansatzpunkte, die man auch auf vergleichsweise einfachere Probleme anwenden kann. Sogar die Sortierverfahren haben manchmal Ansätze, die man für die Lösungssuche gebrauchen kann.

Geht es Dir eher um (regelbasierte) Architekturen kannst Du Dir mal SOAR oder ähnliche Sachen ansehen. Im Soar Tutorial 2 wird z.B. was Pac-Man-ähnliches gebaut, das könnte Deiner Problemstellung schon relativ nahe kommen. (Allgemein kann ich von Soar übrigens abraten, die Syntax ist schrecklich...)

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. Allgemein ist es so, dass (wie sonst meistens auch) die Implementierung der Algorithmen relativ leicht ist und schnell geht. Das größte Problem besteht bei komplexeren Problemen meist in der Gewichtung der Zielfaktoren (Laufzeit, Ergebnis, etc.) oder in der Bestimmung, wie gut das erhaltene Ergebnis tatsächlich ist (also sowas wie die Fitnessfunktion beim EA, wobei das bei Dir aufgrund der schon vorgegeben Punkte kaum das Problem sein dürfte).

Und um nochmal auf den Anfang zurückzukommen: Die Suche nach einer Lösung für das "Problem des Handlungsreisenden" hat viele Lösungsansätze hervorgebracht, auch einige der zuvor beschriebenen. Von daher passt das Stichwort schon. Und es ist grundsätzlich auch egal, ob der Handlungsreisende im Kreis läuft, eine Strecke entlang, ob er seinen persönlichen Trainingsplan optimieren oder die besten Brötchen backen will - das Prinzip ist immer das gleiche. So verwenden beispielsweise einige Navis eine abgewandelte Form des Ameisenalgorithmus, um den Weg zu finden. Und das ist ziemlich genau Deine Problemstellung, auch wenn dort keine Punkte für Gegenstände abgezogen werden, dafür aber z.B. für Mautstraßen ;-)

Gruß, Dennis

Ps: Mögliche Stichwörter zum Weitersuchen in fett.