টার্নারি সার্চ#

আমাদের একটি ফাংশন $f(x)$ দেওয়া আছে যা একটি ব্যবধান $[l, r]$ এ ইউনিমোডাল। ইউনিমোডাল ফাংশন বলতে ফাংশনের দুটি আচরণের একটি বোঝায়:

১. ফাংশনটি প্রথমে কঠোরভাবে বাড়ে, একটি সর্বোচ্চ মানে পৌঁছায় (একটি একক বিন্দুতে বা একটি ব্যবধানে), এবং তারপর কঠোরভাবে কমে।

২. ফাংশনটি প্রথমে কঠোরভাবে কমে, একটি সর্বনিম্ন মানে পৌঁছায়, এবং তারপর কঠোরভাবে বাড়ে।

এই আর্টিকেলে, আমরা প্রথম পরিস্থিতি ধরে নেব। দ্বিতীয় পরিস্থিতি প্রথমটির সম্পূর্ণ প্রতিসম।

কাজটি হলো $[l, r]$ ব্যবধানে ফাংশন $f(x)$ এর সর্বোচ্চ মান খুঁজে বের করা।

অ্যালগরিদম#

এই ব্যবধানে যেকোনো ২টি বিন্দু $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}$ হয়।

মাস্টার্স থিওরেম প্রয়োগ করে, আমরা কাঙ্ক্ষিত কমপ্লেক্সিটি অনুমান পাই।

পূর্ণসংখ্যা আর্গুমেন্টের ক্ষেত্র#

যদি $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$ নির্বাচন পদ্ধতি পুনর্কনসিডার করি। ধরি আমরা $[l, r]$ এ $m_1$ এবং $m_2$ এমনভাবে নির্বাচন করি যাতে $\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;				//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]
}

এখানে eps আসলে পরম ত্রুটি (ফাংশনের ভুল গণনার কারণে সৃষ্ট ত্রুটি কনসিডার না করে)।

r - l > eps শর্তের পরিবর্তে, আমরা থামার শর্ত হিসেবে একটি নির্দিষ্ট সংখ্যক ইটারেশন নির্বাচন করতে পারি। প্রয়োজনীয় নির্ভুলতা নিশ্চিত করতে ইটারেশন সংখ্যা বেছে নেওয়া উচিত। সাধারণত, অধিকাংশ প্রোগ্রামিং চ্যালেঞ্জে ত্রুটির সীমা ${10}^{-6}$ এবং তাই ২০০ - ৩০০ ইটারেশন যথেষ্ট। এছাড়াও, ইটারেশন সংখ্যা $l$ এবং $r$ এর মানের উপর নির্ভর করে না, তাই ইটারেশন সংখ্যা প্রয়োজনীয় আপেক্ষিক ত্রুটির সাথে সঙ্গতিপূর্ণ।

অনুশীলন সমস্যা#