آشنایی با طراحی الگوریتم ها

[smh]

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

----------------------------------------------------
مناف ـ شریف زاده
روزنامه ایران

[K A S R A]

الگوریتم ... یعنی قلب تپنده نرم افزار . به جرات میشه گفت : بحث طراحی الگوریتم مهمترین قسمت علم مهندسی نرم افزاره ...
به زبان ساده : طراحی الگوریتم , تکنیک ها و روش های حل مسئله .
یه مثال جالب : برای مشاهده این لینک/عکس می بایست عضو شوید ! برای عضویت اینجا کلیک کنید
مسئله فروشنده دوره گرد یکی از مسائل معروف و NP Compelete ( دسته ای از مسائل که هنوز هیچ راه حل کار آمدی برای حل کردنشون وجود نداره اما غیر ممکن بودن حل این دسته از مسائل هنوز اثبات نشده )
هست ... که با یه مدلسازی ساده میشه خیلی از مسائل کامپیوتری NP Compelete رو با این مسئله هم ارز در نظر گرفت ... برای مشاهده این لینک/عکس می بایست عضو شوید ! برای عضویت اینجا کلیک کنید
صورت مسئله :
یه فرو شنده قصد داره یرای فروش اجناسش از تعدادی شهر (n شهر ) , که هر شهر با چندین شهر دیگه بوسیله یه جاده وصل شده , سفر کنه . در ضمن فروشنده باید از شهر خودش شروع به حرکت کنه , از همه شهرها یه بار عبور کنه و دوباره به جای اولش برگرده .
هدف : حداقل کردن زمان سفره . یعنی یافتن کوتاهترین مسیر برای سفر (البته با شرایط بالا) ...
این مسئله به ظاهر ساده میتونه قویترین Super Computer ها رو به زانو در بیاره ... برای مشاهده این لینک/عکس می بایست عضو شوید ! برای عضویت اینجا کلیک کنید
اگر فرض کنیم حافظه ی کافی در اختیار داریم ... برای n = 60 ( تعداد شهرها)
بهترین و بهینه ترین الگوریتمی که تاکنون برای حل این مسئله پیشنهاد شده به مدت زمانی در حدود 3857 سال زمان بر روی قویترین Super Computer برای حل احتیاج داره ...
البته همین روش , برای زمانی که n=40 باشه در حدود 45 ثانیه و روی یک Pc معمولی کارو تموم میکنه ...
در صورتی که یک الگوریتم نا کار آمد برای n = 20 هم به سالها زمان برای یافتن پاسخ احتیاج داره
اهمیت طراحی الگوریتم اینجا مشخص میشه ...

موفق باشید
کسری
برای مشاهده این لینک/عکس می بایست عضو شوید ! برای عضویت اینجا کلیک کنید