Úloha 2.u1: Hledání minima (4 b)

Zadáno v čísle 22.2.

Řešeno v čísle 22.4.

Zadání

Existuje funkce, o které víš, že na uzavřeném intervalu $\langle 0;1\rangle $ reálných čísel splňuje následující:

  1. je všude definována

  2. jejím oborem hodnot je podmnožina reálných čísel

  3. má právě jedno lokální minimum1

  4. nikde není konstantní

Tvůj úkol je jednoduchý: najdi takový interval $\langle a;b\rangle $, který toto minimum obsahuje, a přitom $b-a \le 1/1\, 000\, 000$. Bohužel nevíš, jak je funkce definována. Naštěstí ale máš kouzelnou krabičku, které můžeš zadat libovolné reálné číslo a ona ti s naprostou přesností prozradí funkční hodnotu v tomto bodě. Chvilku jí to ale trvá, takže úkol chceš splnit na co nejméně použití krabičky. Za obzvláště efektivní řešení budou bonusové body.


1) Existuje tedy nějaké $x_0$ (ono minimum), pro které platí, že na celém intervalu $\langle 0,x_0 \rangle $ je funkce klesající a na celém intervalu $\langle x_0,1 \rangle $ je zase rostoucí.

Řešení

Nejdříve se domluvme na následujícím značení:

  • $x _\mathrm {min}$ bude námi hledaný bod, ve kterém nabývá funkce $f$ minima na intervalu $\langle 0;1 \rangle $

  • $x_1, x_2, x_3 \dots $ budou námi vybrané hodnoty $x$, pro které jsme zjistili hodnotu $f(x)$. Předpokládejme, že $x_1 < x_2 < x_3 < \dots $

Pozorování: To, že známe $f(x)$ pro nějakou jednu hodnotu $x_1$, nám o $x _\mathrm {min}$ nic neřekne, $x _\mathrm {min}$ může být menší, rovno, nebo větší než $x_1$. Pokud ale známe $f(x)$ pro dvě hodnoty $x_1$ a $x_2$, tak už něco o $x _\mathrm {min}$ víme. Když $f(x_1) \le f(x_2)$, tak $x _\mathrm {min}< x_2$ (a naopak). Rozmyslete si situaci $f(x_1) = f(x_2)$, zejména to, že nám to počet dotazů na krabičku nikdy nezvýší.

Pokud známe hodnoty $f(x)$ pro $x_1, x_2, x_3, \dots , x_ n$ a $f(x)$ je nejmenší pro $x_ k$, tak platí, že $x_{k-1} < x _\mathrm {min}< x_{k+1}$.

Naším cílem bylo 1 000 000-krát zpřesnit náš odhad na to, kde se $x _\mathrm {min}$ nachází. Kdybychom se to pokusili udělat „najednou“, budeme potřebovat 1 999 999 použití krabičky. My ale výsledky z krabičky dostáváme postupně. Pokud se pokusíme dvakrát za sebou zpřesnit náš odhad 1 000-násobně, tak nám bude stačit jen$2\cdot 1\, 999 = 3\, 998$ použití krabičky. Na tři stonásobná zpřesnění budeme potřebovat $3\cdot 199 = 597$ použití krabičky, na šest desetinásobných zpřesnění $6\cdot 19 = 114$ použití krabičky, …

Trocha experimentování ukáže, že ideálním postupem je 20 zpřesnění na 2/4 původního rozsahu. Pokaždé použijeme krabičku třikrát, celkem 60-krát.

To je ale vše za předpokladu, že se nám nijak nepovede „recyklovat“ informace z předchozího kroku. Pokud nedošlo k tomu, že se nám dvě zjištěné hodnoty rovnaly, tak nám jedna z hodnot zůstane „uvnitř“ námi prohledávaného rozsahu.

Tento zbývající bod nám (pokud rozdělujeme interval rovnoměrně) vyjde přesně doprostřed nového rozsahu, což nám prohledávání ještě o kousek zlevní na 41 dotazů celkem (v prvním kroku není co recyklovat).

To ale ještě pořád není ideální řešení! Co když nebudeme dělit interval rovnoměrně? Pokud se zeptáme na dva body opravdu blízko u středu intervalu, umíme interval téměř půlit na dva dotazy. Takže teoreticky bychom mohli zpřesňovat 20-krát za pouhých 40 dotazů.

Co kdybychom uměli současně dělit interval nerovnoměrně a přitom recyklovat předtím zjištěné hodnoty? Řešením je použití zlatého řezu, tedy čísla$\phi = 0{,}6180339887\ldots {}$, které splňuje vlastnost ${1 \over 1+\phi } = \phi $. Pro názornost předpokládejme, že jsme v prvním kroku. Interval od 0 do 1 rozdělíme zlatým řezem z obou stran a krabičky se zeptáme na $f(x)$ pro $x_1 = \phi $ a $x_2 = 1 - \phi $. Tímto docílíme zpřesnění na $\phi $-násobek původního rozsahu za 2 dotazy. To není nic extra, ale následně si stačí všimnout, že ten jeden bod, který nám zůstal v rozsahu, umíme bezproblémově zrecyklovat, protože

\[ {1 \over 1+\phi } = \phi \Leftrightarrow 1 = \phi + \phi ^2 \Leftrightarrow {1-\phi \over \phi } = \phi , \]

díky čemuž nám bude stačit 29 zpřesnění za celkem 30 dotazů.

Existují ještě pokročilejší optimalizační algoritmy, ale tam už jsou rozdíly natolik malé, že nám už nezvládnou ušetřit ani jeden dotaz.

Matej