رحمت قاسمی - دانشکده مهندسی کامپیوتر و مکاترونیک، واحد علوم و تحقیقات، دانشگاه آزاد اسلامی، تهران، ایران
علیرضا باقری - دانشیار دانشکده مهندسی کامپیوتر، دانشگاه صنعتی امیرکبیر(پلی تکنیک)، تهران، ایران
فاطمه کشاورز کوهجردی - دانشکده علوم پایه، گروه علوم کامپیوتر، دانشگاه شاهد، تهران، ایران

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

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