La búsqueda de fugitivos

Imaginemos por un momento, que tenemos un prófugo de la ley y debemos realizar una búsqueda para atraparlo, este proceso puede generar perdidas de tiempo, dinero y esfuerzo  si no se optimiza el proceso de dicha búsqueda, y peor aún, si no se captura el fugitivo.

En este caso podemos echar mano del  problema del Set Covering “se puede entender como el problema de encontrar el mínimo de subconjuntos que contengan todos los elementos de un conjunto dado, con el fin de minimizar algún valor.”

Un ejemplo de como puede funcionar es el siguiente: A fin de evitar naufragios, tenemos que iluminar una costa rocosa, con casas habitación ya que el faro no funciona. Por supuesto, es caro que todas las casas se estén usando para evitar un desastre de esta magnitud, lo que nos gustaría es cubrir  toda la costa con el menor número de casas.

Una manera de resolver este problema es siguiendo un algoritmo voraz . Es decir, podríamos poner la casa  que ilumine en  la sección más grande de la costa, nuestro segundo faro va a ir a donde se puede iluminar el mayor tramo de costa que no esté iluminado por el faro en primer lugar. Seguimos de esta manera, la colocación de cada faro para que ilumine la mayor cantidad de línea de costa, no iluminada por los faros anteriores, hasta que todo el litoral se ilumina. La teoría detrás de esto es que si podemos maximizar el radio de cobertura.

Por ultimo, pensemos en la captura del fugitivo de la siguiente forma

Una ciudad está revisando la ubicación de sus estaciones de policía o cuerpos de seguridad publica . La ciudad se compone de un número de barrios o colonias, como se ilustra en la figura.

Al tener este tipo de mapa,  podemos establecer una estación de policía en cada una de las 11 barrios, si agregamos el hecho de que cada estación cuida su colonia y las colonias adyacentes , podemos encontrar el número optimo de estaciones policíacas, y con esto reforzar la calidad en el servicio, ahora bien si nuestro fugitivo se encuentra en este mapa, la búsqueda se optimiza llegando a resultados aceptables de una forma eficiente al resolver el siguiente sistema

La primera restricción indica que debe haber una estación ya sea en la vecindad de 1 o en alguna zona adyacente. La restricción siguiente es para zona 2 y así sucesivamente. Observe que el coeficiente de restricción tex2html_wrap_inline1571 es 1 si el barrio  i es adyacente al barrio j o bien   si i = j, y 0 en caso contrario. La columna j-ésima de la matriz de restricciones representa el conjunto de barrios que pueden ser atendidas por una estación de policías en el barrio de j. Se nos pide que encontrar el mínimo de subconjuntos de tal manera que cubra a toda la ciudad  en el sentido de que cada barrio aparece en el subgrupo de servicios asociados a la estación de policía al menos uno.

Una solución óptima para este es tex2html_wrap_inline1585 y el resto igual a 0.

Este tipo de argumentos puede minimizar  el gasto en los recursos y poder generar búsquedas de forma inteligente.

Anuncios

2 comentarios en “La búsqueda de fugitivos

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s