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

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

کلیدواژه ها:

موزه هنر ، تورنگهبان چندگانه ، چندضلعی متعامد ، برنامه سازی پویا ، چندضلعی پلکانی