ارائه یک الگوریتم تقریبی نوین برای حل مسئله جنگل اشتاینر
- سال انتشار: 1393
- محل انتشار: همایش ملی الکترونیکی دستاوردهای نوین در علوم مهندسی و پایه
- کد COI اختصاصی: AEBSCONF01_235
- زبان مقاله: فارسی
- تعداد مشاهده: 1263
نویسندگان
تهران- خیابان پیروزی- بلوار ابوذر- بلوار آهنگ- دانشگاه آزاد اسلامی واحد تهران جنوب- دانشکده تحصیلات تکمیلی
تهران- خیابان انقلاب اسلامی- دانشگاه تهران- دانشکده علوم مهندسی- دپارتمان الگوریتم و محاسبات- معاونت آموزشی و تحصیلات تکمیلی
چکیده
همان طور که می دانیم مسائل NP مسائلی هستند که راه حل بهینه برای آن ها وجود ندارد و تا جایی که حل بعضی از آن ها توسط ابررایانه ها با روش های کلاسیک بیش از 300 سال به طول می انجامد. از آنجایی که این گونه مسائل کاربردهای فراوان دارند، ارائه یک روش بهینه می تواند علم، صنعت و در نتیجه ی آن زندگی انسان ها را متحول کند. مسئله جنگل های اشتاینر از جمله مسائل کلاسیک NP است که کاربردهای بسیاری در طراحی مدارهای VLSI، مسیریابی شبکه و بازسازی درخت تکامل نژادی در زیست شناسی و طراحی شبکه دارد. در این مقاله مسئله جنگل های اشتاینر بررسی خواهند شد و پس از بررسی صورت مسئله، راه حل بهینه ای برای آن ها ارائه خواهیم کرد. این راه حل استفاده از الگوریتم های تقریبی می باشد. به این منظور راه حل موجود را بررسی کرده، ایرادات وارد بر راه حل را بر خواهیم شمرد و الگوریتم تقریبی ارائه خواهیم نمود که این ایرادات را برطرف سازد.کلیدواژه ها
الگوریتم تقریبی، درخت اشتاینر، جنگل اشتاینر، مسائل NP، کاهش پذیری، قضیه کودک، مسئله SAT، مسئله MSTاطلاعات بیشتر در مورد COI
COI مخفف عبارت CIVILICA Object Identifier به معنی شناسه سیویلیکا برای اسناد است. COI کدی است که مطابق محل انتشار، به مقالات کنفرانسها و ژورنالهای داخل کشور به هنگام نمایه سازی بر روی پایگاه استنادی سیویلیکا اختصاص می یابد.
کد COI به مفهوم کد ملی اسناد نمایه شده در سیویلیکا است و کدی یکتا و ثابت است و به همین دلیل همواره قابلیت استناد و پیگیری دارد.