بیشینه یابی با استفاده از مقایسه های نادقیق: بررسی نظری و تجربی

بیشینه‌یابی، یکی از مسائل پایه‌ای در علم رایانه است و الگوریتم‌های متعددی وجود دارند که با استفاده از مقایسۀ عناصر، نسبت به بیشینه‌یابی اقدام می‌کنند. در مدل‌های مرسوم، مقایسۀ دو عنصر به‌صورت دقیق انجام می‌شود. ما مدل مقایسه‌های نادقیق را در نظر می‌گیریم: به این معنی که، اگر تفاوت مقدار دو عنصر زیاد باشد، حاصل مقایسه دقیق است؛ در غیر این صورت ممکن است نتیجه مقایسه با واقعیت منطبق نباشد. در الگوریتم‌های موجود برای بیشینه‌یابی در مدل مقایسه‌های نادقیق، ممکن است خطای ناشی از مقایسه‌های نادقیق انباشته شود و موجب خطای زیاد در خروجی نهایی گردد. می‌توان با هزینۀ انجام تمام مقایسه‌ها، به پایین‌ترین حد ممکن خطا رسید. اما هدف، دستیابی به یک تعادل مطلوب بین تعداد مقایسه‌های انجام‌شده و میزان خطا است. با چنین شرایطی، فلدمن و همکارانش الگوریتم k-maxfind را ارائه دادند. در این مقاله این الگوریتم پیاده‌سازی شده و تحلیل تجربی انجام‌شده، گواه بر کارایی این الگوریتم با ورودی تصادفی نسبت به داده‌های خوشه‌ای و مرتب‌شده است، نتایج نظری، برای رسیدن به خطای [loglogn]=k که n اندازه ورودی است، تعداد (n^1+1/)2^k-1 مقایسه را لازم می‌داند، در حالی که بررسی این مقاله نشان می‌دهد در عمل، روی داده‌های تصادفی و روی چند توزیع دیگر، تعداد مقایسۀ حداکثر چند برابر اندازه ورودی، برای رسیدن به این خطا کافی است. بدین جهت در عمل الگوریتم کارایی بهتری نسبت به حالت نظری دارد. تاثیر پارامترهای مختلف بر نحوه تغییر رفتار الگوریتم در «تعداد مقایسه‌های انجام‌شده» و «خطای خروجی» نیز در این مقاله بررسی می‌شوند. قبلاً بررسی عملی این الگوریتم‌ها انجام نشده است و این مقاله اولین بررسی تجربی این الگوریتم‌ها است. نتیجه این بررسی نشان از کارایی خوب این الگوریتم در کاربرد است.