Watchman route problem
ওয়াচম্যান প্রবলেম গণনামূলক জ্যামিতিতে একটি অপ্টিমাইজেশান সমস্যা যেখানে উদ্দেশ্য হল শুধুমাত্র এলাকার একটি মানচিত্র দেওয়া বাধা সহ একটি পুরো এলাকা রক্ষার জন্য একজন প্রহরীকে যে সংক্ষিপ্ততম পথটি গ্রহণ করা উচিত তা গণনা করা। চ্যালেঞ্জটি হল প্রহরী প্রতিটি কোণের পিছনে উঁকি দেয় তা নিশ্চিত করা এবং কোন কোণে যাওয়া উচিত তার সর্বোত্তম ক্রম নির্ধারণ করা। সমস্যাটি বহুপদী সময়ে সমাধান করা যেতে পারে যখন সুরক্ষিত এলাকাটি একটি সাধারণ বহুভুজ। গর্তযুক্ত বহুভুজগুলির জন্য সমস্যাটি এন. পি-হার্ড, তবে বহুপদী সময়ে এমন একটি সমাধান দ্বারা আনুমানিক হতে পারে যার দৈর্ঘ্য সর্বোত্তম পলিলোগারিদমিক ফ্যাক্টরের মধ্যে থাকে। আরও দেখুন আর্ট গ্যালারি সমস্যা, যা একইভাবে একটি নির্দিষ্ট এলাকার সমস্ত পয়েন্ট দেখার সাথে জড়িত, তবে একাধিক স্থির প্রহরী রেফারেন্স জ্যামিতিক অ্যালগরিদম সহ।