BUSQUEDAS
Las búsquedas son uno de
los recursos más básicos e importantes dentro de las técnicas de
programación. Realmente, resulta
difícil hacer hincapié suficiente en la importancia que representan las
técnicas de búsqueda dentro del conjunto de herramientas diarias de un
programador. Pero, ¿A qué nos referimos
con búsqueda? ¿Qué es lo que se está
buscando? ¿Cuándo utilizar una búsqueda?
Una computadora puede utilizarse para una gran
cantidad de fines distintos, para escribir un documento, para ver una película,
para jugar, etc. En el ambiente de los
concursos de programación, la computadora se utiliza como una herramienta para
resolver problemas. Normalmente, por
“resolver un problema” nos referimos a encontrar un conjunto de datos S a partir de un conjunto de
datos inicial D que cumpla con
ciertas características que se estipulan en el planteamiento del problema. Y ¿Cómo encontrar el conjunto de datos S? Pues obviamente, ¡Buscando!
Por búsquedas entonces, nos referimos a las
diferentes técnicas que hay de buscar una solución para un problema, utilizando
como herramienta una computadora. Ahora
si está pareciendo algo útil, ¿Verdad?
Desgraciadamente, las técnicas de búsqueda distan
mucho de ser mágicas, y requieren de una preparación previa. Todo mundo conoce el dicho de “Es como
buscar una aguja en un pajar”, refiriéndose a algo imposible. Y seguramente que el buscar una aguja en un
montón de paja, es una tarea más difícil que las tareas del mismo
Hercules. Sin embargo, dicha aguja
podría hallarse, si se realizará una preparación previa del espacio de búsqueda. Por espacio de búsqueda nos referimos
a todos los lugares en donde pueda encontrarse una solución, para el caso de la
aguja en el montón de paja, nos referimos obviamente al montón de paja. Supón entonces que una vez que tienes el
montón de paja lo extiendes en el piso de un cuarto de madera, de modo que en
ningún lugar quede paja amontonada, después tomas un detector de metales y
comienzas a recorrer el piso del cuarto, tabla por tabla, hasta que el detector
de metales suene, si buscas en ese lugar, seguramente no tardaras mucho en
sentir un piquete en el dedo, y ¡Habrás encontrado la aguja!
Claro que para llevar a cabo dicho método de búsqueda
requieres de un cuarto suficientemente grande para distribuir la paja y de un
detector de metales. Igual para buscar
soluciones con una computadora, en muchos casos requerirás de que la
computadora cuente con memoria suficiente para almacenar el espacio de búsqueda
y necesitarás de una forma de modelar las soluciones de modo que puedan ser
representadas en la memoria de una computadora.
Lo que si tienen de mágico las técnicas de búsqueda
es que si las dominas, y aprendes a definir los espacios de búsqueda podrás
escribir programas que encuentren la solución correcta para el 90% de todos los
problemas de la olimpiada. Tu programa
algunas veces no será muy rápido, pero siempre será correcto. J
Vayamos entonces a los pasos que se requieren para
implementar una búsqueda.
El primero y más importante paso de todos es el de
definir el espacio de búsqueda, este paso, es obvio, antes de buscar,
requerimos saber en donde buscar. Pero
aún cuando parezca obvio, es el paso más difícil de todos y el que menos programadores
son capaces de tomar (Como buen programador es indispensable que puedas definir
el espacio de búsqueda para cualquier problema que se te presente, de otra
forma tendrás serios problemas para poder encontrar soluciones a problemas que
no sean triviales).
Para poder definir el espacio de búsqueda, es
necesario conocer la estructura
de la solución, es decir, ¿Qué es la solución que me piden? ¿Qué estructura tiene? ¿Cómo se puede representar?
Tomemos por ejemplo, un caso bien conocido por
todos. Dado un conjunto de N números enteros escribe un
programa que entregue como salida una permutación de dichos números {x1, x2, ... ,
xN} tal que xi ≤ xj para toda i < j. Es decir, el programa recibe como entrada N números enteros y debe
entregar como salida los mismos números pero ordenados de menor a mayor.
El problema de ordenar un conjunto de números es un
problema bien conocido, y si alguna vez lo has resuelto estoy casi seguro de
que jamás habías pensado, al resolverlo en que estabas buscando una solución en
un espacio de búsqueda. Sin embargo, la
solución a este problema, como a casi todos los problemas puede hallarse
buscando en un espacio de búsqueda definido.
¿Cuál es la estructura de la solución del problema de
ordenamiento? ¿Qué es lo que se tiene
que entregar? La solución de dicho
problema consta de los N números, por lo que cualquier forma de
escribir dichos N números es, de inicio,
una solución potencial.
Conociendo la estructura
de la solución nuestro espacio de búsqueda queda definido, lo único que tenemos
que hacer para ordenar los números es revisar todas las formas de escribir los N números y alguna de ellas cumplirá con el
criterio de ordenamiento deseado.
Una vez definido el
espacio de búsqueda, para fines de implementación es conveniente representarlo
como un árbol. De nuevo, esto no es
posible en todos los casos, pero si en la gran mayoría. ¿Cómo podemos entonces modelar nuestro
espacio de búsqueda como un árbol?
Bueno, tenemos que escribir N
números, alguno de ellos tendrá que ir primero ¿No? Podemos entonces crear un árbol en el que cada nivel agreguemos
un número, cuando lleguemos al nivel N habremos agregado todos los números y
tendremos todas las maneras posibles de escribir los N números.
Abajo se muestra el árbol anterior.
De la figura anterior puede observarse que si
revisamos todos los caminos de este árbol, uno de ellos (o más si hay números
repetidos) será la solución que buscamos.
Así es que, como podrás ver, incluso problemas tan inocuos como el de
ordenar un conjunto de números puede resolverse buscando en un espacio de
soluciones potenciales. Recorrer todo
el espacio de búsqueda de un problema puede ser muy lento, por ejemplo para la
ordenación el espacio de búsqueda es de N! Mientras que los algoritmos más comunes son de N logN, muuuuuuucho más rápidos
que N!. Sin embargo, lo importante de definir el
espacio de búsqueda es que te da una idea mucho más clara del problema. Además de que rara vez es necesario buscar
en todo el espacio, muchas veces el simple hecho de representar el árbol te
indica podas que te pueden ahorrar muchos pasos, por ejemplo, para la
ordenación, si en una rama se agregó un número mas chico al último número que
se tenía, entonces podemos estar seguros de que la solución no esta en ese
camino y podemos cortar esa rama del
árbol.
Como mencione al principio, me es difícil expresarles
lo IMPORTANTE que resulta
definir el espacio de búsqueda para un problema, la claridad que esto les da en
la solución, y sobre todo el hecho de que, únicamente pueden estar seguros de tener la
solución correcta, si buscaron en todo el espacio de búsqueda, o si demostraron
que la solución no podía estar en ninguna de las áreas en las que no buscaron.
Las técnicas de búsqueda son técnicas de programación
que permiten recorrer metódicamente un espacio de búsqueda para encontrar una
solución. Las técnicas de búsqueda más
comunes son dos búsqueda
en profundidad y búsqueda
en amplitud, ambas sirven para buscar una solución cuando el espacio de búsqueda
esta modelado como un árbol. A
continuación se describe brevemente cada uno de ellos.
·
Búsqueda
en profundidad: Esta búsqueda, como su nombre lo indica, trata de llegar
siempre lo más profundo que pueda, en cada paso, si aún no ha encontrado la
solución, trata de bajar un nivel en el árbol, si no es posible bajar más,
entonces regresa un nivel y trata de bajar por la siguiente rama que todavía no
haya recorrido. Las búsquedas en
profundidad por lo general se implementan por medio de una función recursiva.
·
Búsqueda
en amplitud: Esta búsqueda, recorre el árbol nivel por nivel, es
decir, en el primer paso busca la solución entre todos los nodos del primer
nivel del árbol, si no encuentra la solución, entonces baja un nivel y la busca
entre todos los nodos del segundo nivel, y de esa manera recorre cada uno de
los niveles hasta encontrar la solución.
Las búsquedas en amplitud por lo general se implementan con una
cola. Las búsquedas en amplitud son
especialmente útiles cuando lo que se desea es la solución que este más cercana
a la raíz del árbol, ya que al ir recorriendo nivel por nivel, la primera
solución que se encuentra es aquella que esta más cercana a la raíz.
En la siguiente sección se describirá de manera
detallada la forma de utilizar las búsquedas para resolver 4 problemas.