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

 پيوندهاي المپياد كامپيوتر
 سايت‌هاي المپياد كامپيوتر
 
 حل مسأله‌ي درخت پوشا با کم‌ترین هزینه به‌کمک پیمایش DFS (زنگ تفريح شماره‌ي 23)
حل مسأله‌ي درخت پوشا با کم‌ترین هزینه به‌کمک پیمایش DFS (زنگ تفريح شماره‌ي 23)زنگ تفريح كامپيوتر
کمی با تحقيقات محققان معاصر کشورمان در زمینه‌ي علوم رایانه بیشتر آشنا شویم!

مقدمه
در این زنگ تفریح قصد داریم ضمن معرفی کردن یک مقاله ي علمی که توسط اساتید دانشگاه تهران در رابطه با «حل مسأله‌ي درخت پوشا با کم‌ترین هزینه به‌کمک پیمایش DFS» (در مورد پیمایش عمقی گراف DFS در زنگ تفريح‌های آینده توضیحات کاملی خواهیم داد)، به بیان این مطلب بپردازیم که آیا با ما با چنین افرادی که در کشورمان دست به این امور تحقیقاتی می‌زنند آشنا هستیم!؟


مقاله




A New Algorithm for Minimum Spanning Tree
 Using Depth-First Search (DFS) In an Undirected Graph

الگوریتمی جدید برای درخت پوشا با کم‌ترین هزینه با استفاده از جستجوی ژرفایی در گراف غیرجهت‌دار

این الگوریتم جدید برای مسأله‌ي درخت پوشا با کم‌ترین هزینه در هر گراف غیر جهت‌دار ارائه شده است. در این الگوریتم از هیچ‌گونه الگوریتم Sort یا صف اولویت (Priority Queue) یا پشته‌ی دودویی (Binary Heap) استفاده نشده است.
این الگوریتم بر پایه‌ی جستجوی ژرفایی (DFS) و حذف سنگین‌ترین یال دیده شده دایره در DFS است. این الگوریتم در بدترین حالت، برای گرافی با راس و  یال زمان  را می‌گیرد (در مورد نماد O در زنگ تفریح مر بوط به پیچیدگی الگوریتم‌ها توضیح داده شده است) که در آن:

 





معرفي


 

مشهورترین الگوریتم‌ها برای حل مسأله‌ي «درخت پوشا با کم‌ترین هزینه»، «الگوریتم کروسکال» (Kruskal) و «الگوریتم پریم» (Prim) می‌باشند. این الگوریتم‌ها یک روش ابتکاری برای بهینه‌سازی ارائه دادند که به آن Greedy Strategy  (یا همان حریصانه كه در زنگ تفریح‌های نوروزی در مورد آن توضیح لازم داده شده است) می‌گویند. در هر مرحله از الگوریتم، یکی از چندین انتخاب‌ها باید ساخته شود.

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

با استفاده از «پشته‌ي فیبوناچی» (Fibonacci Heap) می‌توان سرعت الگوریتم پریم (Prim) را افزایش داد تا در مدت  اجرا شود.

این الگوریتم که ارائه شده (DHEA)، استراتژی مشابهی دارد که از DFS پیروی می‌کند و آن این است که گراف را به‌صورت ژرفایی جستجو می‌کند. هنگامی که دایره دیده شد سنگین‌ترین یال در دایره حذف می‌شود. این فرایند تا زمانی ادامه پیدا می‌کند که جستجوی ژرفایی پایان یابد. این الگوریتم زمان    را می‌گیرد جایی که k تعداد یال‌های بازگشت (Back Edges) در DFS است. بر حسب خصوصیات گراف:

 

در نتيجه این الگوریتم می‌تواند برای گراف‌هایی که اختلاف تعداد رؤوس و یال‌های آن‌ها کوچک است، مناسب باشد.



الگوريتم


 

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


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

دوستان عزیز ،

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

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

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

موفق باشید !

1386/3/12لينک مستقيم

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

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

 

     

 

 

صفحه‌ي اصلي

     

 

راهنماي سايت

     

 

 

آموزش

     

 

بانك سوال

     

 

 

مسابقه

     

 

 

زنگ تفريح

     

 

 

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

     

 

 

معرفي كتاب

     

 

 

مشاوره

     

 

 

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

     

 

اخبار

 

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

 بازديدها
كاربران غيرعضو آنلاينكاربران غيرعضو آنلاين:  7912
 كاربران عضو آنلاين:  0
  کل كاربران آنلاين:  7912