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