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

بیشینه یابی، یکی از مسایل پایه ای در علم رایانه است و الگوریتم های متعددی وجود دارند که با استفاده از مقایسه عناصر، نسبت به بیشینه یابی اقدام می کنند. در مدل های مرسوم، مقایسه دو عنصر به صورت دقیق انجام می شود. ما مدل مقایسه های نادقیق را در نظر می گیریم: به این معنی که، اگر تفاوت مقدار دو عنصر زیاد باشد، حاصل مقایسه دقیق است؛ در غیر این صورت ممکن است نتیجه مقایسه با واقعیت منطبق نباشد. در الگوریتم های موجود برای بیشینه یابی در مدل مقایسه های نادقیق، ممکن است خطای ناشی از مقایسه های نادقیق انباشته شود و موجب خطای زیاد در خروجی نهایی گردد. می توان با هزینه انجام تمام مقایسه ها، به پایین ترین حد ممکن خطا رسید. اما هدف، دستیابی به یک تعادل مطلوب بین تعداد مقایسه های انجام شده و میزان خطا است. با چنین شرایطی، فلدمن و همکارانش الگوریتم k-MaxFind را ارایه دادند. در این مقاله این الگوریتم پیاده سازی شده و تحلیل تجربی انجام شده، گواه بر کارایی این الگوریتم با ورودی تصادفی نسبت به داده های خوشه ای و مرتب شده است، نتایج نظری، برای رسیدن به خطای که اندازه ورودی است، تعداد مقایسه را لازم می داند، در حالی که بررسی این مقاله نشان می دهد در عمل، روی داده های تصادفی و روی چند توزیع دیگر، تعداد مقایسه حداکثر چند برابر اندازه ورودی، برای رسیدن به این خطا کافی است. بدین جهت در عمل الگوریتم کارایی بهتری نسبت به حالت نظری دارد. تاثیر پارامترهای مختلف بر نحوه تغییر رفتار الگوریتم در «تعداد مقایسه های انجام شده» و «خطای خروجی» نیز در این مقاله بررسی می شوند. قبلا بررسی عملی این الگوریتم ها انجام نشده است و این مقاله اولین بررسی تجربی این الگوریتم ها است. نتیجه این بررسی نشان از کارایی خوب این الگوریتم در کاربرد است.