Hirnloser Hamster im Labyrinth [gelöst]
Neue Frage »

13.03.2004, 12:59 SirJective Auf diesen Beitrag antworten »
Hirnloser Hamster im Labyrinth [gelöst]
Hallo zusammen!

Diese Aufgabe kann man eigentlich auch als Rätsel stellen, aber ich denke, die nötigen Berechnungen gehen über das Maß eines normalen Rätsels hinaus.

Ich habe ein Labyrinth, in dem ein hirnloser und fast blinder Hamster nach einem Futtervorrat sucht. Er betritt das Labyrinth auf dem mit S gekennzeichneten Feld. Der Futtervorrat ist der orangene Klecks auf dem untersten Feld. Die beiden rot markierten Felder an den Seiten sind Fallen, aus denen er nicht selbständig entkommen kann.

Wie man sieht, gibt es auf jedem Feld (ausser den Randfeldern Start, Fallen, Futter) je drei Wege, die zu anderen Feldern führen. Der Hamster kann sich nicht einmal merken, aus welcher Richtung er auf ein Feld gekommen ist, und entscheidet sich mangels weiterer Informationen (und seiner Unfähigkeit, die Nachbarfelder zu sehen) zufällig für eines der drei Nachbarfelder. Kommt er bei seiner Odysee auf das Startfeld, geht er von dort den einzig gangbaren Weg: wieder zurück (hinaus in seien Käfig darf er erst, wenn er das Futter gefunden hat).

Die Frage ist nun, wie hoch die Wahscheinlichkeit ist, dass der Hamster den Futtervorrat findet, ohne in eine der beiden Fallen zu laufen.

Den Heimweg betrachten wir ein andermal, wie gehen also davon aus, dass der Hamster beim Futter hocken bleibt und sich erstmal die Backen vollhaut.

Wie geht man das an?

Gruss,
SirJective

PS: Ich hatte die Aufgabe komplizierter gestellt, als ich das wollte. Die Hervorhebung gibt an, wo's einfacher wird. Außerdem sind mir tödliche Fallen doch etwas zu grausam. Sie halten ihn jedoch so fest, dass er das Fallenfeld nicht verlassen kann.
25.03.2004, 18:29 SirJective Auf diesen Beitrag antworten »
@Moderator: Verschiebung?
Da anscheinend niemand diese "Aufgabe" lösen will, interessiert sich vielleicht jemand für das "Rätsel". Erscheint es sinnvoll, diesen Thread ins Rätselbrett zu verschieben? Die Lösung des Rätsels beinhaltet Berechnungen mit 11x11-Matrizen, sind die zumutbar?

Gruss,
SirJective
25.03.2004, 18:31 sommer87 Auf diesen Beitrag antworten »
RE: @Moderator: Verschiebung?
OK, danke für den Tipp.

Ist VERSCHOBEN in die Rätsel-Ecke smile

Vielleicht hast du da mehr erfolg mir dem Rätsel Augenzwinkern
28.03.2004, 22:20 Steve_FL Auf diesen Beitrag antworten »

die Lösung würde ich gerne sehen Augenzwinkern
Ich hatte noch keine Matrizenberechnungen und noch keine Stochastik in der Schule, aber interessieren würde mich die Lösung trotzdem smile

Ich bin gespannt, wer das löst...
kommt wahrscheinlich nur ein Student in Frage

mfg
29.03.2004, 19:24 SirJective Auf diesen Beitrag antworten »
Hinweise zur Loesung
Dann mach ich mal den Anfang.

Das Zauberwort lautet "Markov-Kette". Egal wie weit der Hamster schon gelaufen ist, sein naechster Zug haengt allein davon ab, wo er sich gerade befindet. Wenn sich der Hamster auf einem bestimmten Feld befindet, gibt es fuer jedes Feld des Labyrinths eine festgelegte Wahrscheinlichkeit dafuer, dass er sich auf dieses Feld bewegt. Befindet er sich am Startfeld, dann ist die Wahrscheinlichkeit gleich 1, dass er sich um ein Feld nach unten bewegt. Befindet er sich in einer Falle oder beim Futter, wird er mit Wahrscheinlichkeit 1 dort bleiben. Die Wahrscheinlichkeit, eines der anderen Felder zu betreten, ist 0.
Auf dem Feld unter dem Startfeld sieht es so aus, dass die drei benachbarten Felder jeweils die Wahrscheinlichkeit 1/3 haben, und alle anderen 0.Nun fragt man sich, wie wahrscheinlich es ist, in genau zwei Schritten ein bestimmtes Feld zu erreichen. Hier kommt nun die Stochastik ins Spiel: Die Wahrscheinlichkeit, von irgendeinem Feld A in genau zwei Schritten auf irgendein Feld C zu kommen, ist die Summe ueber alle Felder B von ("Wahrscheinlichkeit von A in einem Schritt nach B zu kommen" mal "Wahrscheinlichkeit von B in einem Schritt nach C zu kommen").

