Zwei Smartphones ein Hochhaus, von welchem Stockwerk geht das Smartphone zuerst kaputt.

[Bashar]

Wenn es das vierte Stockwerk überlebt hat und im sechsten kaputt geht, woher weißt du dann, ob es das fünfte überlebt hätte?

Außerdem ist h/2, also praktisch nur ein Einsatz des ersten Handies, vermutlich Verschwendung. Das erspart dir gerade mal einen Faktor von 2 zum Einsatz nur eines Handies, du bleibst in O(x).

[Namenloser324]

Ich habe bereits geschrieben, dass es nur geht, wenn man annehmen darf, dass es ein Stockwerk gibt in dem es kaputt geht.

[Bashar]

Ja, und mit deiner Methode findet man das nicht.

[smartypho]

Was ist jetzt eigentlich die dem Erwartungswert nach beste Strategie für H bekannt?
Nachdem das erste Handy sqrt(n)-2 Stockwerke überlebt hat, kann man es ja weiter nutzen...

[Gast]

Jester schrieb:

Wenn man die anzahl nicht kennt macht eigentlich nur eine asymptotische analye sinn. Ansonsten gibt es nämlich garkeine optimale strategie. Wenn zum beispiel das 17. stockwerk das zielstockwerk ist, dann ist es offensichtlich optimal einmal aus dem 17. und einmal aus dem 16. zu werfen.

Sehe ich nicht so. Handy 2 aus 17 zu werfen und Handy 1 aus 16 ist ein Algorithmus der in allen anderen Fällen versagt, es ist schlicht nicht definiert was dann gemacht werden soll.
Imho heißt Optimalität im Bezug auf ein Verfahren: Das Worstcase-Zielstockwerk, d.h. die maximale Anzahl an Schritten, ist unter allen Algorithmen minimal.

Jester schrieb:

Das geht nicht wenn du h nicht kennst. Deswegen behelfsmässig die wuadratzahlen, weil die ungefähr genauso schnell wachsen.

Kann ich auch nicht nachvollziehen. H kann beliebig sein, der darauf angewandte Algorithmus bekommt H aber als Eingabeparameter. Wie ein Sortieralgorithmus der auch auf beliebig langen Listen funktioniert. Zum Start des Verfahrens ist die Anzahl also imho sehr wohl bekannt.

Okay, gleich noch ein paar Gedanken dazu....

[Gast]

Ich habe die ganze Zeit schon das Gefühl, es könnte was mit der Arithmetischen Reihe zu tun haben.

H1 = Handy 1
H2 = Handy 2
H = Anzahl Stockwerke

Also mit H1 jeweils +1 Stockwerke weiterspringen als im Schritt davor:
1 (+1) 2 (+2) 4 (+3) 7 (+4) 11 (+5) 16 ...

Bei H=100 hätten wir mit H1 folgende Stockwerke zu sondieren:
1 2 4 7 11 16 22 29 37 46 56 67 79 92
Nach 92 im schlimmsten Fall bis 100 durchlaufen ... nee, das geht besser in dem man die Reihenfolge umkehrt und die Sprünge bis zu H verkleinert:

9 22 34 45 55 64 72 79 85 90 94 97 99 100

(Anmerkung: Es gibt auch andere, gleichwertige Verfahren gemäß dieser Reihe. Z.B. 14 27 39 51 61 70 78 85 91 96 100. Basiert ebenfalls auf der Arithmetischen Reihe, nur der Start ist etwas verschoben, weil die Höhe des Gebäudes nicht exakt aufgeht)

Das Besondere: Jeder Wurf mit H1 reduziert die Anzahl der notwendigen Würfe mit H2, um die Lücke der letzten Lowerbound zu schließen, um genau eins. (Das ist imho der Grund, warum das Verfahren optimal ist)
Also als Beispiel zwei Fälle, die Handys halten bis Stockwerk 33 und 44.
Dann würde man für 33 untersuchen:
9 22 34 (crash H1 hier) und mit H2 noch 23-33. Sind genau 3+11 = 14 Würfe
Und für 44:
9 22 34 45 (crash H1) und weiter mit H2: 35-44. Macht 4+10 = 14 Würfe.

