پرش به محتویات

جستجوی سه‌سه‌ای

تابعی مانند $f(x)$ به ما داده شده است که در بازه $[l, r]$ تک‌قله‌ای (unimodal) است. منظور از تابع تک‌قله‌ای، یکی از دو رفتار زیر برای تابع است:

  1. تابع ابتدا اکیداً صعودی است، به یک ماکزیمم (در یک نقطه یا یک بازه) می‌رسد و سپس اکیداً نزولی می‌شود.

  2. تابع ابتدا اکیداً نزولی است، به یک مینیمم می‌رسد و سپس اکیداً صعودی می‌شود.

در این مقاله، ما سناریوی اول را فرض می‌کنیم. سناریوی دوم کاملاً متقارن با سناریوی اول است.

هدف، پیدا کردن ماکزیمم تابع $f(x)$ در بازه $[l, r]$ است.

الگوریتم

دو نقطه دلخواه $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}$ اندازه اصلی کاهش می‌یابد.

با اعمال Master's Theorem، به تخمین پیچیدگی مطلوب می‌رسیم.

حالت آرگومان‌های صحیح

اگر $f(x)$ پارامتر صحیح بگیرد، بازه $[l, r]$ گسسته می‌شود. از آنجا که ما هیچ محدودیتی برای انتخاب نقاط $m_1$ و $m_2$ قائل نشدیم، صحت الگوریتم تحت تأثیر قرار نمی‌گیرد. $m_1$ و $m_2$ همچنان می‌توانند طوری انتخاب شوند که بازه $[l, r]$ را به ۳ قسمت تقریباً مساوی تقسیم کنند.

تفاوت در شرط توقف الگوریتم رخ می‌دهد. جستجوی سه‌سه‌ای باید زمانی که $(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$ بازگردیم. فرض کنید $m_1$ و $m_2$ را در بازه $[l, r]$ به گونه‌ای انتخاب می‌کنیم که $\frac{r - l}{r - m_1} = \frac{r - l}{m_2 - l} = \varphi$ که در آن $\varphi$ یک ثابت است. برای کاهش میزان محاسبات، ما می‌خواهیم $\varphi$ را طوری انتخاب کنیم که در تکرار بعدی، یکی از نقاط ارزیابی جدید، $m_1'$ یا $m_2'$، با یکی از نقاط $m_1$ یا $m_2$ منطبق شود تا بتوانیم از مقدار تابع که قبلاً محاسبه شده، دوباره استفاده کنیم.

حال فرض کنید پس از تکرار فعلی، $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)$ که در تکرار قبلی محاسبه شده، دوباره استفاده کنیم.

پیاده‌سازی

double ternary_search(double l, double r) {
    double eps = 1e-9;              //حد خطا را اینجا تنظیم کنید
    while (r - l > eps) {
        double m1 = l + (r - l) / 3;
        double m2 = r - (r - l) / 3;
        double f1 = f(m1);      //تابع را در m1 ارزیابی می‌کند
        double f2 = f(m2);      //تابع را در m2 ارزیابی می‌کند
        if (f1 < f2)
            l = m1;
        else
            r = m2;
    }
    return f(l);                    //ماکزیمم f(x) در بازه [l, r] را برمی‌گرداند
}

در اینجا eps در واقع خطای مطلق است (بدون در نظر گرفتن خطاهای ناشی از محاسبه نادقیق تابع).

به جای شرط r - l > eps، می‌توانیم تعداد ثابتی از تکرارها را به عنوان شرط توقف انتخاب کنیم. تعداد تکرارها باید طوری انتخاب شود که دقت مورد نیاز را تضمین کند. به طور معمول، در اکثر مسابقات برنامه‌نویسی حد خطا ${10}^{-6}$ است و بنابراین ۲۰۰ تا ۳۰۰ تکرار کافی است. همچنین، تعداد تکرارها به مقادیر $l$ و $r$ بستگی ندارد، بنابراین تعداد تکرارها با خطای نسبی مورد نیاز متناسب است.

مسائل تمرینی