Fragt man nun nach weiteren Wahrscheinlichkeiten, wird diese Summe immer laenger. Es gibt aber einen weiteren Weg. Wir fassen die Wahrscheinlichkeiten, von einem Feld auf ein anderes zu kommen, als Matrix auf. In der Komponente A,B steht dann die Wahrscheinlichkeit, in einem Schritt vom Feld A aufs Feld B zu kommen. Diese Matrix heisst "Uebergangsmatrix" und wir bezeichnen sie mit Q.

Wir starten nun mit einer "Anfangsverteilung" des Hamsters, die ein Vektor mit 11 Komponenten ist (fuer jedes Feld eine). Da er sich anfangs auf dem Startfeld befindet, steht in der entsprechenden Komponente eine 1, in allen anderen eine 0.

Um mit diesen Schreibweisen zu berechnen, mit welcher Wahrscheinlichkeit sich der Hamster nach einem Schritt wo befindet, multiplizieren wir Q mit unserem Vektor, und erhalten einen neuen Vektor. Der sagt uns, wo sich der Hamster mit welcher Wahrscheinlichkeit nach einem Schritt aufhaelt. Multiplizieren wir Q mit diesem neuen Vektor, erhalten wir den "Wahrscheinlichkeitsvektor", der uns angibt, wo sich der Hamster nach zwei Schritten befindet.

Wer mir bis hierher folgen konnte, fuer den wird es nun nicht mehr schwer sein, anzugeben, wie man ausrechnet, wo sich der Hamster nach 100 Schritten befindet. Treibt man diese Berechnung ins Unendliche, dann erhalten wir das gesuchte Ergebnis: Die Wahrscheinlichkeit, dass der Hamster irgendwann das Futter findet, ohne dabei in die Falle zu tappen.

Gruss,
SirJective
31.03.2004, 18:23 Martin Auf diesen Beitrag antworten »

sag mal SirJective ab welcher Klasse muss man denn das verstehen??

Ich kann dir bis jetzt nicht wirklich folgen aber mich würd schon irgendwie interessieren was rauskommt *g*
 Anzeige 
 
01.04.2004, 03:27 Ben Sisko Auf diesen Beitrag antworten »

Zitat:
Original von Martin
sag mal SirJective ab welcher Klasse muss man denn das verstehen??

Ich kann dir bis jetzt nicht wirklich folgen aber mich würd schon irgendwie interessieren was rauskommt *g*


Ich denke, dass man Markov-Ketten nicht in der Schule behandelt (berichtigt mich, wenn´s falsch ist). Aber andererseits sind die doch gar nicht so schwer zu verstehen, wenn man ein bisschen Stochastik kann, oder?

Wenn´s dich interessiert, und du ein bisschen googlen willst, der Begriff "stochastische Matrix" hängt auch damit zusammen.

Gruß vom Ben
01.04.2004, 22:45 SirJective Auf diesen Beitrag antworten »
Gelöst?
Ui, ist mir gar nicht aufgefallen, das die Aufgabe gelöst ist!?

Wie Ben schon sagte, in der Schule bekommt man das nicht. Da wird man höchstens mit der Frage gequält, mit welcher Wahrscheinlichkeit der Hamster nach 2 Zügen wo ist. Denn das kann man noch mit einem Wahrscheinlichkeitsbaum lösen.

Aber was soll's, es kommt 1/6 raus. Die beiden Fallen teilen sich den Rest, d.h. deren Wahrscheinlichkeit ist je 5/12.

Gruss,
SirJective
04.04.2004, 22:55 Toxman Auf diesen Beitrag antworten »

@ Sirjective:

Ich hab die Markov-Kette nicht in der Schule gelernt, mache aber in einem Mathe-Seminar mit, indem wir damit gearbeitet haben.
Ich hab mir mal die 11*11 Matrix aufgemalt, das ganze mit dem Startvektor multipliziert und das dann ein paar mal gemacht. Es ist auch jedes Mal ein stochastische Matrix rausgekommen nur leider hat die zu viele Löcher, d.h. ein paar ZUständ werden nicht erreicht. Könntest du vielleicht mal deine Übergangsmatrix mit Bennenung zeigen? Ich sehe irgendwie bei mir keinen Fehler.
Mit welchem Programm hast du die Berechnungen gemacht? Oder macht es die Spaß, eine 11*11 Matrix ein paar 10mal mit einem Wahrscheinlichkeitsvektor zu multiplizieren. :P

Toxman
06.04.2004, 13:51 SirJective Auf diesen Beitrag antworten »

