Problem-/Lösungsname gesucht
dedlfix
0 0 
TS
0 0 dedlfix
0 Tabellenkalk
0 0 dedlfix
2 Der-Dennis
Problem-/Lösungsname gesucht
dedlfix
AugeTach!
Die Aufgabenstellung lautet grob, einen Weg zum Ziel zu finden. Es gibt Stationen, an denen etwas erledigt werden muss. Dass ist Teilaufgabe Nummer 2. Deren Ergebnis ist, dass man Punkte verliert. Die Stationen müssen nicht unbedingt angesteuert werden, aber einige versperren den Weg zum Ziel, wobei es durchaus der Fall ist, dass es mehrere Wege über andere Stationen gibt. Andererseits kann das Ansteuern von abseits gelegenen Stationen durchaus zielführend sein, weil man an ihr Gegenstände bekommen kann (dazu gleich mehr). Hat man nämlich genügend Punkte eingebüßt, hat man verloren. Das war eins der Szenarien. Ich suche dazu Namen von äquivalenten Problemstellungen oder Lösungsansätzen, damit ich die Suchmachine genauer füttern kann, um mir das notwendige Wissen anzueignen.
Es gibt auch noch zwei abweichende Szenarien. Eins lautet, alle Stationen oder einen gewissen Prozentsatz zu besuchen und deren Aufgaben zu erledigen. Das andere ist, eine bestimmte Menge Dinge aufzusammeln, die in den Sektoren zwischen den Stationen liegen. Dazu muss man einige der Stationen erledigen, die den Weg dahin versperren.
Für Teilaufgabe 2, also das was an den Stationen zu erledigen ist, muss man seine Gegenstände (die bestimmte Stärken und Schwächen haben) in der möglichst besten Kombination einsetzen, so dass sie entweder wenig Punkte verlieren, oder aber dass man so erfolgreich ist, dass man einen neuen Gegenstand bekommt. Gegenstände kann man auch verlieren (wenn deren Punktzahl aufgebraucht ist), solange es nicht alle eigenen sind, bevor man das Szenario erledigt hat. Man muss nämlich vor dem Starten wählen, welche Gegenstände (und Zusatzausrüstungen) man mitnehmen möchte. Für diese Aufgabe kann es nötig sein, mehrere Runden zu absolvieren, wobei die Gegenstände jeweils ausgetauscht werden können oder mit der Zusatzausrüstung aktiv und passiv verbessert werden können. Die Aufgabenstellung ändert sich dabei nicht, also wird nicht für jede Runde neu kombiniert, nur deren Punkte-Restmenge verringert sich. - Ich denke, hierfür wird man wohl mit Brute Force alle Kombinationen durchprobieren müssen.
dedlfix.
-
Moin!
Soll das ein Name für die Spieler sein oder ein Name, den die Entwickler für das Problem benutzen?
Wenn für die Entwickler, dann könntest Du hier irgendwo fündig werden: Cisco: "Route Selection", auch "Administrative Distance". Das Problem ähnelt sich ja durchaus, nur dass es eben nicht um Punkte sondern um Zeit oder Geld geht.
Jörg Reinholz
-
Hallo und guten Morgen,
Wenn für die Entwickler, dann könntest Du hier irgendwo fündig werden: Cisco: "Route Selection", auch "Administrative Distance". Das Problem ähnelt sich ja durchaus, nur dass es eben nicht um Punkte sondern um Zeit oder Geld geht.
Oder um die verlangte Umleitung über den Anschlussknoten der NSA & Co.
scnr
Grüße
TS -
Tach!
Soll das ein Name für die Spieler sein oder ein Name, den die Entwickler für das Problem benutzen?
Oftmals haben sich in der Informatik/Mathematik Namen zu einer bestimmten Problematik gebildet. Beispielsweise „Problem des Handlungsreisenden“. Ich möchte eigentlich ein Programm schreiben, dem man die Daten zum Szenario eingibt und das dann den Weg hindurch sucht. Und dafür brauch ich Ideen, wie ich gängige Verfahren finde, um nicht alles neu zu erfinden.
Wenn für die Entwickler, dann könntest Du hier irgendwo fündig werden: Cisco: "Route Selection", auch "Administrative Distance". Das Problem ähnelt sich ja durchaus, nur dass es eben nicht um Punkte sondern um Zeit oder Geld geht.
Das sieht mir auf den ersten Blick noch nicht passend aus (ich schau da aber auch noch mal genauer hin). Die in der Netzwerktechnik enthaltenen Abzweige zu den Geheimdiensten müssen ja ständig angelaufen werden und nicht nur wenn es sich für den Payload-Empfänger lohnt. ;) Ansonsten ist so ein Netz eigentlich auch ohne Sackgassen aufgebaut.
dedlfix.
-
-
Hallo und guten Morgen,
bist Du jetzt unter die Spieleentwickler gegangen und willst jetzt meine Spielidee umsetzen? Da fehlt wirklich nicht viel an der Beschreibung, nur, dass bei mir auch noch virtual Reality bzw. real Virtuality gg eingebaut ist, Du also noch im wahren Leben rumgeistern musst und echte Menschen triffst, die dir (beim Spiel) entweder helfen können, oder aber dich benutzen können, um zu gewinnen. Wie im echten Leben also.
Und für das Ganze benötigt man umfassende Kenntnisse in der Graphentheorie.
https://de.wikipedia.org/wiki/Graphentheorie
http://www.mathematik.uni-wuerzburg.de/~schwartz/Lehre/Graphentheorie/SkriptGraphentheorieSchwartz.pdfHattest Du diese Anregung gesucht?
Grüße
TS-
Tach!
bist Du jetzt unter die Spieleentwickler gegangen und willst jetzt meine Spielidee umsetzen?
Weder noch, es geht sozusagen um die Gegenseite. Wie löst man ein gegebenes Szenario effektiv und vielleicht so gar noch effizient? Aber Effizienz ist nicht so wichtig, Hauptsache es wird erfolgreich gelöst.
Und für das Ganze benötigt man umfassende Kenntnisse in der Graphentheorie.
https://de.wikipedia.org/wiki/Graphentheorie
http://www.mathematik.uni-wuerzburg.de/~schwartz/Lehre/Graphentheorie/SkriptGraphentheorieSchwartz.pdfHattest Du diese Anregung gesucht?
Vermutlich ja. Abgesehen davon, dass die Graphentheorie möglicherweise die Grundlage für die Lösungsfindung bildet, gibt es da auch etwas, was schon spezieller auf das Szenario passt?
dedlfix.
-
Hallo und guten Morgen,
bist Du jetzt unter die Spieleentwickler gegangen und willst jetzt meine Spielidee umsetzen?
Weder noch, es geht sozusagen um die Gegenseite. Wie löst man ein gegebenes Szenario effektiv und vielleicht so gar noch effizient? Aber Effizienz ist nicht so wichtig, Hauptsache es wird erfolgreich gelöst.
Und für das Ganze benötigt man umfassende Kenntnisse in der Graphentheorie.
https://de.wikipedia.org/wiki/Graphentheorie
http://www.mathematik.uni-wuerzburg.de/~schwartz/Lehre/Graphentheorie/SkriptGraphentheorieSchwartz.pdfHattest Du diese Anregung gesucht?
Vermutlich ja. Abgesehen davon, dass die Graphentheorie möglicherweise die Grundlage für die Lösungsfindung bildet, gibt es da auch etwas, was schon spezieller auf das Szenario passt?
Naja, der deutsche Begriff für das, was Du suchst, ist wohl "Expertenlösung" für die Betriebsablaufsteuerung (Arbeitsvorbereitung).
Ich habe sowas ähnliches mal gemacht als "Variantenkalkulation" für die Rolladenfertigung. Du hast nur ein paar Parameter voregeben und das Programm suchte sich dann aus der stetig wachsenden Datenbank alle abhängigen Größen zusammen. Da ging es um das passende Material, Arbeitszeit, Personalbedarf, Schnittoprimierung (Vermeidung von Verschnitt), Maschinennutzung, usw. in Abhängigkeit von Ausführungswunsch, Maßen, Einkaufspreisen, usw.
Die Auflösung in Optionen und Alternativen, Baugruppen usw., Vermeidung zirkulärer Verläufe.
Graphentheorie war damals noch ein Fremndwort für mich.Grüße
TS
-
-
-
Moin Moin,
da sollte es einen Solver für geben.
Ob es passt oder nicht, selbst entscheiden da ungeprüft Solver
Die Suchmaschine gibt für dieses Stichwort "Automatisches Problemlösen" vielleicht brauchbares aus.
Wo ist Gabis Freund ? Gabis Freund ist in 6 Jahren 8 mal so alt wie Gabis Kind und in 13 Jahren 4 mal so alt wie dieses Kind.
Der Solver konnte die Frage beantworten.
-
Tach!
da sollte es einen Solver für geben.
Das sieht mir nach einem Oberbegriff für solcherart Lösungsfindern aus. Aber muss man dem nicht auch noch Kenntnisse zum Problem beibringen und/oder einen haben, der speziell auf das Problem passt?
Ob es passt oder nicht, selbst entscheiden da ungeprüft Solver
Die Suchmaschine gibt für dieses Stichwort "Automatisches Problemlösen" vielleicht brauchbares aus.
Ich schau mir das auf alle Fälle mal genauer an.
dedlfix.
-
Hallo,
Wo ist Gabis Freund ? Gabis Freund ist in 6 Jahren 8 mal so alt wie Gabis Kind und in 13 Jahren 4 mal so alt wie dieses Kind.
Der Solver konnte die Frage beantworten.
Da würde mich ja die Formulierung der Antwort schon interessieren. War sie im ganzen Satz, nur zwei Worte oder wie?
Gruß
Kalk-
Wo ist Gabis Freund ? Gabis Freund ist in 6 Jahren 8 mal so alt wie Gabis Kind und in 13 Jahren 4 mal so alt wie dieses Kind.
Der Solver konnte die Frage beantworten.
Da würde mich ja die Formulierung der Antwort schon interessieren. War sie im ganzen Satz, nur zwei Worte oder wie?
Ausgehend von dem hier ist die Wahrscheinlichkeit am Größten, dass er gerade in seiner Bude pennt. Und seine Freundin treibts mit nem anderen - er tut mir leid.
-
Hallo,
er tut mir leid.
In Zeiten von Patchworkfamilien ist die Frage auch nicht beantwortbar. Ich habe mich daher auch nur für die Formulierung interessiert, die der Solver gegeben hat.
Gruß
Kalk
-
-
-
-
Ich suche dazu Namen von äquivalenten Problemstellungen oder Lösungsansätzen, damit ich die Suchmachine genauer füttern kann, um mir das notwendige Wissen anzueignen.
Da fallen mir ein:
Nick
-
Tach!
Ich suche dazu Namen von äquivalenten Problemstellungen oder Lösungsansätzen, damit ich die Suchmachine genauer füttern kann, um mir das notwendige Wissen anzueignen.
Da fallen mir ein:
Sicher? Ich will nicht wieder zum Ausgangspunkt zurück, sondern von A nach B und dort ist das Szenario gelöst. Außerdem will ich nur die Stationen besuchen, die mir was nützen und nicht alle. Der Handelsreisende hat außerdem Zugang zu allen Orten und muss keine Reihenfolge einhalten, um den Weg freizubekommen.
Das schau ich mir an, da sind ja auch noch weitere Links.
dedlfix.
-
Tach,
Sicher? Ich will nicht wieder zum Ausgangspunkt zurück, sondern von A nach B und dort ist das Szenario gelöst.
das wäre dann erstmal ein Hamilton-Pfad in einem gewichteten Graphen und ich erinnere mich, dass die Lösung daür war, einen weiteren Knoten hinzuzufügen, der die Entfernung 0 zu allen anderen Knoten hat und den dann als Startpunkt für ein TSP zu nehmen (aber Vorsicht, das mit den Graphen war nichts mit dem ich mich viel beschäftigt habe).
Außerdem will ich nur die Stationen besuchen, die mir was nützen und nicht alle.
Das heißt, dass du beim Optimieren Schnitte betrachten musst
Der Handelsreisende hat außerdem Zugang zu allen Orten und muss keine Reihenfolge einhalten, um den Weg freizubekommen.
Das führt zu einem gerichteten Graphen.
Das schau ich mir an, da sind ja auch noch weitere Links.
Ich musste zuerst an das knapsack problem denken, aber deins scheint noch weitere Komplexitätsebenen zu haben, aber vielleicht gibt es in dem Bereich ja etwas das weiterhilft.
mfg
Woodfighter
-
-
-
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.
-
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.
-
Hallo dedlfix,
grundsätzlich verstehe ich jetzt grob, wie die Randbedingungen sind. Das Einzige, was mir noch nicht ganz klar ist, ist folgendes:
Es gibt keinen zweiten Versuch. Weder beim Lösen einer Station noch beim Weg an sich. Es muss in einem Durchlauf erfüllt werden.
Das ist auch genau der Knackpunkt an der Sache, woraus sich auch die am ehesten passenden Stichwörter ergeben. Was heißt "kein zweiter Versuch"?
Szenario A: Du kannst beliebig oft dasselbe Spielfeld verwenden und benötigst die perfekte Lösung => Solver (u.a. Brute-Force)
Szenario B: Du kannst beliebig oft dasselbe Spielfeld verwenden und benötigst eine optimale Lösung => Optimierer
Szenario C: Du kannst nur einmal dasselbe Spielfeld verwenden und benötigst eine perfekte Lösung => bei höherer Komplexität praktisch unmöglich
Szenario D: Du kannst nur einmal dasselbe Spielfeld verwenden und benötigst eine optimale Lösung => Statistik, Reinforcement Learning, "Big Data", etc...
Die Szenarios gelten für statische Spiele, d.h. Aktion A löst immer Aktion B aus. Wenn da Dynamik mit reinkommt wird's natürlich noch deutlich komplexer.
Im Hinblick auf die Kleingewinne ist es aber durchaus sinnvoll, den bestmöglichen Weg zu finden.
Heißt "bestmöglich" jetzt "die absolut beste Lösung" oder "eine optimale Lösung, die der besten sehr nahe kommt"? Wenn ersteres: Je nachdem, wie komplex "das Spiel" an sich ist, ist das praktisch ausgeschlossen. Jede zusätzliche Bedingung geht allgemein als Fakultät mit in die Rechenzeit ein, das kann selbst bei einfach erscheinenden Problemen schnell jeglichen derzeit möglichen Rahmen sprengen (auch hier sei wieder auf TSP verwiesen).
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.
Es passt auch nicht wirklich. Und trotzdem passt es super. Diese ganzen Optimierungsgeschichten sind wirklich gut, weil man sie grundsätzlich wirklich universell einsetzen kann. Ich muss aber gestehen, dass ich da ganz schön lang dran zu knabbern hatte... Und mich trotzdem immernoch nicht wirklich auskenne.
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.
Ich denke ja, aber auch schon vorher. Aus eigener Erfahrung kann ich Dir nur sagen, dass man da am besten einfach nen bisschen liest und dann drüber nachdenkt und irgendwann kommt dann so ein "Heureka!".
Wenn euch aber nochwas einfällt, immer her damit.
Hab mich da in letzter Zeit ausgiebig mit beschäftigt (beschäftigen müssen). Wenn mir was einfällt sag ich Dir Bescheid. Und sonst kannst Du natürlich auch immer gern fragen.
Gruß, Dennis
-
Tach!
Szenario C: Du kannst nur einmal dasselbe Spielfeld verwenden und benötigst eine perfekte Lösung => bei höherer Komplexität praktisch unmöglich
Szenario D: Du kannst nur einmal dasselbe Spielfeld verwenden und benötigst eine optimale Lösung => Statistik, Reinforcement Learning, "Big Data", etc...
Das Spielfeld wird ausgewürfelt und ich kann es mir anschauen, um mir eine Strategie zu überlegen, wie ich mich da durchschlagen kann. Das ist aufwendig, weil eine Menge zu berechnen ist. In der Form kommt es nicht wieder, es gibt nur andere, anders ausgewürfelte. Die Stationen sind an anderen Plätzen, lediglich Anfang und Ende sind immer an festen Positionen.
Die Szenarios gelten für statische Spiele, d.h. Aktion A löst immer Aktion B aus. Wenn da Dynamik mit reinkommt wird's natürlich noch deutlich komplexer.
Das Feld inklusive der Stationen ändert sich nicht mehr, wenn man es einmal bekommen hat. Das dürfte die Definition von statisch erfüllen.
Im Hinblick auf die Kleingewinne ist es aber durchaus sinnvoll, den bestmöglichen Weg zu finden.
Heißt "bestmöglich" jetzt "die absolut beste Lösung" oder "eine optimale Lösung, die der besten sehr nahe kommt"? Wenn ersteres: Je nachdem, wie komplex "das Spiel" an sich ist, ist das praktisch ausgeschlossen. Jede zusätzliche Bedingung geht allgemein als Fakultät mit in die Rechenzeit ein, das kann selbst bei einfach erscheinenden Problemen schnell jeglichen derzeit möglichen Rahmen sprengen (auch hier sei wieder auf TSP verwiesen).
Das werde ich dann sehen, wenn ich es implementiere. Die absolute beste wäre optimal, einfach nur irgendwie erfolgreich durchkommen wäre auch eine mögliche Lösung, wenn die andere zu rechenintensiv ist.
dedlfix.
-
Hallo dedlfix,
Das Spielfeld wird ausgewürfelt und ich kann es mir anschauen, um mir eine Strategie zu überlegen, wie ich mich da durchschlagen kann.
Das ist schon mal gut und darauf zielte auch eine meiner Fragen ab. Wenn das gesamte Spielfeld sowie die ganzen Randbedingungen (in dem Fall z.B. die Gegenstände an den einzelnen Stationen) von Anfang an bekannt sind hast Du mit den Optimierungsverfahren gute Möglichkeiten, eine zufriedenstellende Lösung zu finden.
Das ist aufwendig, weil eine Menge zu berechnen ist.
So, wie ich mir das vorstelle, wahrscheinlich sogar viel zu aufwändig, wenn Du mit sowas wie Brute-Force darauf losgehen willst. In dem Zusammenhang finde ich die Sessa-Legende immer schön anschaulich, auch wenn man es sich intuitiv kaum vorstellen kann.
In der Form kommt es nicht wieder, es gibt nur andere, anders ausgewürfelte. Die Stationen sind an anderen Plätzen, lediglich Anfang und Ende sind immer an festen Positionen.
Wenn es nicht wiederkommt, spräche das meiner Meinung nach am ehesten für Reinforcement-Learning-Ansätze oder vergleichbares. Voraussetzung ist dafür natürlich, dass Du den Algorithmus gewissermaßen "trainieren", also z.B. 1000 Runden spielen kannst, ohne dass dies einen Einfluss auf ein zukünftiges Spiel hat (darauf zielte meine andere Frage ab).
Das Feld inklusive der Stationen ändert sich nicht mehr, wenn man es einmal bekommen hat. Das dürfte die Definition von statisch erfüllen.
Ja, genau. Auch wenn ich mich mit der "statisch/dynamisch"-Definition in diesem Bereich immer noch nicht anfreunden kann. Allgemein geht es dabei darum, ob Du alle folgenden Aktionen "im Voraus sehen" kannst (statisch; gute Lösung wahrscheinlich) oder ob eine Aktion wiederrum eine Aktion auslöst, d.h. Du musst erst etwas tun, damit Du "anschließend sehen" kannst, wie sich die Randbedingungen (oder das Spielfeld oder was-auch-immer) geändert haben (dynamisch; einigermaßen gute Lösungen sind, wenn überhaupt, nur durch statistische Methoden möglich). Wie gesagt, ich finde diese Definition nicht glücklich, hoffe aber, Du weißt, worauf ich hinaus möchte. Noch "schlimmer" als "dynamisch" wird's bei praktisch allen Ansätzen nur noch, wenn man nicht mal die Möglichkeit für ein Training des Algorithmus hat, weil jeder Versuch Auswirkungen auf den nächsten hat (wie vorher schon beschrieben).
Heißt "bestmöglich" jetzt "die absolut beste Lösung" oder "eine optimale Lösung, die der besten sehr nahe kommt"? Wenn ersteres: Je nachdem, wie komplex "das Spiel" an sich ist, ist das praktisch ausgeschlossen. [...]
Das werde ich dann sehen, wenn ich es implementiere. Die absolute beste wäre optimal, einfach nur irgendwie erfolgreich durchkommen wäre auch eine mögliche Lösung, wenn die andere zu rechenintensiv ist.
So wie ich mir Deine Aufgabenstellung mittlerweile vorstelle bin ich mir relativ sicher, dass Du eine allgemeingültige, beste Vorgehensweise nicht wirklich finden kannst, sofern denn überhaupt eine existiert (für eine einzelne Runde könnte das unter Umständen aber möglich sein). Ich selbst wundere mich z.B. immer wieder (und das wird wahrscheinlich auch immer so bleiben), dass Fakultäten völlig unintuitiv sind und ich mir, obwohl ich es eigentlich wissen müsste bzw. weiß, einfach immer wieder vor Augen führen muss, wie schnell die wirklich steigen (Beispiel: Ein Plot von WolframAlpha mit Potenz/Polynom/Fakultät; man beachte besonders die Abzisse, schon bei einer "Komplexität" (Algorithmus-Komplexität bzw. -Laufzeit könnten übrigens weitere Stichwörter sein) von 7 geht die Fakultät buchstäblich "durch die Decke"; das Sessa-Beispiel habe ich zum Vergleich auch mal reingepackt).
Ansonsten könnte ich mir vor dem Hintergrund, was Du bisher zu der Problemstellung gesagt hast, vorstellen, dass Du beispielsweise spielübergreifend Reinforcement-Learning-Ansätze verwenden kannst und pro Runde sowas wie Ant-Colony-Optimization verwendest (die intern übrigens auch meist wieder auf RL-Ansätze zurückgreift; Ant-Colony muss auch nicht das am besten passende Verfahren sein, ich persönlich finde diese Bionik-Ansätze aber immer wieder faszinierend und sie funktionieren erstaunlich gut).
Aus Erfahrung wäre ein weiterer Tipp, sich das Spielprinzip genau anzuschauen und Dir selbst Regeln aufzustellen (ähnlich wie in diesem Beispiel, als es um Schere-Stein-Papier ging, auch wenn die Intention da eine andere war; wenn Du solche Regeln wie A schlägt B (bzw. A ist (fast) immer die bessere Wahl im Gegensatz zu B) findest, minimiert das die Komplexität meist enorm und hilft sehr beim "Training"). Erster Schritt ist immer die Minimierung der Komplexität (unter anderem durch das Aufstellen einfacher Regeln).
Als letztes Stichwort für eine Recherche hätte ich noch das Stichwort Fuzzylogik für Dich. Das löst zwar nicht das eigentliche Problem, kann Dir aber bei einer einzelnen Entscheidungsfindung (bei Dir: z.B. an einer Station) sehr hilfreich sein.
Gruß, Dennis
-
Tach!
Danke für deinen weiteren Informationen. Ich schau mir das an. Momentan weiß ich aber noch gar nicht, ob ich das Projekt überhaupt anfange oder ob ich nicht mit etwas Übung ein Bauchgefühl bekommen kann um die Situationen selber zu lösen. Ich prokrastiniere schon genügend Dinge. Zumindest hab ich mir dann einen theoretischen Überblick verschafft, wie man sowas lösen kann.
dedlfix.
-
Hallo dedlfix,
[...] ob ich nicht mit etwas Übung ein Bauchgefühl bekommen kann um die Situationen selber zu lösen.
bestimmt. Es ist erstaunlich, wozu wir in der Lage sind - in den meisten Bereichen können Algorithmen bzw. Rechner einfach (noch) nicht mithalten.
Ich prokrastiniere schon genügend Dinge.
Geht mir (leider) ähnlich.
Zumindest hab ich mir dann einen theoretischen Überblick verschafft, wie man sowas lösen kann.
Das schadet ja auch nie.
Gruß, Dennis
Ps: Anstatt des WolframAlpha-Plots aus dem letzten Beitrag wollte ich eigentlich diesen logarithmisch aufgetragenen Plot zeigen (u.a. Brute-Force-Ansatz), weil man so den Zuwachs noch besser sehen kann. Das aber nur als Nachtrag und der Vollständigkeit halber, hat ja auch nichts direkt mit einer möglichen Lösung zu tun.
-
Hallo
… Ich prokrastiniere schon genügend Dinge. …
Da war doch noch was …?
Ah, ja! Gestern bei Fefe gefunden.
Amerikanische Wissenschaftler haben herausgefunden: Das Anschauen von Katzenvideos tut gut.
„The pleasure they got from watching cat videos outweighed any guilt they felt about procrastinating.“
Tschö, Auge
--
Es schimmerte ein Licht am Ende des Tunnels und es stammte von einem Flammenwerfer.
Terry Pratchett, „Gevatter Tod“
-
-
-
-