زنگ‌تفریح تصادفی

 پيوندهاي المپياد كامپيوتر
 سايت‌هاي المپياد كامپيوتر
 
 حريصانه اما ژنتيك! (زنگ تفريح شماره‌ي 19)
حريصانه اما ژنتيك! (زنگ تفريح شماره‌ي 19)زنگ تفريح كامپيوتر
اين زنگ تفريح، 2 نوع الگوريتم را به‌صورت مختصر با عنوان مثال‌هايى براى هركدام بررسى و مطالعه مى‌كند!

الگوريتم‌هاى حريصانه (Greedy)
 

اين نوع از الگوريتم مشابه برنامه‌نويسى پويا (Dynamic)، بيش‌تر براى حل مسائل بهينه‌سازى به‌كار مى‌روند. با اين اختلاف كه در برنامه‌سازى پويا از يك رابطه‌ي بازگشتى براى حل زيرمسأله‌ها استفاده مى‌كنند. در روش حريصانه (Greedy)، تقسيم مسأله‌ها به زيرمسأله‌ها انجام نمى‌گيرد و روش تكرارشونده را به‌كار مى‌برند.
در روش حريصانه (Greedy) در هر لحظه، با توجه به عناصر داده‌اى مفروض، عنصرى را كه داراى ويژگى بهترين يا بهينه است (مانند: كوتاه‌ترين مسير، بالاترين ارزش، كم‌ترين سرمايه‌گذارى، بيش‌ترين سود و ...) انتخاب مى‌كنند بدون اين‌كه انتخاب‌هاى قبلى ما بعدى را در نظر بگيرد ولى انتخاب‌هاى بهينه‌ي محلى همواره منجر به راه‌حل بهينه‌ي سراسرى نمى‌شود. اين روش انتخاب، منجر به ارائه يك الگوريتم ساده و كارامد مى‌شود.
تعيين درخت‌هاى پوشالى مينيمم با استفاده از الگوريتم‌هاى «پرايم»، «كراسكال» محاسبه كوتاه‌ترين مسير تك‌منبع با كاربرد الگوريتم «دايجسترا»، مسأله‌ي زمان‌بندى مانند: بهينه‌سازى زمان انتظار و سرويس به كاربران براى دسترسى به ديسك گردان‌ها در يك شبكه‌ي رايانه‌اى، تعيين حداكثر بهره براى مشتريان در يك زمان معين و مسأله‌ي كوله‌پشتى (كسرى، صفر و يك) (Knapsack) با استفاده از روش حريصانه (Greedy) قابل اجرا هستند.

 

مسأله‌ي كوله پشتى

(Knapsack )



الگوريتم‌هاي ژنتيك (Genetic)
 

اخيراً دانشمندان رشته‌ي رايانه از نظريه‌ي تاريخى «داروين» براى حل مسائل علمى پيچيده استفاده مى‌كنند تا بتوانند عمليات هوشمندانه را پيش ببرند. سه عامل اصلى نظريه‌ي «داروين» عبارتند از:


- تنوع

مشخصات والدين متفاوت با يكديگر تركيب شده تا بتوانند موجودى را با خصوصيات برتر به وجود آورند.


- تصادف

عاملى است كه تغييراتى را در موجود فرزند ايجاد مى كند.


- انتخاب

محيط، موجوداتى را گزينش مى كند كه داراى شايستگى بالاترى از لحاظ ادامه حيات و توليد مثل باشند.
 

مدلسازى در الگوريتم «ژنتيك» برپايه‌ي «فرايند طبيعى تكامل» و «اصل بقاى برتر» است و مشابه طبيعت، عمل را با حفظ و تقويت جنس برتر و از بين رفتن جنس ضعيف انجام مى‌دهد. در نتيجه منجر به ايجاد قدرتمندترين ساختار يا بهينه‌ترين آن براى بقا در محيط مى‌شود.

روش انتخاب ژنتيكى در طول ميليون‌ها سال، طبيعتى را پديد آورده كه براساس «اصل بقاى برتر» و «جهش سازنده» قادر به حل پيچيده‌ترين مسائل از جمله: ساختارهاى پروتئينى برپايه‌ي بهترين جانشين «آمينواسيدها» عمل مى‌كند.




با عرض سلام و خسته نباشید (به مناسبت پایان امتحانات!!) به کاربران گرامی !

دوستان عزیز ،

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

منتظر نظرات شما هستیم !

پیشاپیش از همکاری صمیمانه ی شما سپاس گذاریم !

موفق باشید !

1386/1/21 لينک مستقيم

نظر شما پس از تاييد در سايت قرار داده خواهد شد
نام :
پست الکترونيکي :
صفحه شخصي :
نظر:
تایید انصراف
 زنگ تفريح‌ها

 
 المپياد كامپيوتر

 

     

 

 

صفحه‌ي اصلي

     

 

راهنماي سايت

     

 

 

آموزش

     

 

بانك سوال

     

 

 

مسابقه

     

 

 

زنگ تفريح

     

 

 

مصاحبه و گزارش

     

 

 

معرفي كتاب

     

 

 

مشاوره

     

 

 

پرسش‌و‌پاسخ‌علمي

     

 

اخبار

 

فعاليت‌هاي علمي

 بازديدها
خطایی روی داده است.
خطا: بازديدها فعلا" غیر قابل دسترسی می باشد.