Es sind immer 14 Würfe mit Ausnahme von Fällen bei denen das Handy unterhalb des neuten Stockwerks zerbricht. Dann sind es aber weniger als 14.

Wenn man dieses Verfahren A jetzt gedanklich zu einem Verfahren B variiert, um es zu optimieren, gibt es eine Reihe von Fällen. Ich habe den Verdacht, dass man die Fälle alle systematisch auflisten und untersuchen könnte für eine formale Beweisführung. Es geht darum für Verfahren B Upper- und Lowerbounds sowie Sprungweiten mit H1 zu optimieren, und daraus zu schließen, dass sich der Worstcase verlagert und nicht mehr besser als A sein kann.

Ganz informell und unvollständig:
Wenn B eine kleinere Folge an Einzelschritten mit H2 machen muss, hat das Verfahren sich den Vorteil durch größere Lücken an anderen Stellen erkauft. Egal ob die Upperbound geringer oder die Lowerbound höher ist, gibt es danach oder davor eine entsprechend größere Lücke. Sollte sich das Zielstockwerk dort befinden, gibt es Fälle in denen B schlechter als A wird oder zumindest der Worstcase bestenfalls gleich bleibt.

Entsprechendes gilt, wenn B durch größere Sondierungssprünge mit H1 schneller an die Upperbound kommt. Für jeden eingesparten Sprung wächst die größte Lücke darunter und das Worstcase-Zielstockwerk verlagert sich, B verschlechtert sich dort gegenüber A bzw der Worstcase bleibt bestenfalls gleich.

Edit: Nur Tippfehler

[Jester]

µ schrieb:

Jester schrieb:

Wenn man die anzahl nicht kennt macht eigentlich nur eine asymptotische analye sinn. Ansonsten gibt es nämlich garkeine optimale strategie. Wenn zum beispiel das 17. stockwerk das zielstockwerk ist, dann ist es offensichtlich optimal einmal aus dem 17. und einmal aus dem 16. zu werfen.

Sehe ich nicht so. Handy 2 aus 17 zu werfen und Handy 1 aus 16 ist ein Algorithmus der in allen anderen Fällen versagt, es ist schlicht nicht definiert was dann gemacht werden soll.
Imho heißt Optimalität im Bezug auf ein Verfahren: Das Worstcase-Zielstockwerk, d.h. die maximale Anzahl an Schritten, ist unter allen Algorithmen minimal.

genau, das war mein argument: nur eine worst-case analyse macht sinn.

µ schrieb:

Jester schrieb:

Das geht nicht wenn du h nicht kennst. Deswegen behelfsmässig die wuadratzahlen, weil die ungefähr genauso schnell wachsen.

Kann ich auch nicht nachvollziehen. H kann beliebig sein, der darauf angewandte Algorithmus bekommt H aber als Eingabeparameter. Wie ein Sortieralgorithmus der auch auf beliebig langen Listen funktioniert. Zum Start des Verfahrens ist die Anzahl also imho sehr wohl bekannt.

Also ich weiß nicht wie Du das siehst, aber ich finde die Formulierung aus dem Eingangspost: "Aber welche Schrittzahl soll man nehmen wenn H nicht gegeben ist? Was ist die Optimale Schrittweite fuer H ?" sehr eindeutig. H ist nicht Teil der Eingabe und daher auch nicht bekannt.

[Jester]

Die Quadratzahlen zu probieren ist ja letztlich auch nur ne Art arithmetische Reihe, nämlich Summe der ungeraden Zahlen. Du summierst nun halt alle Zahlen, was aber zumindest asymptotisch keinen Unterschied macht.

