الگوریتم چندگانه

الگوریتم چندگانه یک الگوریتم است که دو یا چند الگوریتمی که مسئله مشابهی را حل می‌کنند ترکیب می‌کند به این صورت که یا یکی از دو الگوریتم را انتخاب می‌کند (بسته به نوع داده‌ها) یا بین آن‌ها جابجا می‌شود. اینکار به‌طور کلی برای این انجام می‌شود تا ویژگی‌های هر الگوریتم را با هم استفاده کند و الگوریتم نهایی در مجموع از تک تک الگوریتم‌های سازنده آن کارآتر باشد.

منظور از «الگوریتم‌های چندگانه» این نیست که چند الگوریتم مختلف با هم ترکیب شوند تا راه حلی برای یک مسئله متفاوت ساخته شود – بسیاری از الگوریتم‌ها را می‌توان به عنوان ترکیبی از قطعات ساده‌تر در نظر گرفت –. منظور از الگوریتم‌های چندگانه این است همه الگوریتم‌هایی که یک مسئله مشابه را حل می‌کنند ولی از لحاظ ویژگی و عملکرد با هم متفاوت هستند با هم ترکیب شوند.

چند مثال

در علوم کامپیوتر الگوریتم‌های چندگانه در بهینه‌سازیِ اجرای واقع گرایانه الگوریتم‌های بازگشتی بسیار رایج هستند. به خصوص پیاده‌سازی الگوریتم تقسیم و حل (کاهش و حل) که در آن هر چه به عمق بیشتری در درخت بازگشتی می‌رویم، حجم داده‌ها کاهش می‌یابد. در این حالت یک الگوریتم به عنوان رویکرد کلی در داده‌های بزرگ استفاده می‌شود اما در عمق زیاد درخت بازگشتی به یک الگوریتم دیگر پرش می‌کند که روی داده‌های کوچک‌تر کارآمدتر است. یک مثال رایج این موضوع الگوریتم‌های مرتب‌سازی است. مثلاً مرتب‌سازی درجی که روی داده‌های بزرگ ناکارآمد است اما روی داده‌های کوچک بسیار خوب عمل می‌کند را در نظر بگیرید. برای گام نهایی یعنی بعد از اجرا کردن الگوریتمی دیگر (مانند مرتب‌سازی ادغامی یا مرتب‌سازی سریع) از این نوع مرتب‌سازی استفاده می‌شود چرا که مرتب‌سازی ادغامی و مرتب‌سازی سریع برای داده‌های بزرگ مطلوب هستند ولی سربار قابل توجهی در هنگام استفاده از آن‌ها روی داده‌های کوچک به وجود می‌آید. از این رو از الگوریتمی دیگر در لایه‌های پایین حل بازگشتی استفاده می‌کنند. یک الگوریتم مرتب‌سازی بسیار بهینه الگوریتم مرتب‌سازی تیم است که ترکیبی از مرتب‌سازی ادغامی و مرتب‌سازی درجی به همراه منطق‌های تکمیل‌کننده (از جمله جستجوی دودویی) در منطق ادغام است.

مرتب‌سازی تیم

الگوریتم مرتب‌سازی تیم ترکیبی از دو الگوریتم مرتب‌سازی ادغامی و مرتب‌سازی درجی است. این الگوریتم زیردنباله‌ای را که خودش مرتب است پیدا می‌کند سپس بقیه داده‌ها را مرتب می‌کند و در نهایت با ادغام کردن داده‌های مرتب اولیه و داده‌مرتب شده کل داده‌ها در زمان سریع‌تری مرتب می‌شوند. این الگوریتم در بهترین حالت یک مجموعه داده را در زمان خطی و در حالت متوسط و بدترین حالت مجموعه با $n$ عنصر را با مرتبه زمانی $O(nlogn)$ مرتب می‌کند.

حالت اولیه کوتاه شده

