El llibre de Clara Grima
Hasta el infinito y más allá conté un capítol titulat
¿Por qué no hay un poli en cada sala? on es presenta el problema del que parlarem ara. També va ser motiu d'una entrada a un dels seus blogs:
Cuántos nos están vigilando. No millorarem el que ella ha escrit, però si que intentarem plantejar-ho com una possible seqüència didàctica per treballar el problema a l'aula. Som-hi doncs!
Imaginem que tenim una sala, per exemple d'un museu, on hem de situar una persona vigilant, tenint en compte que pot girar sobre sí mateix però no desplaçar-se. Si volem podem imaginar-nos un vigilant-mussol capaç de girar el seu cap 360º (imaginar-se la
nena de l'exorcista girant el cap és més desagradable) o una càmera que gira sobre un eix.
Si tenim una sala en forma de quadrilàter, com el de l'exemple sota, és indiferent on col·loquem el vigilant. Sempre tindrà tota la sala en el seu camp d'observació, fins i tot posant-se a una cantonada.
Una sala una mica més complexa pot ser més exigent a l'hora de triar el lloc del vigilant, ja que no des de qualsevol lloc la visió és completa.
Algunes sales necessitaran, de totes totes, més d'un vigilant, encara que hi hagi zones sobrevigilades.
El problema tracta justament d'això: donada una sala poligonal qualsevol mirar quina és la quantitat de vigilants mínima que calen, on s'han de posar... i fins i tot treballarem un algoritme que ens ajuda a resoldre totes dues qüestions.
Vols estudiar el problema?