Watchman route problem
ಕಾವಲುಗಾರನ ಸಮಸ್ಯೆಯು ಕಂಪ್ಯೂಟೇಶನಲ್ ಜ್ಯಾಮಿತಿಯಲ್ಲಿನ ಒಂದು ಆಪ್ಟಿಮೈಸೇಶನ್ ಸಮಸ್ಯೆಯಾಗಿದ್ದು, ಅಲ್ಲಿ ಪ್ರದೇಶದ ನಕ್ಷೆಯನ್ನು ಮಾತ್ರ ನೀಡಲಾದ ಅಡೆತಡೆಗಳೊಂದಿಗೆ ಇಡೀ ಪ್ರದೇಶವನ್ನು ರಕ್ಷಿಸಲು ಕಾವಲುಗಾರನು ತೆಗೆದುಕೊಳ್ಳಬೇಕಾದ ಕಡಿಮೆ ಮಾರ್ಗವನ್ನು ಲೆಕ್ಕ ಹಾಕುವುದು ಇದರ ಉದ್ದೇಶವಾಗಿದೆ. ಕಾವಲುಗಾರನು ಪ್ರತಿ ಮೂಲೆಯ ಹಿಂದೆ ಇಣುಕಿ ನೋಡುವುದನ್ನು ಖಚಿತಪಡಿಸಿಕೊಳ್ಳುವುದು ಮತ್ತು ಯಾವ ಮೂಲೆಗಳಲ್ಲಿ ಭೇಟಿ ನೀಡಬೇಕು ಎಂಬುದರ ಅತ್ಯುತ್ತಮ ಕ್ರಮವನ್ನು ನಿರ್ಧರಿಸುವುದು ಸವಾಲಾಗಿದೆ. ಕಾವಲು ಮಾಡಬೇಕಾದ ಪ್ರದೇಶವು ಸರಳವಾದ ಬಹುಭುಜಾಕೃತಿಯಾಗಿರುವಾಗ ಈ ಸಮಸ್ಯೆಯನ್ನು ಬಹುಪದೀಯ ಸಮಯದಲ್ಲಿ ಪರಿಹರಿಸಬಹುದು. ರಂಧ್ರಗಳನ್ನು ಹೊಂದಿರುವ ಬಹುಭುಜಾಕೃತಿಗಳಿಗೆ ಈ ಸಮಸ್ಯೆಯು ಎನ್. ಪಿ.-ಕಠಿಣವಾಗಿದೆ, ಆದರೆ ಬಹುಪದೀಯ ಸಮಯದಲ್ಲಿ ಅದರ ಉದ್ದವು ಸೂಕ್ತವಾದ ಬಹುಪದೀಯ ಅಂಶದೊಳಗೆ ಇರುವ ಪರಿಹಾರದಿಂದ ಅಂದಾಜು ಮಾಡಬಹುದು. ಆರ್ಟ್ ಗ್ಯಾಲರಿ ಸಮಸ್ಯೆಯನ್ನು ಸಹ ನೋಡಿ, ಇದು ನಿರ್ದಿಷ್ಟ ಪ್ರದೇಶದ ಎಲ್ಲಾ ಬಿಂದುಗಳನ್ನು ವೀಕ್ಷಿಸುವುದನ್ನು ಒಳಗೊಂಡಿರುತ್ತದೆ, ಆದರೆ ಅನೇಕ ಸ್ಥಾಯಿ ಕಾವಲುಗಾರರೊಂದಿಗೆ ಜ್ಯಾಮಿತೀಯ ಕ್ರಮಾವಳಿಗಳನ್ನು ಉಲ್ಲೇಖಿಸುತ್ತದೆ.