Was mir gut gefällt ist das Argument, dass Du quasi dafür sorgst, dass mit beiden Smartphones etwa gleich viele Würfe gemacht werden, weil Du in jedem Schritt mit dem ersten Smartphone die Lücke um 1 vergrößerst. Das ist imo ein gutes Indiz dass die Strategie wirklich nah am Optimum ist. Ich vermute aber, dass man das H schon irgendwie groß genug wählen muss, weil man sonst immer irgendwelche fiesen Randeffekte reinbekommt. Aber dann sollte so ein simples Adversary-Argument wie ich es oben skizziert habe doch eigentlich durchgehen, oder?

[Smartphones]

Glaube, das einfachste und beste ist, mit einem Handy im ersten Stock anzufangen und mit dem zweiten im zweiten Stock. Wenn beide nicht kaputt gegangen sind, macht man mit dem ersten im dritten Stock und dem zweiten im vierte Stock weiter.

[Blaues Licht]

Smartphones schrieb:

Glaube, das einfachste und beste ist, mit einem Handy im ersten Stock anzufangen und mit dem zweiten im zweiten Stock. Wenn beide nicht kaputt gegangen sind, macht man mit dem ersten im dritten Stock und dem zweiten im vierte Stock weiter.

Sorry aber ich glaube Du hast das Problem nicht so ganz verstanden.

[SeppJ]

Blaues Licht schrieb:

Smartphones schrieb:

Glaube, das einfachste und beste ist, mit einem Handy im ersten Stock anzufangen und mit dem zweiten im zweiten Stock. Wenn beide nicht kaputt gegangen sind, macht man mit dem ersten im dritten Stock und dem zweiten im vierte Stock weiter.

Sorry aber ich glaube Du hast das Problem nicht so ganz verstanden.

Das ist eben der Versuch einer anderen Optimierung: Laufwege.

[Jockelx]

Aber keine besonders gute Optimierung.
~~
Ausm Bauch heraus, würde ich binäre Suche machen, wobei ich das erste Handy in der Mitte vom letzen Pivot und neuem Pivot werfen würde.~~
Totaler Qutasch...hab ich jetzt aber auch doch keine Lust drüber nachzudenken.

[Fytch]

'tschuldigung, ich habe es nicht ganz verstanden aber inwiefern ist eine arithmetische reihe besser als eine folge mit konstanten differenzen? ich meine, es gibt bei allen arithmetischen reihen worst-case-situationen (wenn der crash genau bei $a_i - 1$ ist). und wenn ich mich nicht irre, hebt sich das doch wieder damit aus, dass bei einer reihe mit konstanten differenzen mehr würfe mit dem handy 1 gemacht werden müssen.

[Jockelx]

Du beziehst dich auf Mühs Antwort oder?

Weil sich die Bereiche immer um eins verkleinern, gleichen Sie aus, dass man einen Wurf mehr brauch, um in diesen Bereich zu kommen.
Vergleiche Mühs Beispiel mit H=100:
Bei gesuchte Stelle 99 brauch Müh maximal 14 Würfe (hier sogar weniger), Schrittweite 10 brauch
10 20 30 40 50 60 70 80 90 91 92 93 94 95 96 97 98

[Gast]

Jester schrieb:

Also ich weiß nicht wie Du das siehst, aber ich finde die Formulierung aus dem Eingangspost: "Aber welche Schrittzahl soll man nehmen wenn H nicht gegeben ist? Was ist die Optimale Schrittweite fuer H ?" sehr eindeutig. H ist nicht Teil der Eingabe und daher auch nicht bekannt.

Du hast recht. Entschuldigung, habe das missverstanden bzw nicht richtig gelesen.
Aber naja, für den Fall, dass H bekannt ist, halte ich die Arithmetische Reihe immer noch für optimal.
Falls unbekannt, scheint mir ein Algorithmus mit Wurzelförmiger Komplexität optimal, wie das quadratische Springen von Dir.

Grüße und frohe Weihnachten

Edit: Tippfehler

[Gast]

Jester schrieb:

Aber dann sollte so ein simples Adversary-Argument wie ich es oben skizziert habe doch eigentlich durchgehen, oder?

Bin mir nicht sicher was Du damit meinst. Kannst Du das erklären?