جستجوی درون‌یابی

جستجوی درون‌یابی (به انگلیسی: Interpolation search) به عنوان یک روش جستجوی خوب شناخته می‌شود. در اینجا پس از تعریف درون‌یابی، دربارهٔ الگوریتم جستجوی آن توضیح می‌دهیم.

به‌طور کلی در علوم کامپیوتر و ریاضیات، یک الگوریتم جستجو، الگوریتمی است که یک مسئله را به عنوان ورودی می‌گیرد و بعد از ارزیابی کردن راه حل‌های ممکن، یک راه حل برای آن مسئله برمی گرداند.مجموعهٔ راه حل‌های ممکن برای یک مسئله را فضای جستجو می‌نامند.

مقدمه

برای روشن شدن این روش از یک مثال استفاده می‌کنیم. برای یافتن شماره تلفن «کالین، کالی» در دفترچه تلفن، چیزی بیش از مقایسه کلیدها را انجام می‌دهیم. یعنی ما از میانه کتاب شروع نمی‌کنیم زیرا می‌دانیم که «ک»ها در کجای دفترچه قرار دارند. یعنی درون یابی کرده و از نقطه خاصی از کتاب شروع می‌کنیم. در ادامه الگوریتمی برای پیاده‌سازی این راهبرد ارائه خواهیم داد.

جستجوی درون‌یابی چگونه کار می‌کند؟

