Гуравтын хайлт¶

Бидэнд $[l, r]$ интервал дээр нэг оргилтой (unimodal) $f(x)$ функц өгөгдсөн. Нэг оргилтой функц гэдгээр бид функцийн хоёр зан төлөвийн нэгийг хэлж байна:

Функц эхлээд чанд өсөж, максимумд (нэг цэгт эсвэл интервал дээр) хүрээд, дараа нь чанд буурна.
Функц эхлээд чанд буурч, минимумд хүрээд, дараа нь чанд өснө.

Энэ өгүүлэлд бид эхний хувилбарыг авч үзнэ. Хоёр дахь хувилбар нь эхнийхтэй бүрэн тэгш хэмтэй.

Бодлого нь $[l, r]$ интервал дээр $f(x)$ функцийн максимумыг олоход оршино.

Алгоритм¶

Энэ интервал дахь дурын 2 цэг $m_1$, $m_2$-ийг авч үзье: $l < m_1 < m_2 < r$. Бид функцийг $m_1$ ба $m_2$ дээр тооцоолно, өөрөөр хэлбэл $f(m_1)$ ба $f(m_2)$-ийн утгыг олно. Одоо бид гурван сонголтын нэгийг олж авна:

$f(m_1) < f(m_2)$

Хайж буй максимум нь $m_1$-ийн зүүн талд, өөрөөр хэлбэл $[l, m_1]$ интервалд байрлаж чадахгүй, учир нь $m_1$ ба $m_2$ хоёр цэг хоёулаа, эсвэл зөвхөн $m_1$ нь функц өсөж буй мужид харьяалагдана. Аль ч тохиолдолд энэ нь бид максимумыг $[m_1, r]$ хэрчмээс хайх ёстой гэсэн үг.
$f(m_1) > f(m_2)$

Энэ нөхцөл байдал өмнөхтэй тэгш хэмтэй: максимум нь $m_2$-ийн баруун талд, өөрөөр хэлбэл $[m_2, r]$ интервалд байрлаж чадахгүй бөгөөд хайлтын орон зай $[l, m_2]$ хэрчим болж багасна.
$f(m_1) = f(m_2)$

Эдгээр хоёр цэг хоёулаа функцийн утга максималчлагдах мужид харьяалагдана, эсвэл $m_1$ нь өсөх утгын мужид, $m_2$ нь буурах утгын мужид байна (энд бид функцийн өсөлт/бууралтын чанд байдлыг ашигласан) гэдгийг харж болно. Тиймээс хайлтын орон зай $[m_1, m_2]$ болж багасна. Кодыг хялбарчлахын тулд энэ тохиолдлыг өмнөх тохиолдлуудын аль нэгтэй нэгтгэж болно.

Ингэснээр хоёр дотоод цэг дэх утгуудын харьцуулалт дээр үндэслэн бид одоогийн $[l, r]$ интервалыг шинэ, богино $[l^\prime, r^\prime]$ интервалаар сольж болно. Тайлбарласан процедурыг интервалд давтан хэрэглэснээр бид дурын богино интервал олж авч болно. Эцэст нь түүний урт нь урьдчилан тодорхойлсон тодорхой тогтмолоос (нарийвчлал) бага болох ба процессыг зогсоож болно. Энэ бол тоон арга тул үүний дараа функц сүүлийн $[l, r]$ интервалын бүх цэгт максимумдаа хүрдэг гэж үзэж болно. Ерөнхий чанараа алдалгүйгээр бид $f(l)$-г буцаах утга болгон авч болно.

Бид $m_1$ ба $m_2$ цэгүүдийн сонголтод ямар ч хязгаарлалт тавиагүй. Энэ сонголт нь хэрэгжүүлэлтийн нийлэх хурд ба нарийвчлалыг тодорхойлно. Хамгийн түгээмэл арга бол цэгүүдийг $[l, r]$ интервалыг гурван тэнцүү хэсэгт хуваахаар сонгох явдал юм. Ингэснээр бид

$$m_1 = l + \frac{(r - l)}{3}$$

$$m_2 = r - \frac{(r - l)}{3}$$

Хэрэв $m_1$ ба $m_2$-ийг бие бие рүүгээ ойр сонговол нийлэх хурд бага зэрэг нэмэгдэнэ.

Ажиллах хугацааны шинжилгээ¶

$$T(n) = T({2n}/{3}) + O(1) = \Theta(\log n)$$

Үүнийг дараах байдлаар төсөөлж болно: $m_1$ ба $m_2$ цэг дээр функцийг тооцоолсны дараа бүр бид үндсэндээ интервалын гуравны нэгийг буюу зүүн эсвэл баруун талыг үл тоомсорлож байна. Тиймээс хайлтын орон зайн хэмжээ нь анхныхныхаа ${2n}/{3}$ болно.

Мастер теорем-ыг хэрэглэснээр бид хайж буй complexity-ийн үнэлгээг олж авна.

Бүхэл тоон аргументийн тохиолдол¶

