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

আমাদের একটি ফাংশন $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$ এর মানের উপর নির্ভর করে না, তাই ইটারেশন সংখ্যা প্রয়োজনীয় আপেক্ষিক ত্রুটির সাথে সঙ্গতিপূর্ণ।

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