تور نگهبان چند گانه در چند ضلعی پلکانی در حالت حداقل مجموع

در این مقاله، ما مسئله تورنگهبان چندگانه را در یک چندضلعی پلکانی بررسی کردیم. مسئله تورنگهبان یکی از مسائل مهم در حوزه هندسه محاسباتی است و یک نسخه دیگر از مسئله موزه هنری است. هدف در این مسئله، یافتن یک یا چند تور بسته برای یک یا چند نگهبان به منظور رویت تمامی‏ناحیه داخل چندضلعی است. ما مسئله را در حالت ثابت در نظر گرفتیم، به این معنی که نقاط شروع نگهبانان داخل چندضلعی پلکانی از پیش تعیین شده‌اند. دو معیار بهینه‌سازی در این مسئله حداقل مجموع، یعنی کمینه کردن مجموع طول تورها، و حداقل حداکثر، یعنی کمینه کردن ماکزیمم طول تورها، است. در این مقاله، یک الگوریتم مبتنی بر برنامه‌سازی پویا ارائه شده است که جواب بهینه مسئله را با معیار حداقل مجموع محاسبه می‌کند. الگوریتم پویا در هر دو حالت بدون دامینیت و با دامینیت دارای پیچیدگی زمانی o(n2.log⁡m) است. همچنین، این الگوریتم در هر دو حالت دارای پیچیدگی مکانی o(n) است، که در آن  تعداد نگهبان‌ها و n تعداد رئوس چندضلعی داده شده است.