الگوریتم چیست؟ انواع الگوریتم و کاربرد آن ها

الگوریتم از پرکاربردترین اصطلاحاتی است که مخصوصاً در حوزه برنامه نویسی و کامپیوتر بیشتر با آن مواجه می شویم. دستورالعمل پخت یک غذا، بهترین مثال برای درک کاربرد algorithm است. یک سری دستور متوالی برای رسیدن به یک نتیجه مورد انتظار.

الگوریتم، مجموعه ای از دستورالعمل ها است که به صورت مرحله ای برای رسیدن به یک نتیجه موردانتظار طراحی شده اند. برنامه نویسی پویا، تقسیم و غلبه و بازگشتی از معروف ترین الگوریتم هایی هستند که برای حل مسائل متنوع بکار می روند.

الگوریتم ها دارای انواع مختلفی هستند که هر کدام متناسب با ویژگی ها و ساختار خود در زمینه های مختلف کاربرد دارند. آشنایی با ساختار و کاربرد هر کدام از آنها به شما کمک می کند که بیشتر متوجه اهمیت آنها در دنیای برنامه نویسی شوید.

الگوریتم چیست؟

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

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

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

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

ویژگی های یک الگوریتم خوب

با توجه به این که از هر دستور پختی برای تهیه یک غذای خاص استفاده نمی کنیم، همه دستورالعمل های نوشته شده برای برنامه نویسی هم، یک algorithm مناسب محسوب نمی شوند. برای این که توالی دستورات خاص در قالب یک الگوریتم، ارائه شوند باید ویژگی های خاصی داشته باشند:

• همه مراحل مربوط به algorithm، واضح، مشخص و بدون ابهام باشند.
• در صورت نیاز به ورودی، ورودی ها باید به طور کامل تعریف شوند.
• حداقل یک خروجی داشته باشد و به طور کامل تعریف شود.
• هر مرحله از الگوریتم موثر باشد و وظیفه خاصی داشته باشد.
• الگوریتم باید متناهی باشد یعنی بعد از یک مدت زمان مشخص به پایان برسد.
• الگوریتم باید ساده، عمومی و کاربردی باشد تا با منابع موجود بتوان آن را اجرا کرد.
• الگوریتم های طراحی شده باید مستقل از زبان باشد و دارای دستورالعمل هایی باشد که با هر زبان برنامه نویسی قابل پیاده سازی باشد و خروجی آن در همه زبان ها یکی باشد.

اجزای یک الگوریتم

الگوریتم ها اجزای مختلفی دارند که بسته به کاربردشان می توانند متفاوت باشند ولی در کل هر algorithm دارای 4 جزء اصلی است: ورودی، شرط، تکرار و خروجی

1. ورودی و خروجی

همانطور که قبلاً هم گفتیم، الگوریتم ها دنباله ای از مراحل هستند که دست به دست هم می دهند تا به یک خروجی مشخص برسند. یک مثال از زندگی واقعی این است که وقتی به شکر نیاز داریم، باید نیشکر را به عنوان ورودی بدهیم یا الگوریتم تشخیص چهره گوشی هوشمند برای باز کردن قفل گوشی، به تصویر چهره شما نیاز دارد تا با بررسی ویژگی های چهره شما و مقایسه آن با تصویری که قبلاً ذخیره کرده اید، در مورد باز کردن قفل گوشی تصمیم بگیرد.

2. دنباله مراحل الگوریتم (شرط و تکرار)

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

شرط: شرط ها، معیاری برای تغییر مسیر ورودی هستند. به عنوان مثال، استفاده از طرح تخفیف برنامه رزرو بلیط مخصوص 65 سال به بالا ها، نیاز به مرحله ای دارد که سن شخص را بررسی کند تا ببیند بالای 65 سال است یا نه.

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

مراحل الگوریتم در برنامه نویسی

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

تعریف مسئله: چه کاری باید انجام دهیم؟

جمع آوری داده ها: برای حل این مشکل، چه داده ها یا ورودی هایی داریم؟

پردازش داده ها: تبدیل داده های ورودی به یک فرم قابل استفاده.