Zitat:
Original von Toxman
@ Sirjective:

Ich hab die Markov-Kette nicht in der Schule gelernt, mache aber in einem Mathe-Seminar mit, indem wir damit gearbeitet haben.
Ich hab mir mal die 11*11 Matrix aufgemalt, das ganze mit dem Startvektor multipliziert und das dann ein paar mal gemacht. Es ist auch jedes Mal ein stochastische Matrix rausgekommen nur leider hat die zu viele Löcher, d.h. ein paar ZUständ werden nicht erreicht. Könntest du vielleicht mal deine Übergangsmatrix mit Bennenung zeigen? Ich sehe irgendwie bei mir keinen Fehler.
Mit welchem Programm hast du die Berechnungen gemacht? Oder macht es die Spaß, eine 11*11 Matrix ein paar 10mal mit einem Wahrscheinlichkeitsvektor zu multiplizieren. :P

Toxman


Zur Angabe der Übergangsmatrix brauchen wir erstmal eine Nummerierung der Zustände.
code: 
1:
2:
3:
4:
5:
6:
7:
8:
9:

         1
   2     3      4
      5      6
          7
      8      9
         10
         11

Mit dem Wert p = 1/3 müsste die Matrix dann so aussehen (jede Spalte gibt die Übergangswahrscheinlichkeit von dem Feld auf die Nachbarfelder an)

code: 
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:

 -) 1 2 3 4 5 6 7 8 9 1011
 1) 0 0 p 0 0 0 0 0 0 0 0
 2) 0 1 0 0 p 0 0 0 0 0 0
 3) 1 0 0 0 p p p 0 0 0 0
 4) 0 0 0 1 0 p 0 0 0 0 0
 5) 0 0 p 0 0 0 0 p 0 0 0
 6) 0 0 p 0 0 0 0 0 p 0 0
 7) 0 0 0 0 0 0 0 p p 0 0
 8) 0 0 0 0 p 0 p 0 0 p 0
 9) 0 0 0 0 0 p p 0 0 p 0
10) 0 0 0 0 0 0 0 p p 0 0
11) 0 0 0 0 0 0 0 0 0 p 1

So oder so ähnlich müsste die Matrix aussehen.

Diese Matrix habe ich als Variable Q in Maple eingegeben und dann nach Q^200 gefragt. Alle Felder ausser den drei Endzuständen haben dann schon extrem kleine Wahrscheinlichkeiten.
Die erste Spalte des Ergebnisses ist der gesuchte Übergangsvektor vom Startfeld.

Gruss,
SirJective

PS: Ich hab garantiert keine Lust, 11x11-Matrizen von Hand zu multiplizieren *g*
06.04.2004, 18:16 Toxman Auf diesen Beitrag antworten »

Etwas komisch finde ich deine Matrix schon:

z.b.:
(- Das Futterfeld ist nicht absorbierend)
- Von der 3 komm ich nicht auf die 5
(- 11 ist absorbierend)

Hast du genau diese Matrix mit Maple berechnet?
Eigentlich müssten doch 2,4 und 11 als absorbierende Zustände höhere Wahrscheinlichkeiten haben als der Rest und das Futter dürfte in etwa Null haben, da es den Hamster sicher auf die 3 schickt.

Toxman

Edit:
:wall: mir ist da was aufgefallen: Ich hab die Zeichnung immer so gelesen, dass der Hamster unten anfängt und nach oben zum Ziel muss.
07.04.2004, 17:17 SirJective Auf diesen Beitrag antworten »

Zitat:
Original von Toxman
Etwas komisch finde ich deine Matrix schon:


Ich kann nicht garantieren, dass die von mir angegebene Matrix richtig ist, da ich sie gestern "aus dem Stand" zusammengeschrieben habe.

Der Hamster startet oben bei dem S-Feld. Er will nach unten zu dem Futterfeld mit dem orangenen Klecks.
Haben sich damit die Probleme mit dieser Matrix erledigt?

Man kann natürlich nun fragen: Wenn der Hamster sich jetzt den Bauch vollgeschlagen hat, mit welcher Wahrscheinlichkeit kommt er wieder zurück zum Startfeld. Nun ist das Startfeld absorbierend und das Futterfeld schickt ihn sicher ein Feld nach oben. Die übrigen Wahrscheinlichkeitsvektoren bleiben unverändert.

Gruss,
SirJective

PS: Der Heimweg wird deutlich gefährlicher. Wenn ich damals richtig gerechnet hab und ich mich jetzt richtig erinnere, dürfte der Wert irgendein kleines siebzehntel sein.
Neue Frage »
Antworten »



Verwandte Themen

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


MatheBoard » Sonstiges » Rätsel & Wettbewerbe » Hirnloser Hamster im Labyrinth [gelöst]