انجمن کامپیوتر ایران

مساله راهرو با طول کمینه یا به عبارتی MLC (minimum length corridor)بر روی یک مستطیل که به اتاق‌های متعامد افراز شده است، تعریف می‌شود. مساله MLC به دنبال راهرویی با طول کمینه است. راهرو در واقع یک درخت است که حداقل یک نقطه از محیط هر اتاق را شامل باشد. حالت خاص این مساله، مساله‌MLC-R است که اتاق‌ها در آن مستطیلی هستند. مساله‌های MLC و MLC-R هر دو جزء دسته مسایل NP-Complete هستند و الگوریتم‌های تقریبی برای آنها ارایه شده است. ما در این مقاله بر روی یک مستطیل که به اتاق‌های مستطیلی افراز شده است، به دنبال راهرو با قطر کمینه هستیم. در یک درخت از بین فاصله‌های هر دو نقطه از درخت، فاصله‌ای که بیشترین مقدار را دارد، را قطر درخت می‌نامند. در این مقاله الگوریتمی دقیق و با زمان اجرای چندجمله‌ای برای یافتن راهرو با قطر کمینه بر روی محیط ورودی ارایه می‌کنیم.