الگوریتم چیست؟
قطعا تاکنون واژه الگوریتم (Algorithm) را شنیده‌اید. الگوریتم‌ها در تمام مسائل روزمره ما دخیل هستند. در نگاهی دقیق‌تر، می‌توان الگوریتم را طرح برنامه‌ای تعریف کرد که صفر تا صد کاری را مبتنی بر آن انجام می‌دهیم. الگوریتم می‌تواند n ورودی داشته باشد، اما 1 خروجی دارد و شرط برقراری‌اش در این است که زمان اجرای آن محدود باشد. در دنیای علوم کامپیوتر هم مجموعه‌ای از گام‌ها و فرآیندهای پی‌در‌پی برای حل مسأله یا انجام محاسبات را الگوریتم می‌گویند که در برنامه نویسی نقش بسیار پررنگی ایفا میکند. در این مطلب قصد داریم انواع الگوریتم ها را بیشتر زیر ذره‌بین بگذاریم، البته برای آشنایی بیشتر با مفهوم اساسی الگوریتم، می‌توانید به صفحه الگوریتم چیستالگوریتم چیست به زبان ساده و با مثال های فراوان
در این مقاله به زبان بسیار ساده و با مثال های متعدد توضیح داده شده که الگوریتم چیست و چه کاربردهایی دارد مراجعه نمایید.
انواع الگوریتم های حل مسأله - روش‌های مختلف حل مسأله
الگوریتم‌ها (به‌ویژه الگوریتم های بهینه سازی) انواع مختلفی دارند، اما اصلی‌ترین آنها را در ادامه بررسی کرده‌ایم تا بهتر بتوانید از آنها در مسائل روزمره و البته در برنامه نویسی بهره بگیرید.
الگوریتم Brute Force
الگوریتم Brute Force سادهترین نوع الگوریتم ممکن برای حل مسائل است. تکیه این الگوریتم برای حل مسأله، قدرت محاسباتی محض است، نه شیوه های پیشرفته مختلف برای بهبود کارایی. در مرحله اول این الگوریتم، راه حلی برای مسأله می‌یابیم و ارائه می‌کنیم. سپس می‌کوشیم در کوتاه‌ترین زمان ممکن، به هدف نهایی مشخص و بهینه‌ای دست پیدا کنیم. همه مسائل را می‌توان با الگوریتم Brute Force حل کرد، هرچند بهلحاظ پیچیدگی زمانی و فضایی، توجیه چندانی ندارد و بنابراین بهتر است هنگام برنامه نویسی دنبال راه‌های بهینه‌تر باشیم.
الگوریتم حریصانه (Greedy)
در تمام گام‌های الگوریتم حریصانه، نیل به هدف از گام‌های قبل و بعد مستقل است. به عبارتی این الگوریتم در هر مرحله و در راستای رسیدن به هدف نهایی، بهترین پاسخ را مبتنی بر ظاهر ماجرا برمی‌گزیند؛ فارغ از این‌که در مراحل پیشین انتخاب چه بوده است و انتخاب فعلی چه گزینه‌های احتمالی را در پی دارد. از همین رو به این الگوریتم، الگوریتم حریصانه می‌گویند و در برنامه نویسی هم کاربرد دارد.
در نگاه کلی، سرعت و مرتبه زمانی الگوریتم حریصانه بهتر از روش‌های مشابه است. اگرچه رسیدن به جواب بهینه خاص و کلی، به ذات مسأله برمی‌گردد و لزوماً با این الگوریتم حاصل نمی‌شود. این الگوریتم را می‌توان جزو الگوریتم های بهینه‌سازی دسته‌بندی کرد، یعنی روش‌هایی که در حل مسائل بهینه‌سازی کاربرد دارند. همچنین الگوریتم حریصانه را می‌توان برای برخی از روش‌های دیگر، نظیر برنامه‌ریزی پویا، جایگزین مناسبی دانست.
الگوریتم حریصانه در برنامه‌های زیر کاربرد دارد:
- مرتب سازی از جمله مرتب سازی انتخابی و مرتب سازی توپولوژیکی
- الگوریتم های پریم و کروسکال
- مسأله تغییر سکه
- مسأله کوله‌پشتی
- الگوریتم زمان‌بندی کار
الگوریتم بازگشتی (Recursive)
الگوریتم بازگشتی (Recursive) که جزو سادهترین انواع الگوریتم به‌شمار می‌رود، مسأله اصلی را به زیرمسألههای کوچکتری تقسیم و البته همه آنها را با روشی یکسان حل میکند تا نتیجه حاصل گردد. گرچه در این الگوریتم به حالت پایه نیاز داریم تا عمل بازگشت و صدا زدن تابع تا ابد ادامه پیدا نکند (به عبارت دیگر الگوریتم برقرار باشد).
خاصیت بازگشتی ابزاری قدرتمند است که در حل مسأله به کمکمان می‌آید، اما عیب بزرگ و مهم این الگوریتم، ایجاد سربار اضافه از نظر حافظه و زمان است. بنابراین وقتی از این الگوریتم در برنامه نویسی بهره می‌گیریم و تابعی را به تعداد دفعات زیاد فراخوانی کنیم، مدیریت حافظهحافظه در کامپیوتر، همه چیز در مورد حافظه در معماری کامپیوتر
در این مقاله به بررسی کامل حافظه در کامپیوتر، انواع حافظه در کامپیوتر، کش، روش‌های آدرس دهی کش، نگاشت آدرس و موارد دیگر می‌پردازیم به یکی از اصلی‌ترین معضل‌ها بدل می‌گردد.
الگوریتم عقبگرد (Backtracking)
الگوریتم عقبگرد در حل مسائل از رویکرد Brute Force بهره می‌گیرد و خروجی را می‌یابد. اصطلاح عقبگرد به این مفهوم است که اگر راه حل فعلی مناسب نیست، به عقب برمی‌گردیم تا دیگر راه حل‌ها را امتحان کنیم. در نتیجه می‌توان آن را به‌نوعی رویکرد بازگشتی نیز دانست. این الگوریتم در برنامه نویسی و دیگر مسائل، در مواردی استفاده می‌شود که راه حل‌های متعددی دارند.
برنامه‌های کاربردی الگوریتم عقبگرد عبارتند از:
- تولید تمام رشته‌های باینری
- مسأله وزیر (N-Queens)
- مسأله کوله پشتی
- مسأله رنگ‌آمیزی نقشه
الگوریتم شاخه و کران (Branch & Bound)
الگوریتم شاخه و کران جزو الگوریتم های بهینه سازی ترکیباتی است. مسائل بهینه سازی معمولا پیچیدگی زمانی نمایی دارند (an, a>1) و در بدترین حالت، امکان دارد تمامی جایشگت‌های مسأله نیاز به بررسی داشته باشند. در الگوریتم شاخه و کران سعی بر این است که حالات اضافی را کنار بگذاریم و به گونه‌ای بعضی از جایگشت‌های مسأله را هرس کنیم. این الگوریتم از روش Backtracking برای بهینه‌سازی بهره می‌برد و برخی از شاخه‌های درخت را که در حالت بدی هستند، از مدار بررسی خارج میکند. این ترفند کمک میکند بسیاری از حالت‌ها را نادیده بگیریم و زمان حل مسأله را کاهش دهیم.
الگوریتم تقسیم و غلبه (Divide & Conquer)
الگوریتم تقسیم و غلبه در برنامه نویسی کاربرد بسیار زیادی دارد. در گام‌های این الگوریتم، مسأله را به زیرمسائلی تقسیم، آنها را حل و سپس با یکدیگر ترکیب می‌کنیم تا نتیجه نهایی (حل مسأله اصلی) حاصل گردد. پس می‌توان گفت الگوریتم تقسیم و غلبه دارای سه مرحله مجزا و بازگشتی است:
- تقسیم: مسأله را به چند زیرمسأله کوچک تقسیم می‌کنیم که به یکدیگر شباهت دارند.
- غلبه: زیرمسأله‌هایی را که به اندازه کافی کوچک و غیرقابل تقسیم هستند، به صورت بازگشتی حل می‌کنیم.
- ترکیب: راه حل هر زیرمسأله را با هم ترکیب می‌کنیم تا پاسخ مسأله اصلی حاصل گردد.
از این الگوریتم به‌طور گسترده در مسائل مختلف و البته برنامه نویسی استفاده می‌کنند، چون پایدار و بهینه است. برنامه های کاربردی الگوریتم تقسیم و غلبه عبارتند از:
- جستجوی باینری
- مرتب‌سازی ادغامی و سریع
- پیدا کردن میانه
- ضرب ماتریس
الگوریتم برنامه نویسی پویا (Dynamic)
الگوریتم پویا (Dynamic) همچون الگوریتم تقسیم و غلبه، مسأله را به زیرمسألههای کوچکتر می‌شکند. اما تفاوتش با الگوریتم تقسیم و غلبه در این است که زیرمسائل را به‌طور مستقل حل نمی‌کنیم، بلکه نتایج زیرمسائل را به خاطر سپرده و از آنها برای حل زیرمسألههای مشابه (آن‌هایی که هم‌پوشانی دارند) بهره می‌گیرد. الگوریتم پویا در مسائل بهینه سازی و برنامه نویسی کاربرد زیادی دارد.
برخی از برنامه های کاربردی الگوریتم پویا به شرح زیر است:
- یافتن طولانی‌ترین زیررشته مشترک، طولانی‌ترین زیررشته افزایشی، طولانی‌ترین زیررشته مشترک و...
- الگوریتم بلمن-فورد (Bellman-Ford)
- ضرب ماتریس زنجیره‌ای
- جمع زیرمجموعه
- مسأله کوله‌پشتی
جمع بندی
الگوریتم در ابعاد مختلف زندگی ما پرکاربرد است و در حل ساده ترین مسائل روزمره یا حتی پیچیده ترین امور نظیر برنامه نویسی که تنها با کمک فناوری قابل انجام هستند، نقش پررنگی دارد. الگوریتم در واقع گام به گام ما را تا حل مسأله پیش می‌برد و یاری‌مان میکند. در این مطلب کوشیدیم انواع الگوریتم را بررسی و موشکافی کنیم.
انواع الگوریتم را نام ببرید؟
الگوریتم در نگاه کلی و البته در دنیای کامپیوتر و برنامه نویسی، روش حل مسأله است. بسته به حوزه مورد بحث و مسائل پیش رو، الگوریتم های مختلف یا به عبارتی شیوه‌های مختلف حل مسأله هستند که به کار می‌آیند. برخی از مهم‌ترین الگوریتم‌ها که برای حل مسائل و به‌ویژه مسائل بهینه‌سازی به کار می‌آیند، عبارتند از الگوریتم Brute Force، الگوریتم حریصانه، الگوریتم بازگشتی، الگوریتم تقسیم و غلبه، الگوریتم شاخه و کران، الگوریتم عقبگرد و...
الگوریتم بازگشتی چه طور مسائل را حل می کند؟
الگوریتم بازگشتی (Recursive) از سادهترین انواع الگوریتم است. خاصیت بازگشتی ابزار قدرتمندی است که در حل مسائل مختلف و در برنامه نویسی کمکمان میکند، اما عیب بزرگش ایجاد سربار اضافه بهلحاظ حافظه و زمان است. الگوریتم بازگشتی مسأله اصلی را به زیرمسألههای کوچکتری تقسیم و البته همه آنها را با روشی یکسان حل میکند.
کارکرد الگوریتم تقسیم و غلبه چگونه است؟
الگوریتم تقسیم و غلبه که در برنامه نویسی کاربرد بسیار زیادی دارد، مسأله را به زیرمسائلی تقسیم، آنها را حل و سپس با یکدیگر ترکیب میکند تا نتیجه نهایی (حل مسأله اصلی) حاصل گردد. در واقع الگوریتم تقسیم و غلبه (Divide and Conquer) به‌نوعی سه مرحله مجزا و بازگشتی دارد و به کمک آنها مسأله را حل میکند.
