تلاش بى پایان ذهن انسان هاى کنجکاو براى کشف ناشناخته ها و حل مسائل جالب یکى از جنبه هاى زیباى زندگى است. تاریخ علم نشان مى دهد که دانشمندان و ریاضیدانان متعددى عمر طولانى خود را وقف حل معماهاى مختلف و شناسایى اسرارطبیعت و جامعه کرده و با حل هر مسأله نام خود را جاودانى کرده اند. تکنولوژى کامپیوتر با توجه به پیشرفت جهشى خود در ۶۰ سال اخیر، هم به عنوان یک ابزار حل مسأله، هم به عنوان منبعى از کاربردهاى متنوع آن، روز به روز جذاب تر شده و در این رابطه، الگوریتم به عنوان روش و مراحل حل مسأله، نقش کلیدى را در این فناورى ایفا مى کند. یک مثال ساده براى الگوریتم، دستورالعمل هاى لازم براى روى هم قرار دادن قطعات مدل هواپیماست. این مونتاژ از قطعه خاصى شروع شده و سپس قطعات دیگر به ترتیب تا کامل شدن مدل، روى هم قرار مى گیرند. یک برنامه کامپیوترى که براى پیاده سازى و اجراى الگوریتم ها روى رایانه به کار مى رود، مجموعه متناهى از دستوراتى است که به ترتیب معینى از نخستین دستور به ترتیب تاانتها باید اجرا شوند
.
این نوشته انواع الگوریتم ها را به صورت مختصر با عنوان مثال هایى براى هر کدام بررسى و مطالعه مى کند. منظور از انواع الگوریتم ها، ارائه یک راه حل جامع و کارآمد براى مسائل مختلف است. الگوریتم ها هسته مرکزى راه حل مسائل متعددى در بخش هاى علوم پایه، مسائل تجارى، رشته هاى مهندسى مانند طراحى پل ها، سدها، خودروها، هواپیماها، پیش بینى وضع جوى و نقشه هاى مربوطه، تجزیه و تحلیل ساختار مولکول ها و DNA، کشف ذخایر گاز و نفت و طراحى و بهینه سازى سیستم هاى کامپیوترى است.
از لحاظ تاریخى کلمه الگوریتم برگرفته از نام ریاضیدان معروف قرن نهم هجرى، الخوارزمى است که براى نخستین بار در کتاب معروف جبر و مقابله براى بعضى از مسائل ریاضى مانند معادلات خطى و معادلات درجه دوم، راه حل نوینى مطرح کرد که تا آن مقطع زمانى ارائه نشده بود. الگوریتم به عنوان مراحل حل یک مسأله یا انجام یک کار، مجموعه اى متناهى از دستورالعمل هایى است که براى رسیدن به خروجى هاى مطلوب با شروع از یک حالت اولیه به کار مى رود. در تعریف ریاضى الگوریتم به دستورالعمل ها یا رویه هاى خوش تعریف اطلاق مى شود که به وسیله ماشین تورینگ که یک مدل انتزاعى از کامپیوترهاى دیجیتال است، شبیه سازى و اجرا گردد.
روش هاى زیادى براى گروه بندى الگوریتم ها با توجه به قابلیت و توانایى هاى هر دسته وجود دارد. از یک دیدگاه کلى مى توان الگوریتم ها را به دو گروه عمده الگوریتم هاى ترتیبى و الگوریتم هاى موازى تقسیم کرد
.
الگوریتم هاى ترتیبى
در این گروه از الگوریتم ها، رایانه فقط از یک پردازنده براى اجراى دستورالعمل ها به صورت ترتیبى (سریال) استفاده مى کند. در این نوع رایانه ها که به نام معمارى فون نیومن معروف است، برنامه و داده ها در حافظه ذخیره مى شوند. ریزپردازنده هر بار یکى از دستورات برنامه را بازیابى کرده، پس از تفسیر آن را اجرا مى کند. چنین رایانه هایى را SLSD (جریان تک دستورى، جریان تک داده اى) مى گویند. در اینجا به ۲ روش از الگوریتم هاى ترتیبى اشاره مى شود.
روش تقسیم و حل
در این روش، با استفاده از رویه هاى بازگشتى، مسأله اصلى را به زیرمسأله هاى کوچکترى تا جایى تقسیم مى کنند که امکان تقسیم مجدد آن وجود نداشته باشد. سپس با حل ساده ترین زیرمسأله ها و ترکیب آنها با یکدیگر مى توان به حل مسأله اصلى نائل شد. رویه بازگشتى، الگوریتمى است که با استفاده از فراخوانى خودرویه، دستورات تشکیل دهنده آن را تا رسیدن به شرایط اولیه و خروج از آن، مکرر اجرا کند.
روش تقسیم و حل، یک روش طراحى بالا به پائین است، یعنى الگوریتم یک مسأله از سطح بالا به زیرمسأله ها تقسیم بندى مى شود. به عنوان مثال مى توان الگوریتم هاى جست وجوى دورویى در یک بردار (آرایه یک بعدى) یا در یک جدول (آرایه دوبعدى) ، مرتب سازى ترکیب و مرتب سازى سریع ، مسأله برج هاى هانوى ، ضرب «ماتریس به روش استراسن»، عملیات محاسباتى مانند ضرب و جمع اعداد صحیح بسیار بزرگ و جدول مسابقات تیم ها در یک جام حذفى را با استفاده از روش تقسیم و حل انجام داد.
الگوریتم برنامه نویسى پویا
در برنامه نویسى پویا به عنوان یک روش طراحى الگوریتم، چون راه حل مسأله از طریق تقسیم آن به زیرمسأله ها به دست مى آید، مشابه روش تقسیم وحل است ولى برعکس آن، یک روش پائین به بالا یا یک روش جز به کل است، یعنى حل مسأله را از ساده ترین زیرمسأله شروع کرده و با قراردادن نتایج در یک آرایه، آنها را در محاسبات بعدى استفاده مى کنند. در صورتى که روش تقسیم و حل فاقد حافظه است. این روش طراحى الگوریتم، داراى شرایط بهینه سازى است وزیرمسأله ها هم بهینه هستند. به عنوان مثال، اگر برنامه نویسى پویا، براى مسأله کوتاه ترین مسیر که با یک گراف مدل سازى مى شود به کار مى رود، هر زیرگرافى هم باید داراى ویژگى کوتاه ترین مسیر بین رأس هاى متشکله آن باشد. اگر اصل بهینه سازى براى یک مسأله مفروض، صدق کند مى توان یک رابطه بازگشتى براى حل مسأله و زیرمسأله ها ارائه داد.
الگوریتم فلوید براى تعیین کوتاه ترین مسیر، ضرب زنجیرى ماتریس ها، درخت هاى جست وجوى دورویى بهینه حاصل جمع بهینه لیستى از n عدد حقیقى، تعیین طولانى ترین زیر مشترک در دو رشته دلخواه و مسأله فروشنده دوره گرد (TSP) با استفاده از روش برنامه نویسى پویا قابل انجام هستند.
الگوریتم هاى حریصانه
الگوریتم هاى حریصانه مشابه برنامه نویسى پویا، بیشتر براى حل مسائل بهینه سازى به کار مى روند. با این اختلاف که در برنامه سازى پویا از یک رابطه بازگشتى براى حل زیرمسأله ها استفاده مى کنند. در روش حریصانه، تقسیم مسأله ها به زیر مسأله ها انجام نمى گیرد و روش تکرارشونده را به کار مى برند.
در روش حریصانه در هر لحظه، با توجه به عناصر داده اى مفروض، عنصرى را که داراى ویژگى بهترین یا بهینه است (مانند کوتاه ترین مسیر، بالاترین ارزش، کمترین سرمایه گذارى، بیشترین سود و ...) انتخاب مى کنند بدون این که انتخاب هاى قبلى ما بعدى را در نظر بگیرد ولى انتخاب هاى بهینه محلى همواره منجر به راه حل بهینه سراسرى نمى شود. این روش انتخاب، منجر به ارائه یک الگوریتم ساده و کارآمد مى شود.
تعیین درخت هاى پوشالى مینیمم با استفاده از الگوریتم هاى پرایم، کروسکال محاسبه کوتاه ترین مسیر تک منبع با کاربرد الگوریتم دایجسترا ، مسأله زمان بندى مانند بهینه سازى زمان انتظار و سرویس به کاربران براى دسترسى به دیسک گردان ها در یک شبکه رایانه اى، تعیین حداکثر بهره براى مشتریان در یک زمان معین و مسأله کوله پشتى (کسرى، صفرو یک) با استفاده از روش حریصانه قابل اجرا هستند.
الگوریتم عقب گرد
الگوریتم عقبگرد، براى یافتن جواب مسأله اى با فضاى جست وجو به طور گسترده اى به کار مى رود و از آن به عنوان حالت اصلاح شده جست وجوى عمقى یک درخت نام مى برند. در این روش، منظور از عقبگرد، پیدا کردن راه حل مسأله از طریق جست وجوى عمقى در درخت فضاى حالت براى یافتن گره هاى امید بخش است. در صورتى که موقع پیمایش درخت به یک گروه غیرامیدبخش برخورد کند که منجر یه یافتن جواب مسأله نمى شود، باید به سمت ریشه درخت برگشته و عمل جست وجو را در دیگر شاخه ها ادامه داد. این فرآیند را هرس کردن درخت فضاى حالت مى نامند.
به عنوان مثال، مسأله n وزیر، استفاده از الگوریتم مونت کارلو براى نخستین کارآیى یک الگوریتم عقبگرد، مسأله حاصل جمع زیرمجموعه ها، مسأله رنگ آمیز گراف، مسأله مدارهاى هامیلتونى، مسأله کوله پشتى صفر و یک با استفاده از راهبرد عقبگرد، قابل حل هستند.
الگوریتم شاخه وقید
روش شاخه و قید با ایجاد درختى از زیرمسأله ها با توجه به مسأله اولیه و پیمایش درخت بدون قاعده خاصى، دنبال جواب هاى مسأله مى گردد. این روش شکل بهبود یافته اى از الگوریتم عقبگرد است که در آن شیوه خاصى را براى ملاقات گره ها اعمال نمى کند و در هر گره براى امیدبخش بودن آن گره، قید یا عددى را محاسبه مى کند و فقط براى مسائل بهینه سازى استفاده مى شود. به عنوان مثال مسأله کوله پشتى صفر و یک، بهترین جست وجو با هرس کردن، ایجاد یک تور بهینه و محاسبه طول آن، مسأله فروشنده دوره گرد و استنباط با عکس العمل استفاده از روش شاخه و قید اجرا مى شود.
الگوریتم جست وجو و پیمایش
این روش روى دو گروه از مسائل قابل اعمال هستند:
الف روش هاى پیمایش
در روش هاى پیمایش، باید تک تک گره هاى یک درخت دودویى براى بررسى مقادیر عددى آنها ملاقات و بررسى جست وجو شوند.
ب روش هاى جست وجو
روش هاى جست وجو که حالت عمومى ترى نسبت به روش هاى پیمایش هستند، مى توانند روى رئوس یک گراف اعمال شوند.
جست وجو و پیمایش در درخت هاى دودویى و جست وجو و پیمایش گراف ها به صورت عرضى یا عمقى به وسیله این الگوریتم ها قابل حل هستند.