ارائه یک الگوریتم تقریبی نوین برای حل مسئله جنگل اشتاینر
سال انتشار: 1393
نوع سند: مقاله کنفرانسی
زبان: فارسی
مشاهده: 1,261
متن کامل این مقاله منتشر نشده است و فقط به صورت چکیده یا چکیده مبسوط در پایگاه موجود می باشد.
توضیح: معمولا کلیه مقالاتی که کمتر از ۵ صفحه باشند در پایگاه سیویلیکا اصل مقاله (فول تکست) محسوب نمی شوند و فقط کاربران عضو بدون کسر اعتبار می توانند فایل آنها را دریافت نمایند.
- صدور گواهی نمایه سازی
- من نویسنده این مقاله هستم
استخراج به نرم افزارهای پژوهشی:
شناسه ملی سند علمی:
AEBSCONF01_235
تاریخ نمایه سازی: 6 آبان 1393
چکیده مقاله:
همان طور که می دانیم مسائل NP مسائلی هستند که راه حل بهینه برای آن ها وجود ندارد و تا جایی که حل بعضی از آن ها توسط ابررایانه ها با روش های کلاسیک بیش از 300 سال به طول می انجامد. از آنجایی که این گونه مسائل کاربردهای فراوان دارند، ارائه یک روش بهینه می تواند علم، صنعت و در نتیجه ی آن زندگی انسان ها را متحول کند. مسئله جنگل های اشتاینر از جمله مسائل کلاسیک NP است که کاربردهای بسیاری در طراحی مدارهای VLSI، مسیریابی شبکه و بازسازی درخت تکامل نژادی در زیست شناسی و طراحی شبکه دارد. در این مقاله مسئله جنگل های اشتاینر بررسی خواهند شد و پس از بررسی صورت مسئله، راه حل بهینه ای برای آن ها ارائه خواهیم کرد. این راه حل استفاده از الگوریتم های تقریبی می باشد. به این منظور راه حل موجود را بررسی کرده، ایرادات وارد بر راه حل را بر خواهیم شمرد و الگوریتم تقریبی ارائه خواهیم نمود که این ایرادات را برطرف سازد.
کلیدواژه ها:
الگوریتم تقریبی ، درخت اشتاینر ، جنگل اشتاینر ، مسائل NP ، کاهش پذیری ، قضیه کودک ، مسئله SAT ، مسئله MST
نویسندگان
سید فرید سید السادات
تهران- خیابان پیروزی- بلوار ابوذر- بلوار آهنگ- دانشگاه آزاد اسلامی واحد تهران جنوب- دانشکده تحصیلات تکمیلی
علی معینی
تهران- خیابان انقلاب اسلامی- دانشگاه تهران- دانشکده علوم مهندسی- دپارتمان الگوریتم و محاسبات- معاونت آموزشی و تحصیلات تکمیلی
مراجع و منابع این مقاله:
لیست زیر مراجع و منابع استفاده شده در این مقاله را نمایش می دهد. این مراجع به صورت کاملا ماشینی و بر اساس هوش مصنوعی استخراج شده اند و لذا ممکن است دارای اشکالاتی باشند که به مرور زمان دقت استخراج این محتوا افزایش می یابد. مراجعی که مقالات مربوط به آنها در سیویلیکا نمایه شده و پیدا شده اند، به خود مقاله لینک شده اند :