یک رویکرد منطقی: بکار بردن داده های پردازش شده در منطق حل مسئله

راه حل: ارائه راه حل با استفاده از زبان طبیعی، ابزار گرافیکی، نمودار، فلوچارت، کد یا شبه کد

انواع الگوریتم ها و کاربرد آنها

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

1) Brute Force

Brute Force، ساده ترین الگوریتمی است که می توان برای حل یک مسئله در نظر گرفت. این الگوریتم، همه گزینه های ممکن برای حل یک مسئله را به صورت کورکورانه امتحان می کند تا به یک راه حل بهینه برسد. مثل تکنیک ساده ای که برای باز کردن قفل 4 رقمی یک گاوصندوق به کار می بریم. ترکیب 4 رقمی از اعداد 0 تا 9 را آنقدر تکرار می کنیم تا در نهایت به یک ترکیب درست برسیم و در گاوصندوق باز شود.

Brute Force به راحتی قابل پیاده سازی است و پیچیدگی زمانی و هزینه محاسباتی آن به تعداد راه حل های کاندید بستگی دارد. در کل، Brute Force مناسب مسائلی است که محدود و کوچک هستند و مشکلات پیچیده و بزرگی ندارند.

الگوریتم Brute Force زمانی استفاده می شود که هیچ الگوریتم دیگری برای سرعت بخشیدن به فرآیند وجود نداشته باشد و برنامه نویس باید همه راه حل های ممکن را تست کند.

شبه کد مرتب سازی انتخابی (selection sort) با روش Brute Force:

این الگوریتم هر بار، کل اعداد لیست را با هم مقایسه می کند و کوچکترین عدد را انتخاب می کند و در ابتدای لیست قرار می دهد.

2) حریصانه یا Greedy

روش حریصانه یکی از الگوریتم های ساده و موثر است که بیشتر در مسائل مربوط به بهینه سازی استفاده می شود. این روش از هر استراتژی استفاده می کند تا بهترین راه حل برسد. شاید فکر کنید که دو روش Brute Force و Greedy یکی هستند ولی روش حریصانه از لحاظ زمان محاسبه کارآمدتر از Brute Force و به مراتب به نتایج بهتری می رسد.

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

این الگوریتم در حل مسائلی مثل کوله پشتی کسری، مرتب سازی توپولوژیکی و زمان بندی کار به کار می رود.

شبه کد کوله پشتی کسری با روش حریصانه:

نسبت قیمت به وزن همه اشیا را محاسبه می کنیم و شیئی که دارای بیشترین نسبت است را انتخاب می کنیم و در داخل کوله قرار می دهیم. اگر از این شی چند تا داشته باشیم، تعدادی را قرار می دهیم که کمتر یا مساوی ظرفیت کیسه باشد. بعد اگر ظرفیت فعلی کیسه، کمتر از وزن این شی باشد، برای اشیاء بعدی نیز همین عمل را تکرار میکنیم تا ظرفیت کیسه کامل شود.

3) الگوریتم بازگشتی

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

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

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

شبه کد تابع فاکتوریل با روش بازگشتی:

برای محاسبه فاکتوریل یک عدد، با فراخوانی بازگشتی تابع، مقدار فاکتوریل اعداد قبلی محاسبه می شوند و با ضرب آنها در مقدار ورودی تابع، خروجی موردنظر حاصل می شود.

4) Backtracking

Backtracking، نسخه توسعه یافته الگوریتم brute force است و به نحوی، روش بازگشتی و brute force را ترکیب می کند.

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

روش Backtracking برای حل مسائلی مثل N-Queens، کوله پشتی، رنگ آمیزی گراف و تولید تمام رشته های باینری کاربرد دارد.

شبه کد تولید رشته های باینری با روش Backtracking:

در این مسئله، n به عنوان ورودی لازم برای تعیین طول رشته دریافت می شود و بعد رشته های باینری به ترتیب صعودی محاسبه می شوند.

به عنوان مثال اگر n=3 باشد، یکی از نقاط شکست برای برگشت به عقب بعد از رشته 011 اتفاق می افتد، همان جایی که همه رشته های باینری دوتایی برای دو رقم آخر نوشته شده اند و به 11 رسیده است و چاره ای ندارد مگر این که به عقب برگردد و با رشته 100 ادامه دهد.

