# Alorithmus zur Findung einer Tür im dunklen



## Binary.Coder (22. Okt 2009)

Hallo zusammen,

sitze an folgender Aufgabe und komme nicht weiter.







Also ich komme immer auf 4*n im Worstecase. Vielleicht ist das auch der Denkfehler.
Wenn Worstecase 4n ist, vielleicht muss man dann bei der O-Notation eins darüber sein?

Und zur Verbesserung fällt mir wirklich nichts ein. 

Würde mich über jegliche Hilfe, Hinweise und Tipps sehr freuen.

Besten Gruß und Dank

Binary


----------



## ARadauer (22. Okt 2009)

sagen wir n ist 4, wie viele Schritte brauchst du?
links, zurück, rechts, zurück = 4
2 links, 2 zurück,  2 rechts, 2 zurück = 8
3 links, 3 zurück,  3 rechts, 3 zurück = 12
4 links, 4 zurück,  4 rechts, 4 zurück = 16
gefunden... das heißt aber nicht dass du jetzt 16 Schritte gebraucht hast. Sondern 4+8+12+16 =40

Ich denke es ist O(4n!)


----------



## ARadauer (22. Okt 2009)

oder doch nicht... blödsinn...


----------



## Gonzo17 (22. Okt 2009)

Ich weiss zwar nicht, was das O() bedeutet, aber im schlimmsten Falle muss man doch 4*(1+2+...+(n-1)) + 3n Schritte laufen (die letzten 3 Schritte läuft man ja durch die Tür und nicht wieder zurück zum Startpunkt ).

@ ARadauer: Wie du von der vorletzten Zeile auf die letzte Zeile kommst verstehe ich nicht ganz. ???:L


----------



## 0x7F800000 (22. Okt 2009)

Binary.Coder hat gesagt.:


> Also ich komme immer auf 4*n im Worstecase.


Und wie kommst du auf sowas? :autsch:



			
				Aradauer hat gesagt.:
			
		

> Ich denke es ist O(4n!)


wtf?!?

@Binary.Coder: wieviele Schritte musst du machen, wenn die Tür n entfernt ist?

+1 links, 1 zurück, 1 rechts, 1 zurück
+2 links, 2 zurück, 2 rechts, 2 zurück
+4*3
+4*4
+4*5
+4*6
+...
+4*(n-1)
+n
=4*(1+2+3+...+(n-1))+n=2*n(n-1)+n
=O(n^2)

