مشاهده مشخصات مقاله
پوشش همبند فضای مسطح مستطیل‌بندی شده
|
Authors |
-
حلیمه خوجم‌لی
-
علیرضا زارعی
|
|
Conference |
بیست و یکمین کنفرانس ملی سالانه انجمن کامپیوتر |
|
Abstract |
مساله راهرو با طول کمینه یا به عبارتی MLC (minimum length corridor)بر روی یک مستطیل که به اتاق‌های متعامد افراز شده است، تعریف می‌شود. مساله MLC به دنبال راهرویی با طول کمینه است. راهرو در واقع یک درخت است که حداقل یک نقطه از محیط هر اتاق را شامل باشد. حالت خاص این مساله، مسالهMLC-R است که اتاق‌ها در آن مستطیلی هستند. مساله‌های MLC و MLC-R هر دو جزء دسته مسایل NP-Complete هستند و الگوریتم‌های تقریبی برای آنها ارایه شده است. ما در این مقاله بر روی یک مستطیل که به اتاق‌های مستطیلی افراز شده است، به دنبال راهرو با قطر کمینه هستیم. در یک درخت از بین فاصله‌های هر دو نقطه از درخت، فاصله‌ای که بیشترین مقدار را دارد، را قطر درخت می‌نامند. در این مقاله الگوریتمی دقیق و با زمان اجرای چندجمله‌ای برای یافتن راهرو با قطر کمینه بر روی محیط ورودی ارایه می‌کنیم. |
|
قیمت |
-
برای اعضای سایت : 100,000 Rial
-
برای دانشجویان عضو انجمن : 20,000 Rial
-
برای اعضای عادی انجمن : 40,000 Rial
|
خرید مقاله
|
|
.gif){kind=icon}