مشاهده مشخصات مقاله
الگوريتم‌هايي براي بدست آوردن دو درخت پوشاي کمينه
|
Authors |
-
مهدی وجدی
-
محمدرضا رزازی
-
مهدی وجدی
-
محمدرضا رزازی
-
مهدی وجدی
-
محمدرضا رزازی
|
|
Conference |
شانزدهمین کنفرانس ملی سالانه انجمن کامپیوتر ایران |
|
Abstract |
درخت هاي پوشاي کمينه يکي از پر کاربردترين ها ساختمان داده ها در علوم هستند. در مسئله دو درخت پوشاي کمينه هدف پوشش دادن مجموعه نقاط با دو درخت جدا از هم است که مجموع طول اين دو درخت کمينه باشد. کاربرد اين مسئله در مواردي است که نياز به سرويس‌رساني به مجموعه اي از نقاطِ تقاضا توسط دو سرويس‌دهنده باشد و بخواهيم مجموع مسافت طي شده و يا طول شبکة ايجاد شده جهت ارائه سرويس را کمينه کنيم. اين مسئله مي‌تواند با محدوديت هاي مختلفي نيز بررسي شود. در اين مقاله ما ابتدا يک الگوريتم بهينه براي مسئله در حالت کلي ارائه مي‌دهيم و سپس به بررسي مسئله با محدوديت مساوي بودن تعداد گره هاي دو درخت مي‌پردازيم. در اين حالت براي مسئله دو الگوريتم مکاشفه‌اي و ژنتيک ارائه مي‌کنيم و به مقايسه نتايج آن‌ها با جواب هاي دقيق مسئله و با يکديگر مي‌پردازيم. نتايج مقايسه نشان دهنده آن است که الگوريتم ژنتيک ارائه شده مي‌تواند در زماني خوب و با دقتي مناسب به حل مسئله بپردازد. |
|
قیمت |
-
برای اعضای سایت : 100,000 Rial
-
برای دانشجویان عضو انجمن : 20,000 Rial
-
برای اعضای عادی انجمن : 40,000 Rial
|
خرید مقاله
|
|
.gif){kind=icon}