یک روش کلی برای یک الگوریتم بازگشتی چندگانه حالت اولیه کوتاه شده‌است. در این روش این که در گام بعدی حالت اولیه اجرا می‌شود یا خیر پیش از فراخوانی تابع بررسی می‌شود که این موجب جلوگیری از فراخوانی تابع‌های غیرضروری می‌شود. برای مثال در یک درخت به جای صدا زدن تابع روی یک فرزند و سپس چک کردن اینکه آن فرزند $NULL$ است را قبل از فراخوانی تابع این مسئله را بررسی کنیم (اساساً در برنامه‌نویسی به داده‌ای که مقداردهی نشده‌باشد و صرفاً جایی از حافظه را اشغال کرده‌باشد، NULL می‌گویند). این کار وقتی خیلی مفید است که بارها با حالت اولیه در الگوریتم‌های درخت مختلف روبرو می‌شویم. اما از طرفی این روش به صورت نظری روشی غیرحرفه‌ای به حساب می‌آید چرا که پیچیدگی الگوریتم بالا می‌رود.

مرتب‌سازی درونگرا

مثال دیگر از الگوریتم‌های چندگانه و نحوه عملکرد آن‌ها مرتب‌سازی درونگرا و انتخاب درونگرا است که یک الگوریتم سریع برای حالت میانگین و الگوریتمی دیگر برای بهینه شدن بدترین حالت را ترکیب می‌کنند. مرتب‌سازی درونگرا با مرتب‌سازی سریع آغاز می‌شود و در ادامه با زیاد شدن عمق درخت بازگشتی الگوریتم به مرتب‌سازی هرمی تغییر می‌کند. این باعث می‌شود مرتب‌سازی درونگرا در بدترین حالت از مرتبه زمانی $O(nlogn)$ باشد در حالی‌که مرتب‌سازی سریع به تنهایی در بدترین حالت از مرتبه زمانی $n^{2}$ است. مشابهاً انتخاب درونگرا با انتخاب سریع آغاز می‌شود اما در صورت نیاز به الگوریتم میانه میانه‌ها پرش می‌کند.

اما در برخی پیاده‌سازی‌های مرتب‌سازی درونگرا در مرحله پایانی و پس از اجرای مرتب‌سازی هرمی، مرتب‌سازی درجی استفاده می‌شود. برای درک بهتر در ادامه گام‌های مرتب‌سازی درونگرا را بررسی می‌کنیم:

• ابتدا یک بخش را جدا می‌کنیم. سه حالت پیش می‌آید:

• اگر تعداد عناصر بخش جدا شده از حدی که از پیش معین شده($2*logn$) بیشتر باشد روی این بخش مرتب‌سازی هرمی پیاده می‌شود.
• اگر تعداد عناصر این بخش از $16$ کمتر باشد روی این بخش مرتب‌سازی درجی را پیاده می‌کنیم. (عدد ۱۶ با محاسبات به‌دست آمده‌است)
• در غیراینصورت روی بخش جدا شده مرتب‌سازی سریع را اعمال می‌کنیم.

الگوریتم‌های توزیع شده

از الگوریتم‌های توزیع شده متمرکز اغلب به عنوان الگوریتم‌های چندگانه یاد می‌شود زیرا این الگوریتم‌ها متشکل از یک الگوریتم تکی (اجرا بر روی هر پردازنده توزیع شده) و یک الگوریتم ترکیبی (اجرا روی متمرکزکننده توزیع) هستند. یک مثال اولیه از این الگوریتم‌ها مرتب‌سازی توزیعی است که مخصوصاً برای مرتب‌سازی خارجی استفاده می‌شود که همه داده‌ها را به زیر مجموعه‌های جدا از هم تقسیم می‌کند، هر زیر مجموعه را مرتب می‌کند و در نهایت زیر مجموعه‌ها را ترکیب می‌کند تا داده‌های مرتب شده حاصل شوند. مشابه مرتب‌سازی سطلی مرتب و مرتب‌سازی فلش.

اما به‌طور کلی الگوریتم‌های توزیع شده الزاماً الگوریتم‌های چندگانه نیستند چرا که الگوریتم‌های تکی یا ترکیب چند الگوریتم به هر حال ممکن است چند مسئله مختلف را حل کند. برای مثال در مدل‌هایی مانند نگاشت کاهش گام نگاشت و گام کاهش مسئله‌های مختلفی را حل می‌کنند و با هم ترکیب می‌شوند تا مسئله متفاوت سومی را حل کنند.

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

• مرتب‌سازی تیم
• توابع بازگشتی
• مرتب‌سازی درونگرا