Leuts, verdammte scheiße, der kleine Gauß hat sowas im Kindergarten gelöst... ;(


----------



## Gonzo17 (22. Okt 2009)

In deiner Rechnung fehlt doch was. 



> +1 links, 1 zurück, 1 rechts, 1 zurück
> +2 links, 2 zurück, 2 rechts, 2 zurück
> +4*3
> +4*4
> ...



Das muss doch am Ende "+ 3*n" heissen. Schließlich kann man ja im blödestens Fall erstmal n Schritte in die falsche Richtung laufen, muss dann n Schritt zurück laufen, um dann in n Schritten endgültig das Ziel zu erreichen. 

Und wäre auch cool, wenn mir einer erklären könnte, was was O(x) bedeutet ???:L


----------



## 0x7F800000 (22. Okt 2009)

Gonzo17 hat gesagt.:


> Das muss doch am Ende "+ 3*n" heissen. Schließlich kann man ja im blödestens Fall erstmal n Schritte in die falsche Richtung laufen, muss dann n Schritt zurück laufen, um dann in n Schritten endgültig das Ziel zu erreichen.


ObdA trete der blödeste Fall nie ein... Ob da 0 oder 3*0 steht, ist letztendlich eh egal, es geht doch nicht um diesen Blinddarm, sondern um die entscheidende Summe.


> Und wäre auch cool, wenn mir einer erklären könnte, was was O(x) bedeutet ???:L


Landau-Symbole ? Wikipedia


----------



## Unregistriert (23. Okt 2009)

Der oben beschriebene Algorithmus wirkt ja ziemlich naiv. Bekommt man das Problem auch in O(n) gelöst. Wie sähe das aus?


----------



## bygones (23. Okt 2009)

Unregistriert hat gesagt.:


> Der oben beschriebene Algorithmus wirkt ja ziemlich naiv. Bekommt man das Problem auch in O(n) gelöst. Wie sähe das aus?


laut schreien "lasst mich rein"

warten wo die tuer aufgeht

zur tuer laufen


----------



## ARadauer (23. Okt 2009)

> Wie sähe das aus?


licht aufdrehen.


----------



## Landei (23. Okt 2009)

Der Algorithmus ist ineffektiv, weil man ja jedesmal nur eine zusätzliche Position absucht. Wahrscheinlich ist es am besten, die "Amplitude" jedesmal um einen festen Faktor f erhöhen. Dann findet man die Tür in der Entfernung n beim 2*ln(n)/ln(f)-ten Versuch, man macht also O(ln(n)²) Schritte, oder sehe ich das falsch?


----------



## Marco13 (23. Okt 2009)

Aus dem Bauch raus:

Wenn man einen Array hat, und dort n Elmente einfügen will, dann kann man:
- Bei jedem eingefügten Element einen um k Elemente größeren Array anlegen, die alten Daten dort reinkopieren, und das neue Element ans Ende legen
ODER
- Jedes mal wenn der Array voll ist den Array um einen bestimmten _Faktor_ vergrößern (z.B. die Größe verdoppeln)

Beim ersten Verfahren hat das Einfügen von n Elementen eine Laufzeit von O(n²). (wegen des Umkopierens)
Beim zweiten Verfahren hat das Einfügen von n Elementen eine Laufzeit von O(n).

Übertragen auf dieses Beispiel könnte mal jemand (der gerade mehr Zeit hat) durchrechnen, was rauskommt, wenn man die Anzahl der Schritte nicht jedes mal um 1 erhöht, sondern die Anzahl der Schritte jedes mal verdoppelt. Mir deucht da könnte O(n) rauskommen... :reflect:


EDIT: @Landei: (no comment)


----------



## 0x7F800000 (23. Okt 2009)

Pfh, O(n) ist doch billig: man ziehe die Schuhe aus, und stelle sie beide auf 0.
Dann wiederhole man abwechselnd folgende Aktionen:

zum rechten Schuh springen, einen schritt nach rechts machen, wand absuchen, schuh um 1 nach rechts verschieben
zum linken Schuh springen, einen schritt nach links machen, wand absuchen, schuh um 1 nach links verschieben
bis man die Tür gefunden hat. Am ende hat man höchstens (2n-1) Schritte gemacht. Sprünge zählen nicht. Der Aufwand ist dann O(n).


----------



## Unregistriert (23. Okt 2009)

Sehr gute Idee. Vielen Dank!


----------



## Painii (23. Okt 2009)

0x7F800000 hat gesagt.:


> Pfh, O(n) ist doch billig: man ziehe die Schuhe aus, und stelle sie beide auf 0.
> Dann wiederhole man abwechselnd folgende Aktionen:
> 
> zum rechten Schuh springen, einen schritt nach rechts machen, wand absuchen, schuh um 1 nach rechts verschieben
> ...



Nicht jeder ist so sportlich dass er beliebig weit springt. 

Das mit dem festen Faktor hört sich sinnvoll an (ich würd wohl eher quadratisch vorgehen : Wenn ich am Ausgangspunkt stehe gehe ich n^2 Schritte nach rechts/links, suche alle Positionen bis ((n-1)^2)+1 Richtung Mitte ab, wenn ich die Tür nicht hab in die nächste Richtung, dann erhöh ich mein n um eins und fang von vorne an.

Nach n=4 würd ich dann aber erstmal ne Pause machen.
Und nach n=5 oder 6 würd ich die Sache abblasen und nach Hause gehen.
So toll kanns hinter der Tür nicht sein.


----------



## 0x7F800000 (24. Okt 2009)

Painii hat gesagt.:


> Nicht jeder ist so sportlich dass er beliebig weit springt.


Der RAM ist es...


----------



## Tharsonius (26. Okt 2009)

0x7F800000 hat gesagt.:


> Und wie kommst du auf sowas? :autsch:
> 
> 
> wtf?!?
> ...




Das Ergebnis passt zwar, die Herleitung ist leider noch etwas falsch 

Im Worstcase ist die Tür auf der Seite wo man zuletzt hin geht. Das heißt bei n schritten entfernt ergibt sich folgende Reihe:

n    Anzahl der Schritte     Gesamtschritte
1          3                       3
2          7                       10
3          11                      21
4          15                      36
...

Ich brauche ja, wenn ich die Tür gefunden habe nicht wieder zur Mitte zurück laufen. Daher habe ich bei n=1 nur 3 Schritte. Bei n=2 sind es 7, weil ich erst einen zurück zur Mitte muss, dann 2 in die eine, wieder zur Mitte und nochmal 2 zur anderen Seite laufen muss.


Ergo benötige ich also
3 + 7 + 11 + 15 .... Schritte oder anders geschrieben

(4*1-1) + (4*2-1) + (4*3-1) + (4*4-1) + ... + (4*(n-1)-1) + (4*n-1) Schritte

= (4*1)+(4*2)+(4*3)+ ... (4*(n-1))+(4*n) -n Schritte
Hier habe ich die -1 (welche n mal abgezogen werden herausgezogen)

= (4 * (1+2+3+...+(n-1)+n) ) - n Schritte
Ich habe die 4 herausgezogen.

= (4 * (n * (n+1)/2) ) - n  = (2*n*(n+1))-n =  2n^2+2n-n = 2n^2+n


Ich benötige als für eine Tür in n Schritten Entfernung schlimmstenfalls 2*n^2+n Schritte um sie zu finden.

Für die Aufwandsabschätzung wird ein Multiplikator mit Konstanten vernachlässigt und bei n^2 ist ein +n ebenfalls uninteressant. Daher ergibt sich als Aufwand für den Algorithmus ein O(n^2).


----------



## 0x7F800000 (26. Okt 2009)

Dass ich nicht den worst case, sondern den best-case betrachte, hat Gonzo17 doch schon bemängelt...


Gonzo17 hat gesagt.:


> Das muss doch am Ende "+ 3*n" heissen. Schließlich kann man ja im blödestens Fall erstmal n Schritte in die falsche Richtung laufen, muss dann n Schritt zurück laufen, um dann in n Schritten endgültig das Ziel zu erreichen.


Und da bei der Abschätzung sich kaum etwas ändert, heißt es nach wie vor:


0x7F800000 hat gesagt.:


> ObdA trete der blödeste Fall nie ein...



Was du gerechnet hast, verstehe ich nicht... was bedeuten die vielen Zahlen?

```
1 3 3
2 7 10
3 11 21
4 15 36
```


----------



## Tharsonius (27. Okt 2009)

0x7F800000 hat gesagt.:


> Was du gerechnet hast, verstehe ich nicht... was bedeuten die vielen Zahlen?
> 
> ```
> 1 3 3
> ...



Da ist mir leider die Formatierung verloren gegangen. :-(

Die erste Spalte gibt das n an, die zweite Spalte die zusätzlichen Schritte und die dritte Spalte die Gesamtschritte.

2 7 10 steht für n=2, 7 zusätzliche Schritte, 10 Gesamtschritte im Worstcase


----------

