En
programación es muy común usar
Estructuras de Datos
para poder ordenar y almacenar información. Ésta puede ser desde
primitivas como números enteros hasta cadenas de texto hasta tipos
definidos por el programador como productos, personas o estados de un
juego.
Existen diversas
Estructuras de Datos entre las cuales están
los arrays, las listas, las colas, las pilas, los conjuntos, los
árboles, los grafos… En esta entrada vamos a centrarnos en los árboles y
en los dos algoritmos de búsqueda más sencillos que podemos usar en
ellos: la búsqueda en anchura y la búsqueda en profundidad.
Comencemos entonces.
Un
árbol es una
estructura de datos compuesta por
nodos y
ramas. Un nodo es un
elemento, el dato que queremos organizar. Una rama es una unión
dirigida entre un par de nodos. Un nodo se dice que es
padre si existe alguna rama que le una con otro nodo, del mismo modo que un nodo es
hijo si existe una rama que una a otro nodo con éste. Decimos que un nodo es
hoja si no tiene hijos. Un
grafo es una generalización de un árbol. Para entenderlo mejor, consultemos la siguiente figura:
Como toda estructura de datos, los árboles tienen tres operaciones básicas:
- Inserción de nuevos elementos.
- Eliminación de elementos existentes.
- Búsqueda de un elemento en la estructura.
Existen otras operaciones como la ordenación y la mezcla de dos
estructuras de datos del mismo tipo, pero no vamos a tratarlas aquí.
Durante el resto de la entrada vamos a utilizar el siguiente árbol:
Comenzamos por tanto, construyendo los tipos de datos necesarios para
representar este árbol. En esta ocasion voy a elegir Java como lenguaje
de programación por disponer de tipos de datos predefinidos que nos van
a ayudar, ya que por ejemplo en C tendríamos que crearnos diversos
tipos de datos (los cuales veremos más adelante) que pertenecería a una
entrada sobre estructuras de datos y su construcción, y no de algoritmos
de búsqueda.
Lo primero será crear nuestra clase
NodoArbol, la cual va a representar un nodo de nuestro árbol (
duh).
En nuestro caso vamos a usar como elemento de cada nodo un carácter,
para hacerlo simple. Sin embargo podríamos también usar otras primitivas
o nuestros propias clases. Y además vamos a aceptar que cada nodo pueda
tener
entre 0 y N hijos, de modo que querremos algún tipo de
lista dinámica para almacenarlo (ya que no sabemos inicialmente cuántos
hijos habrá por nodo). El código de la clase comienza siendo el
siguiente:
1 | public class NodoArbol { |
4 | private List<NodoArbol> hijos; |
6 | public NodoArbol(char elemento) { |
7 | this.elemento = elemento; |
8 | hijos = new ArrayList<NodoArbol>(); |
11 | public char getElemento() { |
15 | public void addHijo(NodoArbol hijo) { |
19 | public List<NodoArbol> getHijos() { |
23 | public boolean esNodoHoja() { |
24 | return hijos.size() > 0; |
Además de los atributos que hemos mencionado, añadimos funcionalidad
para obtener el elemento del nodo actual y los hijos de dicho nodo,
además de la opción de insertar hijos al nodo y de consultar si es un
nodo hoja.
Ahora crearemos nuestra clase principal, desde la que vamos a ejecutar las pruebas:
1 | public class ArbolesBusquedas { |
3 | public static void main(String[] args) { |
5 | NodoArbol raiz = new NodoArbol('v'); |
8 | NodoArbol nivel1hijo0 = new NodoArbol('i'); |
9 | NodoArbol nivel1hijo1 = new NodoArbol('o'); |
10 | NodoArbol nivel1hijo2 = new NodoArbol('r'); |
13 | NodoArbol nivel2hijo0 = new NodoArbol('d'); |
14 | NodoArbol nivel2hijo1 = new NodoArbol('c'); |
15 | NodoArbol nivel2hijo2 = new NodoArbol('n'); |
16 | NodoArbol nivel2hijo3 = new NodoArbol('r'); |
17 | NodoArbol nivel2hijo4 = new NodoArbol('e'); |
18 | NodoArbol nivel2hijo5 = new NodoArbol('e'); |
21 | NodoArbol nivel3hijo0 = new NodoArbol('a'); |
22 | NodoArbol nivel3hijo1 = new NodoArbol('s'); |
23 | NodoArbol nivel3hijo2 = new NodoArbol('c'); |
24 | NodoArbol nivel3hijo3 = new NodoArbol('u'); |
25 | NodoArbol nivel3hijo4 = new NodoArbol('n'); |
26 | NodoArbol nivel3hijo5 = new NodoArbol('t'); |
27 | NodoArbol nivel3hijo6 = new NodoArbol('s'); |
30 | raiz.addHijo(nivel1hijo0); |
31 | raiz.addHijo(nivel1hijo1); |
32 | raiz.addHijo(nivel1hijo2); |
35 | nivel1hijo0.addHijo(nivel2hijo0); |
36 | nivel1hijo0.addHijo(nivel2hijo1); |
37 | nivel1hijo1.addHijo(nivel2hijo2); |
38 | nivel1hijo2.addHijo(nivel2hijo3); |
39 | nivel1hijo2.addHijo(nivel2hijo4); |
40 | nivel1hijo2.addHijo(nivel2hijo5); |
43 | nivel2hijo0.addHijo(nivel3hijo0); |
44 | nivel2hijo0.addHijo(nivel3hijo1); |
45 | nivel2hijo2.addHijo(nivel3hijo2); |
46 | nivel2hijo2.addHijo(nivel3hijo3); |
47 | nivel2hijo4.addHijo(nivel3hijo4); |
48 | nivel2hijo4.addHijo(nivel3hijo5); |
49 | nivel2hijo5.addHijo(nivel3hijo6); |
El código de arriba crea el árbol que hemos visto en la figura
superior. Todos estamos de acuerdo en que quizá no es la forma elegante
de crear el árbol y probablemente existen formas más cortas y eficientes
de hacerlo. Sin embargo prefiero mantener la claridad en la explicación
para que no se me pierda nadie.
Lo siguiente que vamos a hacer es crear las búsquedas en anchura y
profundidad. Pero antes de crearlas tendremos que saber qué hace cada
una, ¿no?
Búsqueda en anchura
La busqueda en anchura (o búsqueda en amplitud), llamada
Breadth First Search
en inglés, es un algoritmo usado para recorrer o buscar elementos en
una estructura de datos como los árboles y los grafos (aunque nosotros
nos centremos ahora mismo en los árboles). Pertenece al grupo de las
búsquedas no informadas (sin
heurísticas).
Su procedimiento consiste en ir visitando todos los nodos de un nivel
antes de proceder con el siguiente nivel tal y como mostramos en la
siguiente figura (los números en
naranja indican el orden de exploración de los nodos):
De modo que lo primero que hará será visitar la raíz, luego los hijos
de la raíz, luego los hijos de cada uno de estos hijos y así
sucesivamente. ¿Cómo hacemos esto para que funcione, pensaréis? La
respuesta es sencilla: usar una
cola como estructura de datos auxiliar.
Una
cola es una estructura
FIFO (
First In, First Out) en la que sólo disponemos de dos operaciones: insertar al final de la
cola y extraer del principio de la
cola.
Por tanto, el elemento que entra el último será el último en salir.
Como hemos elegido Java como lenguaje de programación para esta entrada,
disponemos ya de la interfaz
Queue<E> y la clase
LinkedList<E> que nos van a brindar la funcionalidad de las colas sin programar nada.
Nuestro procedimiento va a ser el siguiente:
- Insertamos la raíz en la cola, como preparación.
- Si la cola no está vacía, sacamos el primer elemento (el primer nodo que haya en la cola)
y comprobamos si es el elemento que estamos buscando. Si es igual
entonces acabamos, si no es igual obtenemos todos los hijos de dicho
nodo y los insertamos en la cola (recordamos que las inserciones son por
el final).
- Repetimos hasta que hayamos encontrado el elemento o la cola sea vacía.
- Finalizamos.
Como la búsqueda se realiza desde un
NodoArbol (la raíz),
cabe pensar que la función de búsqueda debe ser parte de esta clase. Por
tanto, agreamos la siguiente función a la clase
NodoArbol:
1 | public boolean busquedaAnchura(char c) { |
2 | Queue<NodoArbol> colaAuxiliar = new LinkedList<NodoArbol>(); |
3 | colaAuxiliar.add(this); |
5 | while(colaAuxiliar.size() != 0) { |
6 | NodoArbol cabeza = colaAuxiliar.poll(); |
7 | System.out.println(cabeza.getElemento()); |
8 | if(cabeza.getElemento() == c) |
11 | for(NodoArbol hijo : cabeza.getHijos()) |
12 | colaAuxiliar.add(hijo); |
Como hemos dicho previamente, lo primero es insertar la raíz en la
cola para que tengamos algo por donde empezar. A partir de entonces, si
existe algo en la cola cogemos la cabecera (la función
poll()
devuelve la cabeza y la elimina de la cola). Ahora comprobamos si el
elemento interno de este nodo es el que estamos buscando (recordemos que
se debe usar la función .equals() para comparar objetos
no primitivos).
Si el elemento es el que buscamos entonces retornamos de la función
positivamente, si no lo es entonces cogemos todos los hijos de dicho
nodo y los insertamos en la cola para hacer una iteración más.
Llega el momento de probar que lo que hemos hecho funciona como
esperamos. Los siguientes códigos se deben insertar al final del
main de la clase ArbolesBusquedas y lo que obtendríamos al ejecutar está marcado como
output. Comenzamos probando que encontramos la raíz:
1 | System.out.println(raiz.busquedaAnchura('v')); |
Comprobamos que encontramos la letra ‘u’:
1 | System.out.println(raiz.busquedaAnchura('u')); |
Comprobamos que no encontramos la letra ‘z’:
1 | System.out.println(raiz.busquedaAnchura('z')); |
¿Qué pasa si buscamos la letra ‘c’? Existen varias letras ‘c’, ¿cuál encontrará? Probemos:
1 | System.out.println(raiz.busquedaAnchura('c')); |
Entonces, la búsqueda en anchura va a encontrar el elemento de
menor profundidad del árbol, si es que existe.
Ventajas de la búsqueda en anchura:
- Es completo: siempre encuentra la solución si existe.
- Es óptimo si el coste de cada rama es constante: en Inteligencia
Artificial puede que cada nodo sea un estado de un problema, y que unas
ramas tengan un coste diferente a las demás.
Inconvenientes de la búsqueda en anchura:
- Complejidad exponencial en espacio y tiempo (incluso peor la del espacio que la del tiempo).
Búsqueda en profundidad
La busqueda en profundidad, llamada
Depth First Search en
inglés, es un algoritmo usado para recorrer o buscar elementos en un
árbol o un grafo y pertenece al grupo de las búsquedas no informadas
(sin
heurísticas).
Su procedimiento consiste en visitar todos los nodos de forma ordenada
pero no uniforme en un camino concreto, dejando caminos sin visitar en
su proceso. Una vez llega al final del camino vuelve atrás hasta que
encuentra una bifurcación que no ha explorado, y repite el proceso hasta
acabar el árbol (esto se conoce como
backtracking). En la siguiente figura mostramos el orden de visita, siendo los números en
naranja dicho orden:
Para poder programar dicho comportamiento vamos a apoyarnos en una estructura de datos llamada
pila. Una
pila es una estructura de datos
LIFO (
Last In, First Out) en la que sólo disponemos de dos operaciones: apilar y desapilar. Apilar añade el elemento en
la cabeza
y desapilar lo extrae y elimina. Por tanto, el primer elemento que
entre se quedará en el fondo y será el último en visitarse. Igual que
con las colas, Java nos brinda la clase
Stack<T> que nos va a servir el comportamiento deseado.
Nuestro procedimiento, por tanto, será:
- Insertamos la raíz en la pila, para preparación.
- Mientras haya algo en la pila, desapilamos la cabeza. Comprobamos si
es el elemento que buscamos y si lo es acabamos. Si no lo es, cogemos
todos los hijos de dicho nodo y los apilamos todos.
- Repetimos hasta que encontremos el elemento buscado o la pila esté vacía.
- Finalizamos.
Por tanto, añadimos la siguiente función a la clase
NodoArbol:
1 | public boolean busquedaProfundidad(char c) { |
2 | Stack<NodoArbol> pilaAuxiliar = new Stack<NodoArbol>(); |
3 | pilaAuxiliar.push(this); |
5 | while(pilaAuxiliar.size() != 0) { |
6 | NodoArbol cabeza = pilaAuxiliar.pop(); |
7 | System.out.println(cabeza.getElemento()); |
8 | if(cabeza.getElemento() == c) |
11 | for(int i = cabeza.getHijos().size() - 1; i >= 0; i--) |
12 | pilaAuxiliar.push(cabeza.getHijos().get(i)); |
Pregunta: ¿por qué no hemos hecho el bucle
for igual que en
la búsqueda en anchura? Recordemos que una pila es una estructura en la
que lo último que entra es lo primero que sale. Nosotros queremos ir
explorando el árbol por
el camino de más a la izquieda, tal y
como mostrábamos en la figura superior. Si usáramos el mismo bucle for
que en la búsqueda en anchura, estaríamos haciendo la búsqueda
por la derecha, puesto que el elemento de la cabeza de la pila siempre sería
el hijo de más a la derecha del nodo consultado.
Comprobemos entonces que funciona. Igual que antes, pondremos los siguientes códigos al final de la creación del árbol en el
main y al ejecutar veremos lo que está marcado como
output:
Comprobamos que encuentra la raíz:
1 | System.out.println(raiz.busquedaProfundidad('v')); |
Comprobamos que encuentra la letra ‘u’:
1 | System.out.println(raiz.busquedaProfundidad('u')); |
Comprobamos que no encuentra la letra ‘z’:
1 | System.out.println(raiz.busquedaProfundidad('z')); |
¿Qué pasa si buscamos la letra ‘c’?
1 | System.out.println(raiz.busquedaProfundidad('c')); |
Como vemos, la búsqueda en profundidad busca el elemento por el
camino de máxima profundidad y cuando éste se acaba, vuelve al último
nodo que había visitado con caminos posibles (
caminos abiertos).
Ventajas de la búsqueda en profundidad:
- Es completa si no existen ciclos repetidos.
- Tiene menor complejidad en espacio que la búsqueda en anchura, porque solo mantenemos en memoria un camino simultáneamente.
Inconvenientes de la búsqueda en profundidad:
- No es óptima.
- Puede no encontrar la solución aunque exista si hay caminos infinitos. Luego no es completa.
Quizá el ejemplo anterior no sea demasiado ilustrativo para el caso
de la letra ‘c’. Veamos el siguiente árbol, que está simplificado pero
nos ayudará a entenderlo mejor:
Ahora veamos qué pasa si buscamos con ambos algoritmos el elemento cuyo carácter es una ‘c’.
Comenzamos con la búsqueda en anchura:
Ahora la búsqueda en profundidad:
¿Qué vemos aquí? La búsqueda en anchura ha visitado sólo 3 nodos
hasta encontrar la solución mientras que la búsqueda en profundidad ha
visitado 11 nodos para encontrar la suya. ¿Significa esto que la
búsqueda en anchura es mejor que la búsqueda en profundidad? Miremos un
último ejemplo:
Buscamos el elemento cuyo carácter es ‘c’ y los dos recorridos serán
los que se ven en la siguiente figura (click para agrandar):
¿Y ahora? ¿Cuál es mejor? Parece que la búsqueda en profundidad.
Concluiremos con que en realidad
no hay una búsqueda no informada mejor o peor, porque dependen mucho de la posición de nuestra
solución dentro del árbol (entendemos
solución por
lo que estamos buscando).
¿Cómo solucionamos esto, entonces? La respuesta es usar búsquedas
informadas (usando heurísticas). Sin embargo es un campo muy amplio y en
esta entrada no vamos a tratarlo.
Por tanto, podemos generalizar el algoritmo que usaremos en dichas búsquedas como lo siguiente:
3 | SI esVacia(listaAbierta) ENTONCES |
6 | nodo <- primero(listaAbierta) |
7 | SI esNodoMeta(nodo) ENTONCES |
10 | listaSucesores <- expandir(nodo) |
11 | PARA CADA n : sucesores HACER |
12 | insertar(n, listaAbierta, ordenInsercion) |
Donde la lista abierta podemos generalizarla como una lista enlazada
simple y el orden de inserción es al inicio, al final u otro lugar
dependiendo de la búsqueda que estemos haciendo. De esta forma
tendríamos una forma general de realizarlas. Si esto fuera Ingeligencia
Artificial y no una simple búsqueda de un elemento, cabria añadir una
instrucción más por cada sucesor y además devolver el nodo una vez
encontrado, y no un valor booleano.
Algunos usos de las búsquedas
Antes de acabar voy a hablar muy brevemente sobre las aplicaciones de estas búsquedas.
La aplicación básica es la de encontrar un elemento en concreto dentro de nuestra estructura de datos, como hemos visto.
Por su parte, la
Inteligencia Artificial trata de, dado un problema, hayar su solución. Supongamos un laberinto. Nuestro
agente inteligente
debe encontrar la salida. Si esta búsqueda de la salida la realiza con
búsquedas no informadas (sin heurísticas) puede acabar en ciclos
infinitos (en caso de la búsqueda en profundidad) o tardar muchísimo
tiempo (en la búsqueda en anchura siempre encontramos la solución más
corta si existe, pero esto puede ser en
la parte inferior derecha del árbol,
que es lo último en visitar). También existen modificaciones de dichos
algoritmos como la búsqueda en profundidad limitada (para evitar ciclos
infinitos).
Para solventar estos problemas surgieron las búsquedas informadas que
usan heurísticas. Éstas, antes de explorar un nuevo nodo evaluan cuál
de los hijos le ofrece
mayor recompensa. Esta forma de decidir qué nodo
es mejor depende de la heurística usada, que pueden ser muy variadas e incluso ineficientes.
Por ejemplo la heurística
lo que más me acerque a la meta
puede parecer una gran idea. Pero puede traer un inconveniente: ¿y si
hay una pared desde donde estoy hasta la meta? Sí, me queda una casilla
para llegar, ¡pero no puedo atravesar el muro!
Esto es solamente un ejemplo y haría falta mucha explicación para
cubrir los casos y sobre todo hacer una comparativa en complejidad
espacial y temporal de cada una de las búsquedas. Sin embargo como idea
inicial de posibles usos de las búsquedas vistas durante la entrada es
suficiente.
¡Espero que haya sido de utilidad para los lectores!
Por cierto, creo que tienes un error en la numeración del ejemplo de búsqueda en profundidad (letras n, r, t)
Saludos!
¡Muchas gracias!
Queue colaAuxiliar = new LinkedList();
Lo que pasa es que lo estoy migrando a c# y no me permite crear la Queue con el constructor de la lista enlazada.
y también esta porfavor, l
for(NodoArbol hijo : cabeza.getHijos())
Es para revisarlo y entenderlo mejor. GRACIAS.
Espero me puedas ayudar. Gracias.
salu2