ارائه یک الگوریتم تقریبی نوین برای حل مسئله جنگل اشتاینر

همان طور که می دانیم مسائل NP مسائلی هستند که راه حل بهینه برای آن ها وجود ندارد و تا جایی که حل بعضی از آن ها توسط ابررایانه ها با روش های کلاسیک بیش از 300 سال به طول می انجامد. از آنجایی که این گونه مسائل کاربردهای فراوان دارند، ارائه یک روش بهینه می تواند علم، صنعت و در نتیجه ی آن زندگی انسان ها را متحول کند. مسئله جنگل های اشتاینر از جمله مسائل کلاسیک NP است که کاربردهای بسیاری در طراحی مدارهای VLSI، مسیریابی شبکه و بازسازی درخت تکامل نژادی در زیست شناسی و طراحی شبکه دارد. در این مقاله مسئله جنگل های اشتاینر بررسی خواهند شد و پس از بررسی صورت مسئله، راه حل بهینه ای برای آن ها ارائه خواهیم کرد. این راه حل استفاده از الگوریتم های تقریبی می باشد. به این منظور راه حل موجود را بررسی کرده، ایرادات وارد بر راه حل را بر خواهیم شمرد و الگوریتم تقریبی ارائه خواهیم نمود که این ایرادات را برطرف سازد.

Keywords:

الگوریتم تقریبی , درخت اشتاینر , جنگل اشتاینر , مسائل NP , کاهش پذیری , قضیه کودک , مسئله SAT , مسئله MST