Хэрэв $f(x)$ бүхэл тоон параметр авбал $[l, r]$ интервал дискрет болно. Бид $m_1$ ба $m_2$ цэгүүдийн сонголтод ямар ч хязгаарлалт тавиагүй тул алгоритмын зөв байдалд нөлөөлөхгүй. $m_1$ ба $m_2$-ийг $[l, r]$-ийг ойролцоогоор 3 тэнцүү хэсэгт хуваахаар сонгосон хэвээр байж болно.

Ялгаа нь алгоритмын зогсох шалгуурт гарна. Гуравтын хайлт $(r - l) < 3$ болоход зогсох ёстой, учир нь тэр тохиолдолд бид $m_1$ ба $m_2$-ийг бие биенээсээ болон $l$, $r$-ээс өөр байхаар сонгож чадахгүй бөгөөд энэ нь төгсгөлгүй давталтад хүргэж болзошгүй. $(r - l) < 3$ болмогц үлдсэн нэр дэвшигч цэгүүдийн сан $(l, l + 1, \ldots, r)$-г шалгаж $f(x)$ хамгийн их утга гаргах цэгийг олох хэрэгтэй.

Алтан огтлолын хайлт¶

Зарим тохиолдолд $f(x)$-г тооцоолох нь нэлээд удаан байж болох боловч нарийвчлалын асуудлаас болж итерацийн тоог багасгах боломжгүй байдаг. Аз болоход итерац бүрд (эхнийхийг эс тооцвол) $f(x)$-г зөвхөн нэг удаа тооцоолж болно.

Үүнийг хэрхэн хийхийг харахын тулд $m_1$ ба $m_2$-ийн сонгох аргыг эргэн харцгаая. Бид $[l, r]$ дээр $m_1$ ба $m_2$-ийг $\frac{r - l}{r - m_1} = \frac{r - l}{m_2 - l} = \varphi$ байхаар сонгоно гэж бодъё, энд $\varphi$ нь ямар нэг тогтмол. Тооцооллын хэмжээг багасгахын тулд бид дараагийн итерацид шинэ тооцоолох цэгүүд $m_1'$, $m_2'$-ийн нэг нь $m_1$ эсвэл $m_2$-тэй давхцахаар ийм $\varphi$-г сонгохыг хүсэж байна, ингэснээр аль хэдийн тооцоолсон функцийн утгыг дахин ашиглаж болно.

Одоо бид одоогийн итерацийн дараа $l = m_1$ тавьсан гэж бодъё. Тэгвэл $m_1'$ цэг нь $\frac{r - m_1}{r - m_1'} = \varphi$-г хангана. Бид энэ цэгийг $m_2$-тэй давхцахыг хүсэж байна, өөрөөр хэлбэл $\frac{r - m_1}{r - m_2} = \varphi$.

$\frac{r - m_1}{r - m_2} = \varphi$-ийн хоёр талыг $\frac{r - m_2}{r - l}$-ээр үржүүлбэл бид $\frac{r - m_1}{r - l} = \varphi\frac{r - m_2}{r - l}$-г олж авна. $\frac{r - m_1}{r - l} = \frac{1}{\varphi}$ ба $\frac{r - m_2}{r - l} = \frac{r - l + l - m_2}{r - l} = 1 - \frac{1}{\varphi}$ болохыг анхаарна уу. Үүнийг орлуулж $\varphi$-ээр үржүүлбэл бид дараах тэгшитгэлийг олж авна:

$\varphi^2 - \varphi - 1 = 0$

Энэ бол сайн мэдэгдэх алтан огтлолын тэгшитгэл юм. Түүнийг бодоход $\frac{1 \pm \sqrt{5}}{2}$ гарна. $\varphi$ эерэг байх ёстой тул бид $\varphi = \frac{1 + \sqrt{5}}{2}$-г олж авна. $r = m_2$ тавьж $m_2'$-г $m_1$-тэй давхцуулахыг хүсэх тохиолдолд ижил логикийг хэрэглэснээр бид мөн адил $\varphi$-ийн ижил утгыг олж авна. Тиймээс хэрэв бид $m_1 = l + \frac{r - l}{1 + \varphi}$ ба $m_2 = r - \frac{r - l}{1 + \varphi}$ сонговол итерац бүрд өмнөх итерацид тооцоолсон $f(x)$ утгуудын нэгийг дахин ашиглаж болно.

Implementation¶

double ternary_search(double l, double r) {
    double eps = 1e-9;              //set the error limit here
    while (r - l > eps) {
        double m1 = l + (r - l) / 3;
        double m2 = r - (r - l) / 3;
        double f1 = f(m1);      //evaluates the function at m1
        double f2 = f(m2);      //evaluates the function at m2
        if (f1 < f2)
            l = m1;
        else
            r = m2;
    }
    return f(l);                    //return the maximum of f(x) in [l, r]
}

Here eps is in fact the absolute error (not taking into account errors due to the inaccurate calculation of the function).

Instead of the criterion r - l > eps, we can select a constant number of iterations as a stopping criterion. The number of iterations should be chosen to ensure the required accuracy. Typically, in most programming challenges the error limit is ${10}^{-6}$ and thus 200 - 300 iterations are sufficient. Also, the number of iterations doesn't depend on the values of $l$ and $r$, so the number of iterations corresponds to the required relative error.