آشنایی با طراحی الگوریتم ها
ریاضی،جبر،هندسه تلاش بی پایان ذهن انسان های کنجکاو برای کشف ناشناخته ها و حل مسائل جالب یکی از جنبه های زیبای زندگی است. تاریخ علم نشان می دهد که دانشمندان و ریاضیدانان متعددی عمر طولانی خود را وقف حل معماهای مختلف و شناسایی اسرارطبیعت و جامعه کرده و با حل هر مسأله نام خود را جاودانی کرده اند.
تکنولوژی کامپیوتر با توجه به پیشرفت جهشی خود در ۶۰ سال اخیر، هم به عنوان یک ابزار حل مسأله، هم به عنوان منبعی از کاربردهای متنوع آن، روز به روز جذاب تر شده و در این رابطه، الگوریتم به عنوان روش و مراحل حل مسأله، نقش کلیدی را در این فناوری ایفا می کند. یک مثال ساده برای الگوریتم، دستورالعمل های لازم برای روی هم قرار دادن قطعات مدل هواپیماست. این مونتاژ از قطعه خاصی شروع شده و سپس قطعات دیگر به ترتیب تا کامل شدن مدل، روی هم قرار می گیرند. یک برنامه کامپیوتری که برای پیاده سازی و اجرای الگوریتم ها روی رایانه به کار می رود، مجموعه متناهی از دستوراتی است که به ترتیب معینی از نخستین دستور به ترتیب تا انتها باید اجرا شوند.
این نوشته انواع الگوریتم ها را به صورت مختصر با عنوان مثال هایی برای هر کدام بررسی و مطالعه می کند. منظور از انواع الگوریتم ها، ارائه یک راه حل جامع و کارآمد برای مسائل مختلف است. الگوریتم ها هسته مرکزی راه حل مسائل متعددی در بخش های علوم پایه، مسائل تجاری، رشته های مهندسی مانند طراحی پل ها، سدها، خودروها، هواپیماها، پیش بینی وضع جوی و نقشه های مربوطه، تجزیه و تحلیل ساختار مولکول ها و DNA، کشف ذخایر گاز و نفت و طراحی و بهینه سازی سیستم های کامپیوتری است.
از لحاظ تاریخی کلمه الگوریتم برگرفته از نام ریاضیدان معروف قرن نهم هجری، الخوارزمی است که برای نخستین بار در کتاب معروف جبر و مقابله برای بعضی از مسائل ریاضی مانند معادلات خطی و معادلات درجه دوم، راه حل نوینی مطرح کرد که تا آن مقطع زمانی ارائه نشده بود. الگوریتم به عنوان مراحل حل یک مسأله یا انجام یک کار، مجموعه ای متناهی از دستورالعمل هایی است که برای رسیدن به خروجی های مطلوب با شروع از یک حالت اولیه به کار می رود.
در تعریف ریاضی الگوریتم به دستورالعمل ها یا رویه های خوش تعریف اطلاق می شود که به وسیله ماشین تورینگ که یک مدل انتزاعی از کامپیوترهای دیجیتال است، شبیه سازی و اجرا گردد.
روش های زیادی برای گروه بندی الگوریتم ها با توجه به قابلیت و توانایی های هر دسته وجود دارد. از یک دیدگاه کلی می توان الگوریتم ها را به دو گروه عمده الگوریتم های ترتیبی و الگوریتم های موازی تقسیم کرد.

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