Alorithmus zur Findung einer Tür im dunklen

[Binary.Coder]

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]

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]

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

 

[Gonzo17]

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]

Also ich komme immer auf 4*n im Worstecase.

Und wie kommst du auf sowas? :autsch:

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]

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
+4*5
+4*6
+...
+4*(n-1)
+n

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]

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]

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

 

[bygones]

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]

Wie sähe das aus?

licht aufdrehen.

 

[Landei]

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]

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]

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]

Sehr gute Idee. Vielen Dank!

 

[Painii]

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).

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]

Nicht jeder ist so sportlich dass er beliebig weit springt.

Der RAM ist es...

 

[Tharsonius]

Und wie kommst du auf sowas? :autsch:


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... ;(

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]

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

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:

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]

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

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

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