درخت اشتاینر کمینه اقلیدسی درون چند ضلعی ساده با وجود موانع
محل انتشار: همایش ملی پژوهش های کاربردی در علوم و مهندسی
سال انتشار: 1392
نوع سند: مقاله کنفرانسی
زبان: فارسی
مشاهده: 668
متن کامل این مقاله منتشر نشده است و فقط به صورت چکیده یا چکیده مبسوط در پایگاه موجود می باشد.
توضیح: معمولا کلیه مقالاتی که کمتر از ۵ صفحه باشند در پایگاه سیویلیکا اصل مقاله (فول تکست) محسوب نمی شوند و فقط کاربران عضو بدون کسر اعتبار می توانند فایل آنها را دریافت نمایند.
- صدور گواهی نمایه سازی
- من نویسنده این مقاله هستم
استخراج به نرم افزارهای پژوهشی:
شناسه ملی سند علمی:
TIAU01_364
تاریخ نمایه سازی: 14 شهریور 1393
چکیده مقاله:
مسئله درخت اشتاینر منجر به راه حل هایی در زمینه علمی و تجاری مختلف شده است که مسیر یابی شبکه های کامپیوتری و مدارهای مجتمع الکترونیکی از آن جمله هستند . زمینه های محاسباتی این مسئله ،آن راتبدیل به یک موضوع مهم تحقیقاتی در هندسه محاسباتی کرده است . با در نظر گرفتن چند نقطه در صفحه اقلیدسی که به این نقاط ترمینال گویند یک درخت پوشای مینیمم بدست می آید که این نقاط را به هم متصلمی کند به این درخت یکسری نقاط دیگر (نقاط اشتاینر ) اضافه می شود که باعث کوتاهتر شدن طول درخت می شود که به درخت حاصل ،درخت اشتاینر کمینه اقلیدسی می گویند . این مسئله به عنوان مسئلهNP_hard در نظر گرفته می شود. با در نظر گرفتن چند ضلعی ساده p با m راس وn ترمینال درآن سعی می گردد یک درخت کمینه اشتاینر اقلیدسی پیدا شود که به همهn ترمینال موجود درp متصل باشد. در این مقاله ما راه حلی برای چند ترمینال در یک چند ضلعی ساده با وجود موانع پیشنهاد کر ده ایم
کلیدواژه ها:
نویسندگان
و خسروی نژاد
دانشجو کارشناسی ارشد کامپیوتر دانشگاه آزاد قزوین
ع باقری
دکترای کامپیوتر عضو هیئت علمی دانشگاه امیرکبیر
م کیوان پور
دکترای کامپیوتر عضو هیئت علمی دانشگاه آزاد قزوین
ع خسروی نژاد
دانشجو کارشناسی ارشد کامپیوتر دانشگاه آزاد قزوین