انواع مختلف استراتژی های الگوریتمی

الگوریتم چیست؟یک الگوریتم روشی برای حل یک مشکل خاص در تعداد محدودی از مراحل برای ورودی به اندازه محدود است. الگوریتم ها را می توان به روش های مختلف طبقه بندی کرد. آن ها هستند:

1. روش اجرا
2. روش طراحی
3. رویکردهای طراحی
4. طبقه بندی های دیگر

در این مقاله ، الگوریتم های مختلف در هر روش طبقه بندی مورد بحث قرار گرفته است.

طبقه بندی الگوریتم ها به دلایل مختلف مهم است:

سازمان: الگوریتم ها می توانند بسیار پیچیده باشند و با طبقه بندی آنها ، سازماندهی ، درک و مقایسه الگوریتم های مختلف آسان تر می شود.

حل مسئله: مشکلات مختلف به الگوریتم های مختلف نیاز دارد و با داشتن طبقه بندی ، می تواند به شناسایی بهترین الگوریتم برای یک مشکل خاص کمک کند.

مقایسه عملکرد: با طبقه بندی الگوریتم ها ، می توان عملکرد آنها را از نظر پیچیدگی زمان و مکان مقایسه کرد و انتخاب بهترین الگوریتم برای یک مورد استفاده خاص را آسان تر می کند.

قابلیت استفاده مجدد: با طبقه بندی الگوریتم ها ، استفاده مجدد از الگوریتم های موجود برای مشکلات مشابه آسان تر می شود ، در نتیجه باعث کاهش زمان توسعه و بهبود کارآیی می شود.

تحقیق: طبقه بندی الگوریتم ها برای تحقیق و توسعه در علوم کامپیوتر ضروری است ، زیرا به شناسایی الگوریتم های جدید و بهبود موارد موجود کمک می کند.

به طور کلی ، طبقه بندی الگوریتم ها نقش مهمی در علوم کامپیوتر دارد و به بهبود کارآیی و اثربخشی حل مشکلات کمک می کند. طبقه بندی با روش اجرای: در درجه اول سه دسته اصلی وجود دارد که در این نوع طبقه بندی می توان یک الگوریتم را نامگذاری کرد. آن ها هستند:

1. بازگشت یا تکرار: یک الگوریتم بازگشتی الگوریتمی است که دوباره و دوباره خود را فراخوانی می کند تا اینکه یک شرط پایه حاصل شود در حالی که الگوریتم های تکراری از حلقه ها و/یا ساختارهای داده مانند پشته ها استفاده می کنند ، صف ها برای حل هر مشکلی. هر راه حل بازگشتی می تواند به عنوان یک راه حل تکراری و برعکس اجرا شود. مثال: برج هانوی به صورت بازگشتی اجرا می شود در حالی که مشکل سهام سهام به طور تکراری اجرا می شود.
2. دقیق یا تقریبی: الگوریتم هایی که قادر به یافتن یک راه حل بهینه برای هر مشکل هستند ، به عنوان الگوریتم دقیق شناخته می شوند. برای همه این مشکلات ، جایی که امکان یافتن بهینه ترین راه حل امکان پذیر نیست ، از الگوریتم تقریبی استفاده می شود. الگوریتم های تقریبی نوع الگوریتم هایی هستند که نتیجه را به عنوان یک نتیجه متوسط از نتایج فرعی برای یک مشکل می دانند. مثال: برای مشکلات NP سخت ، از الگوریتم های تقریبی استفاده می شود. الگوریتم های مرتب سازی الگوریتم های دقیق هستند.
3. الگوریتم های سریال یا موازی یا توزیع شده: در الگوریتم های سریال ، یک دستورالعمل در یک زمان اجرا می شود در حالی که الگوریتم های موازی مواردی هستند که ما در آن مشکل را به زیرزمین ها تقسیم می کنیم و آنها را در پردازنده های مختلف اجرا می کنیم. اگر الگوریتم های موازی در دستگاه های مختلف توزیع شوند ، آنها به عنوان الگوریتم های توزیع شده شناخته می شوند.

طبقه بندی با روش طراحی: در درجه اول سه دسته اصلی وجود دارد که در این نوع طبقه بندی می توان یک الگوریتم را نامگذاری کرد. آن ها هستند:

1. روش حریص: در روش حریص ، در هر مرحله ، تصمیم به انتخاب مطلوب محلی گرفته می شود ، بدون اینکه به پیامدهای آینده فکر کند. مثال: کوله پشتی کسری ، انتخاب فعالیت.
2. تقسیم و فتح: استراتژی تقسیم و فاتح شامل تقسیم مشکل به زیرنویس ، حل بازگشتی آنها و سپس نوترکیب آنها برای پاسخ نهایی است. مثال: ادغام مرتب سازی ، QuickSort.
3. برنامه نویسی پویا: رویکرد برنامه نویسی پویا شبیه به تقسیم و فاتح است. تفاوت در این است که هر زمان که ما با همان نتیجه تماس های بازگشتی داشته باشیم ، به جای اینکه دوباره آنها را فراخوانی کنیم ، سعی می کنیم نتیجه را در ساختار داده به شکل یک جدول ذخیره کنیم و نتایج را از جدول بازیابی کنیم. بنابراین ، پیچیدگی زمان کلی کاهش می یابد."پویا" به این معنی است که ما به صورت پویا تصمیم می گیریم ، خواه یک تابع را صدا کنیم یا مقادیر را از جدول بازیابی کنیم. مثال: 0-1 کوله پشتی ، مشکل زیر مجموعه.
4. برنامه نویسی خطی: در برنامه نویسی خطی ، از نظر ورودی نابرابری ها و به حداکثر رساندن یا به حداقل رساندن برخی از عملکردهای خطی ورودی ها وجود دارد. مثال: حداکثر جریان نمودار کارگردانی
5. کاهش (تبدیل و فتح): در این روش ، ما با تبدیل آن به یک مشکل شناخته شده که برای آن یک راه حل بهینه داریم ، یک مشکل دشوار را حل می کنیم. در اصل ، هدف این است که یک الگوریتم کاهش دهنده را پیدا کنید که پیچیدگی آن توسط الگوریتم های کاهش یافته حاصل نشود. مثال: الگوریتم انتخاب برای پیدا کردن میانه در یک لیست شامل مرتب سازی ابتدا لیست و سپس پیدا کردن عنصر میانی در لیست مرتب شده است. این تکنیک ها نیز تبدیل و فاتح نامیده می شوند.
6. Backtracking: این تکنیک در حل مشکلات ترکیبی که یک راه حل منحصر به فرد دارند بسیار مفید است. جایی که ما باید ترکیبی صحیح از مراحل را پیدا کنیم که منجر به انجام کار شود. چنین مشکلاتی چندین مرحله دارد و در هر مرحله گزینه های مختلفی وجود دارد. این رویکرد مبتنی بر کاوش هر گزینه موجود در هر مرحله یک به یک است. در حالی که در صورت دستیابی به یک نقطه ، به نظر می رسد که به نظر نمی رسد که به راه حل منجر شود ، کنترل برنامه یک مرحله را پشت سر می گذارد و شروع به کاوش در گزینه بعدی می کند. به این ترتیب ، این برنامه به بررسی تمام دوره های ممکن اقدامات می پردازد و مسیری را پیدا می کند که منجر به راه حل می شود. مثال: مشکل N-Queen ، مشکل ذرت.
7. Branch and Bound: این تکنیک در حل مشکل بهینه سازی ترکیبی که دارای چندین راه حل است بسیار مفید است و ما علاقه مند به یافتن بهینه ترین راه حل هستیم. در این روش ، کل فضای راه حل به شکل یک درخت فضایی دولتی نشان داده شده است. با پیشرفت برنامه ، هر ترکیب دولت مورد بررسی قرار می گیرد ، و در صورتی که بهینه از راه حل فعلی نباشد ، راه حل قبلی توسط جدید جایگزین می شود. مثال: توالی شغل ، مشکل فروشنده مسافرتی.

طبقه بندی با رویکردهای طراحی: دو رویکرد برای طراحی الگوریتم وجود دارد. این رویکردها شامل

1. رویکرد بالا به پایین :
2. رویکرد پایین به بالا

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

رویکرد بالا به پایین:

شکستن یک مشکل پیچیده در زیرنویس های کوچکتر و قابل کنترل تر و حل هر یک از زیرنویس ها به صورت جداگانه. طراحی سیستمی که از بالاترین سطح انتزاع شروع می شود و به سمت سطح پایین حرکت می کند. رویکرد پایین به بالا:

ساختن یک سیستم با شروع با مؤلفه های فردی و به تدریج ادغام آنها برای تشکیل یک سیستم بزرگتر. حل مشکلات فرعی ابتدا و سپس استفاده از راه حل ها برای ایجاد یک راه حل یک مشکل بزرگتر. توجه: هر دو رویکرد دارای مزایا و معایب خاص خود هستند و انتخاب بین آنها اغلب به مشکل خاص حل شده بستگی دارد.

در اینجا نمونه هایی از رویکردهای از بالا به پایین و پایین به بالا در کد آورده شده است:

رویکرد از بالا به پایین (در پایتون):