Problem z trasą Watchmana

Problem stróża to problem optymalizacyjny w geometrii obliczeniowej , w którym celem jest obliczenie najkrótszej trasy, jaką strażnik powinien pokonać, aby strzec całego obszaru z przeszkodami, biorąc pod uwagę tylko mapę tego obszaru. Wyzwanie polega na upewnieniu się, że stróż zajrzy za każdy róg i określeniu najlepszej kolejności odwiedzania zakamarków. Problem można rozwiązać w czasie wielomianowym , gdy obszar, który ma być strzeżony, jest prostym wielokątem . Problem jest NP-trudny dla wielokątów z otworami, ale można je przybliżyć w czasie wielomianowym za pomocą rozwiązania, którego długość mieści się w zakresie współczynnika polilogarytmicznego optymalnego.

Zobacz też

• Problem galerii sztuki , który podobnie polega na oglądaniu wszystkich punktów danego obszaru, ale z wieloma stacjonarnymi strażnikami