5) تقسیم و غلبه

این رویکرد، مسئله را به مسائل فرعی کوچکتر تقسیم می کند و بعد، نتیجه این زیر مسائل را با هم ترکیب می کند تا به نتیجه نهایی برسد. پس این روش تقسیم و غلبه دارای 3 مرحله اصلی است: تقسیم، حل و ترکیب.

الگوریتم تقسیم و غلبه در حل بسیاری از مسائل به کار می رود و دلیل آن هم این است که راه حل پایدار و بهینه ای را ارائه می دهد.

مسائلی مثل جستجوی باینری، مرتب سازی ادغامی، پیدا کردن میانه و ضرب ماتریس با این روش قابل حل هستند.

شبه کد مرتب سازی ادغامی با روش تقسیم و غلبه:

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

6) برنامه نویسی پویا

عملکرد روش برنامه نویسی پویا شبیه تقسیم و غلبه است ولی با این تفاوت که نتایج حاصل از زیرمسائل ذخیره می شوند تا در آینده استفاده شوند و از محاسبات تکراری جلوگیری شود. این الگوریتم کاربرد بسیار زیادی دارد ولی دلیل آن هم این است که کارآمدترین روش را برای حل مسئله ارائه می دهد و از نظر پیچیدگی زمانی هم بهینه است.

این روش دارای دو نسخه است:

رویکرد پایین به بالا – در این روش، اول زیرمسائل حل می شوند و از نتایج آنها برای حل زیر مسائل بالایی و در نتیجه مسئله اصلی استفاده می شود.

رویکرد بالا به پایین – مسئله اصلی از همان ابتدا حل می شود تا اینکه نوبت به زیر مسئله موردنظر برسد و با استفاده از نتایج مسائل قبلی، حل شود.

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

شبه کد دنباله فیبوناچی به روش برنامه نویسی پویا:

برای حل این مسئله به نقطه شکست نیاز داریم تا فراخوانی تابع بازگشتی در یک جایی به پایان برسد و این نقاط هم با شرط های n==0 و n==1 لحاظ شده اند.

دنباله فیبوناچی با فراخوانی بازگشتی تابع و حفظ مقادیر قبلی برای استفاده در محاسبات بعدی به دست می آید.

7) الگوریتم تصادفی

این الگوریتم، تصمیم گیری خود را بر اساس عناصر تصادفی انجام می دهد یعنی در منطق خود از این عناصر استفاده می کند.

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

مرتب سازی سریع تصادفی و Kager’s از مهم ترین مسائلی هستند که در روش حل آنها از الگوریتم تصادفی استفاده می شود.

شبه کد مرتب سازی سریع با روش تصادفی:

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

 استفاده از الگوریتم در حل مسائل چه مزایا و معایبی دارد؟

مزایا

• درک نحوه کار الگوریتم راحت است.
• نمایش راه حل مسئله به صورت مرحله ای باعث روشن شدن مسیر می شود.
• حل مسئله به زیر مسائل، کار را برای برنامه نویس راحت تر می کند.

معایب

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

در کل، یک الگوریتم به ما کمک می کند تصمیم بگیریم که آیا مسئله موردنظر قابل حل است یا نه. اگر جواب بله بود که چه بهتر، باید به فکر نحوه ارائه یک راه حل سریع و دقیق باشیم. اگر جواب نه بود، الگوریتم به ما کمک می کند که تصمیم بگیریم آیا می توانیم بخشی از مشکل را حل کنیم یا نه.

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

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

کلام آخر

نقش الگوریتم ها در دنیای برنامه نویسی و IT غیر قابل انکار است. الگوریتمی از ویژگی های مناسب برخوردار باشد و استفاده بهینه از منابع سیستم داشته باشد، می تواند در زمینه برنامه نویسی موثر واقع شود. انواع الگوریتم هایی که در این مقاله بررسی کردیم، هر کدام متناسب با ساختار خود، کاربردهای خاصی دارند که می توانند پروسه حل مسئله را سریع تر و موثرتر جلو ببرند.

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