الگوریتمی ابتکاری برای ساخت درخت اشتاینرکمینه اقلیدسی درون چند ضلعی متعامد
Publish Year: 1392
نوع سند: مقاله کنفرانسی
زبان: Persian
View: 612
متن کامل این Paper منتشر نشده است و فقط به صورت چکیده یا چکیده مبسوط در پایگاه موجود می باشد.
توضیح: معمولا کلیه مقالاتی که کمتر از ۵ صفحه باشند در پایگاه سیویلیکا اصل Paper (فول تکست) محسوب نمی شوند و فقط کاربران عضو بدون کسر اعتبار می توانند فایل آنها را دریافت نمایند.
- Certificate
- من نویسنده این مقاله هستم
استخراج به نرم افزارهای پژوهشی:
شناسه ملی سند علمی:
TIAU01_346
تاریخ نمایه سازی: 14 شهریور 1393
Abstract:
مسئله درخت اشتاینر، عبارت است از پیدا کردن درخت کمینه ای که شامل نقاط مشخصی باشد و در صورت لزوم از تعدادی نقاط کمکی نیز برای کمینه کردن طول درخت استفاده کند.دراین مقاله درخت اشتاینر درحالتی بررسی شده است که رئوس و یالهای درخت در داخل یک چند ضلعی متعامد قرار گرفته اند. این مسئله در طراحی خطوط نفت و بزرگراه ها و طراحی مدارات مجتمع الکترونیکی کاربرد بسیاری دارد. این مسئله Np-hardبوده و الگوریتمی تا کنون با زمان چندجمله ای برای آن شناخته نشده است .دراین مقاله الگوریتمی برای ساخت درخت اشتاینر با استفاده از گراف پیشنهاد شده است و در برخی موارد به جواب های بهینه رسیده ایم.
Keywords:
Authors
ع خسروی نژاد
دانشجو کارشناسی ارشد کامپیوتر دانشگاه آزاد قزوین
ع باقری
دکترای کامپیوتر عضو هیئت علمی دانشگاه امیرکبیر
م کیوان پور
دکترای کامپیوتر عضو هیئت علمی دانشگاه آزاد قزوین
خسروی نژاد
دانشجو کارشناسی ارشد کامپیوتر دانشگاه آزاد قزوین