فرض کنید کلید x را در میان ۱۰ عدد صحیح جستجو می‌کنیم و می‌دانیم که عدد صحیح اول بین ۰ تا ۹، دومی بین ۱۰ تا ۱۹، سومی بین ۲۰ تا ۲۹، ... و دهمی بین ۹۰ تا ۹۹ قرار دارد. در این صورت اگر کلید x کوچکتر از صفر یا بزرگتر از ۹۹ باشد، می‌توان بی درنگ شکست را گزارش کرد و در غیر این صورت، فقط کافی است x را با $S[1+\lfloor {\frac {x}{10}}\rfloor ]$ مقایسه کنیم. برای مثال، x=25 را با $S[1+\lfloor {\frac {25}{10}}\rfloor ]=S[3]$ مقایسه می‌کنیم. اگر مساوی نبودند، شکست را گزارش می‌کنیم. معمولاً این مقدار اطلاعات در اختیار ما نیست. ولی در برخی کاربردها منطقی است که فرض کنیم کلیدها از توزیع تقریباً یکنواختی برخوردارند. در چنین مواردی، بجای چک کردن آن که آیا x با کلید میانی برابر است، می‌توانیم چک کنیم که آیا x در موقعیتی که انتظار داریم آن را بیابیم، هست یا خیر. برای مثال، اگر فرض کنیم که ۱۰ کلید از توزیع یکنواختی برخوردارند، می‌توانیم انتظار داشته باشیم که x=۲۵ در موقعیت سوم قرار دارد و به جای مقایسه x با [S[۵ آن را با [S[۳ مقایسه می‌کنیم. الگوریتمی که این راهبرد را پیاده‌سازی می‌کند، جستجوی درون یابی نام دارد. همانند جستجوی دودویی، به low مقدار اولیه ۱ و به high مقدار اولیه n داده می‌شود. سپس از درون یابی خطی برای تعیین تقریبی محل واقع شدن x استفاده می‌کنیم، یعنی محاسبه زیر را انجام می‌دهیم:

$mid=low+\lfloor {\frac {x-S[low]}{S[high]-S[low]}}\times (high-low)\rfloor$

برای مثال، اگر S[۱]=۴ و S[10]=۹۷ باشد و ما به دنبال x=۲۵ باشیم، محاسبه زیر را انجام می‌دهیم:

$mid=1+\lfloor {\frac {25-4}{97-4}}\times (10-1)\rfloor =1+\lfloor 2.032\rfloor =3$

الگوریتم

الگوریتم جستجوی درون یابی، که در زیر می‌آید، به جای شیوه متفاوت محاسبه mid و کارهای اضافی، همانند جستجوی دودویی عمل می‌کند.

پیاده سازی

void interpsrch (int n, const number S[], number x, index& i)
{
	index low, high, mid;
	number denominator;
	low = ۱;
	high = n;
	i = ۰;
	if (S[low] <= x && S[high]>= x)
		while (low <= high && i == ۰)
		{
			denominator = S[high] - S[low];
			if (denominator == ۰)
				mid = low;
			else
				mid = low + int(((x - S[low])*(high - low))/denominator);
			if (x == S[mid])
				i = mid;
			else if (x <S[mid])
				high = mid - ۱;
			else
				low = mid + ۱;
		}
}

تحلیل

اگر توزیع کلیدها تقریباً یکنواخت باشد، جستجوی درون یابی سریعتر از جستجوی دودویی، کلید x را پیدا می‌کند. برای نمونه، در مثال قبل، اگر x=۲۵ کوچکتر از [S[۳ می‌بود، جستجوی درون یابی، اندازه نمونه را از ۱۰ به ۲ کاهش می‌داد، حال آنکه جستجوی دودویی آن را فقط به ۴ کاهش می‌داد. فرض کنید کلیدها به‌طور یکنواخت بین [S[۱ و [S[n توزیع شده باشند. منظور ما این است که احتمال پیدا شدن یک کلید انتخاب شده به‌طور تصادفی در یک محدوده خاص، مساوی احتمال پیدا شدن آن در هر محدوده دیگری با همان طول است. اگر چنین باشد، انتظار داریم x را تقریباً در محلی که جستجوی برون یابی تعیین کرده‌است، بیابیم و بنابراین، انتظار داریم کارایی جستجوی درون یابی در حالت میانگین بهتر از جستجوی دودویی باشد. در واقع، تحت شرایطی که کلیدها به‌طور یکنواخت توزیع شده‌اند، می‌توان نشان داد که پیچیدگی زمانی جستجوی درون یابی در حالت میانگین عبارت است از:

$A(n)\approx lg(lgn)$

اگر n برابر با یک میلیارد باشد، (lg(lg n حدود ۵ است، حال آنکه lg n حدود ۳۰ است. یک عیب جستجوی درون یابی، کارایی آن در بدترین حالت است. فرض کنید ۱۰ کلید داریم و مقادیر آن‌ها عبارتند از ۱، ۲، ۳، ۴، ۵، ۶، ۷، ۸، ۹ و ۱۰۰. اگر x برابر ۱۰ باشد، mid به کرات برابر low قرار داده می‌شود و x با هر یک از کلیدها مقایسه می‌شود. در بدترین حالت، جستجوی درون یابی تا حد جستجوی ترتیبی تنزل می‌یابد. توجه کنید که بدترین حالت، زمانی رخ می‌دهد که mid به کرات برابر low قرار داده می‌شود. شکل دیگری از جستجوی درون یابی که جستجوی درون یابی توانمند نامید می‌شود، این مشکل را با تعریف متغیر gap حل می‌کند، بطوریکه mid-low و high-mid همواره بزرگتر از gap هستند. به gap مقدار اولیه زیر را می‌دهیم:

$gap=\lfloor (high-low+1)^{\frac {1}{2}}\rfloor$

و mid را با استفاده از فرمول قبلی برای درون یابی خطی محاسبه می‌کنیم. پس از آن محاسبه، مقدار mid احتمالاً با محاسبه زیر تغییر می‌یابد:

$((mid=minimum(high-gap,maximum(mid,low+gap$

در مثالی که x=۲۰ و کلیدها برابر ۱، ۲، ۳، ۴، ۵، ۶، ۷، ۸، ۹ و ۱۰۰ بودند، به gap مقدار اولیه $\lfloor (10-1+1)^{\frac {1}{2}}\rfloor =3$، به mid مقدار اولیه ۱ داده می‌شود و داریم:

$mid=minimum(10-3,maximum(1,1+3))=4$

به این ترتیب تضمین می‌شود که اندیس به کار رفته برای مقایسه، حداقل به اندازه gap از low و high دور است. هر گاه جستجو به دنبال x در زیر آرایه حاوی تعداد بزرگتری از عناصر آرایه ادامه یابد، مقدار gap دو برابر می‌شود، ولی هرگز بزرگتر از نصف تعداد عناصر موجود در آن زیر آرایه نمی‌شود. برای نمونه، در مثال قبل، جستجو به دنبال x، در زیر آرایه بزرگتر از [S[۵ تا [S[۱۰ ادامه می‌یابد. بنابراین gap را دو برابر می‌کنیم. با این تفاوت که در این مورد، زیر آرایه حاوی تنها شش عنصر است و با دو برابر کردن gap مقدار آن از تعداد عناصر موجود در زیر آرایه تجاوز می‌کند. gap را دو برابر می‌کنیم تا به سرعت از زیرآرایه‌های بزرگ گریز کنیم. هنگامی که معلوم می‌شود x در زیر آرایه حاوی تعداد کوچکتری از عناصر است، به gap همان مقدار اولیه اش را می‌دهیم. با این فرضیات که کلیدها به‌طور یکنواخت توزیع شده‌اند و احتمال وجود x در همه محلهای آرایه یکسان است، پیچیدگی زمانی در حالت میانگین برای جستجوی درون یابی توانمند برابر $((\Theta (lg(lgn$ است. پیچیدگی زمانی آن در بدترین حالت به $(\Theta ((lgn)^{2}$ تعلق دارد، که از جستجوی دودویی بدتر ولی از جستجوی درون یابی بسیار بهتر است. چند محاسبه اضافی در جستجوی درون یابی توانمند، نسبت به جستجوی درون یابی و در جستجوی درون یابی نسبت به جستجوی دودویی وجود دارد. در عمل باید تحلیل شود که آیا صرفه جویی در محاسبات ارزش این افزایش در محاسبات را دارد یا خیر. جستجوهای شرح داده شده در اینجا، در مورد کلمات نیز کاربرد دارد زیرا کلمات را می‌توان به راحتی به اعداد کدگذاری کرد. بنابراین، می‌توانیم روش جستجوی دودویی اصلاح شده را در جستجوی کتاب راهنمای تلفن به کار گیریم.

جستارهای وابسته

• الگوریتم جستجوی دودویی

پیوند به بیرون

• National Institute of Standards and Technology

منابع

• جعفرنژاد قمی، عین الله. طراحی الگوریتم ها. چاپ ششم، انتشارات علوم رایانه، ۱۳۸۳.
• گروه مهندسی-پژوهشی خوارزمی(مترجمین).مقدمه‌ای بر الگوریتم ها. انتشارات دقت، ۱۳۸۷.

• Interpolation search
• National Institute of Standards and Technology