Die mathematische Lösung zu einem Flash-Spiel

01.05.2008, 20:14	Siddhartha	Auf diesen Beitrag antworten »
Die mathematische Lösung zu einem Flash-Spiel Hallo. Es geht um dieses Flash Spiel. Wir haben am rechten Ufer anfangs 3 Priester und 3 Teufel. Ziel ist es alle sechs an das linke Ufer zu bringen indem wir die Fähre nutzen. Die Fähre kann maximal zwei Personen gleichzeitig tragen und mindestens eine Person muss in ihr sitzen damit sie den Fluss überqueren und auf die jeweils andere Seite fahren kann. Wenn Anzahl der Priester an einer Seite geringer ist als die Anzahl der Teufel an der Seite, dann sterben die Priester und das Spiel ist verloren. Gezählt wird jeweils die Bootsbesatzung und die Personen an Land. Jetzt strebe ich eine mathematische Lösung des Problems an. Wir starten am rechten Ufer wo 3x+3y stehen; mit Priestern als x und den Teufeln als y. Die Besatzung der Fähre liegt im Bereich [1;2]. Wenn ax an einer Seite geringer ist als by ist das Spiel verloren.(a,b in Z+) Hat jemand Rat wie ich weiter verfahren kann?
02.05.2008, 08:54	Mazze	Auf diesen Beitrag antworten »
Das ist doch ein klassisches Problem der Problemraumsuche. Man definiert sich Zustände und Aktionen und bekommt so einen Zustandsgraphen (später Baum). Was man dann tut ist Suchalgorithmen anzusetzen. Einige wären Breitensuche oder Tiefensuche. Man muss sich dann noch zusätzlich merken in welchen Zuständen man schon war und erhält einen Suchbaum, der dadurch das die Teufel und Priester endlich in Ihrer Anzahl sind, auch endlich wird (wenngleich er sehr groß sein kann). Ich würde aber das Problem direkt für beliebig viele Priester und Teufel lösen, da es der gleiche Algorithmus sein wird . Dann kann man natürlich die Bootsgröße auch variabel halten. Ich würde es so machen Zustand definieren : Ein Zustand zeichnet sich durch die Anzahl der Teufel/Priester an den Ufern A und B aus und durch die Position des Bootes und deren Fahrer. Also $\begin{eqnarray} Z_t \in \{(T_1,P_1,T_2,P_2,B_t,(B_p)_t)\} \end{eqnarray}$ $\begin{eqnarray} T_i \in \{1,...,n\}, P_i \in \{1,...,m\} \end{eqnarray}$ Dabei drückt B aus, ob der Fahrer ein Teufel oder Priester ist und $\begin{eqnarray} B_p \end{eqnarray}$ an welchem Ufer das Boot ist. Man kann ohne Einschränkung annehmen das ein Fahrerwechsel immer an der Seite wo das Boot abfährt statt findet. Das ist nur zur Vereinfachung, man könnte die Fahrer auch wechseln wenn das Boot ankommt, das hat aber für den Problemraum nur eine Umordnung zur Folge, weshalb wir ersteres annehmen. Als nächstes brauchen wir eine Zustandsüberführung , eine Aktion. Aktionen definieren : Aktionen überführen einen Zustand in einen Folgezustand. Mit $\begin{eqnarray} \triangle T, \triangle P \end{eqnarray}$ bezeichne ich die Differenz der Priester/Teufel auf den Seiten, oder anders gesprochen, die Priester die Wir benutzen. $\begin{eqnarray} A:Z_t \times (\triangle T, \triangle P,x \in \{T,P\}) \to Z_{t+1} \end{eqnarray}$ $\begin{eqnarray} A(Z_t,\triangle T,\triangle P,x) = \begin{cases}(T_1 - \triangle T + f(x,B_t),P_1 - \triangle P + g(x,B_t),T_2 + \triangle T,P_2 + \triangle P,x,B), & \text{wenn }B_t = A \\(T_1 + \triangle T,P_1 + \triangle P,T_2 - \triangle T + f(x,B_t),P_2 - \triangle P + g(x,B_t) ,x,A), & \text{wenn }B_t = B \end{cases} \end{eqnarray}$ Hierbei musst Du die Übergangsfunktion A natürlich noch einschränken. Es können nicht mehr Teufel verladen werden als da sind usw. Wichtig ist auch ob Du bereits bei der Aktion entscheidest das Du in einen falschen Zustand kommst, oder erst im betreffenden Zustand erkennst das Du einen Schritt zurück musst (eventuel auch mehr). f(x),g(x) drücken den Bootsfahrer aus. Wenn ich den Bootsfahrer wechsle, bekommt eine Seite einen dazu und die andere einen abgezogen. Das ergibt also $\begin{eqnarray} f(x,B_t)=\begin{cases}0, & \text{wenn }x = B_t\\1, & \text{wenn } B_t = T \text{ und } x = P \\ -1, & \text{wenn } B_t = P \text{ und } x = T \end{cases} \end{eqnarray}$ $\begin{eqnarray} g(x,B_t)=\begin{cases}0, & \text{wenn }x = B_t\\-1, & \text{wenn } B_t = T \text{ und } x = P \\ 1, & \text{wenn } B_t = P \text{ und } x = T \end{cases} \end{eqnarray}$ Ich bestimme mit einer Aktion also wieviele Teufel, Priester ich verlade. Das ganze wird ein wenig aufgebläht wenn man noch erlaubt das die Passagiere auf dem Boot bleiben dürfen. Das Ganze ist hier natürlich stark formalisiert. Aber prinzipiell ist die Idee immer : Zustände definieren, Zustandsübergänge definieren, Baumsuche. Wichtig ist hier aber wirklich das Du Dir die Zustände merkst in denen Du schon warst, sonst entstehen zykel. Die Frage ist natürlich ob Du schonmal sowas wie Breiten-, oder Tiefensuche behandelt hattest. Aber wie gesagt, das Problem ist klassich dafür. edit: Man muss natürlich auch einen Ziel- und Anfangszustand definieren. Sagen wir wir haben n Teufel,m Priester mit m > n und einen Teufel als Fahrer (also n + 1 Teufel), dann ist der Anfagszustand $\begin{eqnarray} Z_0 = (n,m,0,0,T,A) \end{eqnarray}$ der Zielzustand (an dem der Algorithmus terminiert) $\begin{eqnarray} Z_Z = (0,0,n + \delta(x,T),m + \delta(x,P),x,B) \end{eqnarray}$ Hierbei ist es egal wer im Boot am ende sitzt, solange das Boot auf Seite B ist. Delta ist einfach eine Abhängige vom Bootsman und der entsprechenden Gruppe. Man könnte alternativ auch zulassen das keiner im Boot sitzt.
03.05.2008, 17:18	Siddhartha	Auf diesen Beitrag antworten »
Solche Berechnungen sind mir völlig fremd... ich werde mich mal einarbeiten; vielleicht verstehe ich es ja sogar. Danke für die offenbar ausführliche Erklärung.
03.05.2008, 18:24	Mazze	Auf diesen Beitrag antworten »
Das Ganze ist nur eine Formalisierung, eines "Systematisch-alle-Möglichkeiten-durchprobieren-Verfahren". Man muss es genau aufschreiben , damit man sich mehr um die implementierung und weniger um die Problemlösung kümmern kann.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »