1

Métodos de Búsqueda: Búsquedas a Ciegas,

Búsquedas Heurísticas
Jonathan M. Blandín.

 B. Objetivos Específicos
Resumen—El siguiente documento presenta un análisis sobre  Implementar en Java los algoritmos para realizar
los dos tipos de técnicas para resolver problemas de búsquedas búsquedas a ciegas y búsquedas heurísticas.
utilizados en la Inteligencia Artificial. La primera, realiza una
 Analizar las distintas búsquedas realizadas y comprobar
búsqueda exhaustiva (Ciega) para llegar al destino y la segunda
se basa en conocimiento o experiencia (Heurística) para lograr la su eficiencia.
meta. Dentro de estos tipos, se encuentran varios algoritmos que
ayudan a cumplir con los objetivos basándose en metodologías
distintas. III. METODOLOGÍA
Palabras Clave—Búsqueda, Ciega, Conocimiento, Exhaustiva, A. Materiales
Experiencia, Inteligencia Artificial, Heurística.  Entorno de desarrollo Integrado NetBeans.
 Software Java.
I. INTRODUCCIÓN
B. Métodos
L A búsqueda es una parte natural de la vida de la
mayoría de las personas, la cual es una técnica para
resolver problemas cuya solución consiste en una serie de
Se inició con la implementación de los algoritmos de
búsquedas a ciegas y búsquedas heurísticas como se especifica
pasos que frecuentemente deben determinarse mediante la en los siguientes puntos y en las referencias [3] y [4].
prueba sistemática de las alternativas. Desde los inicios de la Luego, se preparó un algoritmo extra con el objetivo de
Inteligencia Artificial (IA), la búsqueda se ha aplicado en generar nodos aleatoriamente, creando árboles y grafos para
diversas clases de problemas como juegos de dos jugadores, poder probar el funcionamiento de los algoritmos de
problemas de satisfacción de restricciones y problemas de búsquedas.
pathfinding de un único agente. Luego fueron tomando más Finalmente, se comenzó a analizar la eficiencia de cada
forma, siendo parte de investigaciones, descubrimientos y algoritmo, tanto de las búsquedas a ciegas como de las
experimentos académicos en cuánto a robótica dando cierta búsquedas heurísticas tratando los siguientes puntos:
independencia a las máquinas para tomar decisiones. [1]
Aunque los métodos de búsqueda se reduzcan en muchos  Tiempo de ejecución de cada algoritmo para resolver
casos a meros algoritmos matemáticos, lo que se persigue un mismo grafo.
desde el punto de vista de la Inteligencia Artificial (IA) es  Llega o no a la meta.
entender el problema que se trata de resolver, analizar sus  Extensión o largo del código. (Líneas de código).
posibles soluciones y las consecuencias de buscar una  Número de iteraciones.
solución por un camino u otro. [2]
Se debe tomar en cuenta que para que el algoritmo sea
eficiente, las características anteriores se generalizarán de la
siguiente manera:
II. OBJETIVOS
A. Objetivo General  El tiempo de ejecución debe ser mínimo.
 Implementar y analizar los diferentes algoritmos de  Debe partir de un nodo raíz y llegar siempre a la
búsquedas. meta.
 Debe contener un número de líneas de programación
muy reducidas.
 Debe contener un número mínimos de iteraciones.
Documento recibido el 24 de Mayo de 2017. Este proyecto se realizó en la
Universidad de Cuenca, en la Escuela de Electrónica y Telecomunicaciones,
El número de líneas de código es un poco ambiguo ya que
para la materia de Redes Neuronales Artificiales puede dar un sentido de eficiencia o de complejidad al
J. M. Blandín estudia en la en la Universidad de Cuenca, en la Escuela de software.
Electrónica y Telecomunicaciones, Av. 12 de Abril y Agustín Cueva, Cuenca-
Ecuador (teléfono: 593-7 409 2219; e-mail: [email protected]).
 2

IV. GLOSARIO DE TÉRMINOS D. Búsqueda en Profundidad Iterativa

Para tratar este documento y muchos aspectos en cuanto a Es derivada de la búsqueda en profundidad, que consiste en
búsquedas, existen términos que se deben conocer, siendo realizar dicha búsqueda solo hasta cierto nivel; para lo cual en
estos los siguientes: cada iteración inicia en el nivel cero y termina en un nivel
mayor al que recorrió en la última iteración. Este proceso
 Conjunto de Estados: Todas las configuraciones termina cuando llegó a la meta o consumió todos sus recursos.
posibles en el dominio.
 Estados Iniciales: Estado del cual partimos en el E. Búsqueda de Costo Uniforme
problema.
Su utilización minimiza el coste del camino del origen a la
 Estados Finales: La solución u objetivo del
meta. Siempre expande el nodo que cuente con menor coste
problema.
desde su nodo padre.
 Operadores: Función de transformación de un estado
a otro.
 Expandir un Nodo: Obtener los hijos de un nodo al
VI. BÚSQUEDAS HEURÍSTICAS
aplicar un operador.
 Nodos Abiertos: Estados generados no visitados. Las técnicas de búsquedas heurísticas usan el conocimiento
 Nodos Cerrados: Estados visitados y expandidos. del dominio, para de esta manera el proceso sea más potente y
 Nodo Hijo: Nodo que ha sido generado a partir de su consiga llegar a la solución con mayor rapidez y eficiencia.
padre. Este conocimiento se lo llama función de evaluación.
 Nodo Padre: Nodo de partida de los nodos
generados. A. Búsqueda por Método del gradiente
 Nodo Visitado: Nodo que ya ha sido expandido. Se asemeja a escalar una montaña; se busca llegar a la cima
 Árbol: Estructura unidireccional de nodos. ascendiendo cada vez pero no pudiendo retroceder en el
 Grafo: Estructura bidireccional de vértices. camino. Comienza con un punto que es llamado actual, se
 Coste de camino: Distancia o costo entre dos puntos. evalúa un nuevo estado mejor para transformarse en punto
 Función de evaluación: Conocimiento sobre el grafo. actual. El proceso termina cuando ya no hay mejoras pudiendo
encontrar o no la meta.[5]

V. BÚSQUEDAS A CIEGAS
B. Búsqueda Primero el Mejor
La idea detrás de la búsqueda a ciegas es examinar el árbol Se parece a la búsqueda por método del gradiente solo que
entero de una manera ordenada, usando todos los operadores y ahora si hay como retroceder si es que se ha escogido un
generando tantos nodos sucesores como sea necesario para camino con una función de evaluación menor pero que no
encontrar la solución deseada. [3] lleva a la meta.[5]

A. Búsqueda en Amplitud C. Búsqueda A*

Es equivalente a recorrer un árbol por niveles. Dado un Es un algoritmo que encuentra la ruta de menor coste entre
nodo v, considerado raíz, se empiezan a visitar todos los nodos dos puntos. Es uno de los algoritmos más usados gracias a su
hijos de v antes de pasar al siguiente nivel, luego todos los desempeño y precisión. Su fundamento se basa en combinar el
nodos hijos que están en un siguiente nivel y así conocimiento de la función de evaluación con el coste del
sucesivamente hasta recorrer todos los nodos. Utiliza una camino, formando una nueva función en la que vamos a
estructura de cola (FIFO). [5] guiarnos que es igual a la función de evaluación más el coste
del camino. De igual manera se va visitando a los nodos que
B. Búsqueda en Profundidad menor valor de función tengan hasta llegar a la meta.
Es equivalente a recorrer un árbol por ramas. Dado un nodo
v, considerado raíz, se empiezan a visitar todos los nodos hijos D. Búsqueda Avara
correspondientes a uno de sus hijos hasta llegar al final de la Denominada Greedy Search, es derivada de la búsqueda
rama. Si no encuentra la meta, continua por el siguiente hijo primero el mejor, siendo la diferencia fundamental la
de la raíz haciendo el mismo recorrido a profundidad hasta bidireccional del grafo con la que va a contar la búsqueda
llegar al objetivo. Utiliza una estructura de pila (LIFO).[5] avara, además de poder partir de cualquier nodo para hacerlo
raíz.
C. Búsqueda Bidireccional
Se llevan a cabo dos búsquedas, una “descendente” que
inicia en el nodo raíz, y otra “ascendente” que inicia desde la VII. GRAFO ALEATORIO
meta. Se puede escoger ya sea una búsqueda en amplitud o en El grafo aleatorio es de gran utilidad para poder probar
profundidad para recorrer el grafo. El proceso termina cuando todos los algoritmos de búsquedas de manera eficiente,
la búsqueda converge en algún nodo.
 3

evitando tener que ingresar manualmente los nodos, Se logra apreciar que cada nodo tiene su función de
relaciones, costos, funciones de evaluación, entre otros. evaluación y que cada hijo tiene un coste de camino con
La creación de los nodos aleatorios para formar un grafo, respecto al padre.
basa su proceso en la generación de números aleatorios y el
almacenamiento en una tabla hash, siendo los números, los
nombres de los nodos para mayor comodidad y entendimiento. VIII. ANÁLISIS Y RESULTADOS
Por cuestiones de eficiencia en cuanto al tiempo, las Se ha realizado pruebas con los algoritmos para sacar
pruebas se las ha realizado implementado un grafo con conclusiones a cerca de los mismos y verificar su
ramificaciones de hasta dos nodos (árbol binario), en otras funcionamiento y eficiencia. Para evaluar, se ha basado en
palabras, cada padre va a tener un máximo de dos hijos, cuatro parámetros los cuales se los ha mencionado
haciendo que tanto la creación del grafo como las búsquedas anteriormente, que son: Tiempo de ejecución, si encuentra
sean más rápidas. meta o no, líneas de código y el número de iteraciones. Se han
A. Parámetros de Entrada y Salida tomado cinco muestras y se las ha promediado para tener una
El único parámetro de ingreso que va a aceptar la función referencia fija.
de grafo aleatorio es el número n de nodos que queramos El modelo con el cual se ha hecho las pruebas consta de:
crear.
La salida del grafo aleatorio como habíamos dicho  Número de nodos del grafo: 100
anteriormente, es la tabla hash completa con los n nodos  Origen: 1
creados, junto con sus valores de heurísticas, costes de  Destino: 90
caminos, relaciones y nombres.
El equipo en el que se han realizado las pruebas tiene las
B. Pseudocódigo siguientes especificaciones:

 Procesador: Intel Core 2 Duo

 Número de núcleos: 2
 Frecuencia básica del procesador: 2.10 GHz
 Memoria RAM: 4 GB
 Memoria Caché: 2MB

A. Búsquedas a Ciegas
TABLA I
PRUEBAS DE LOS ALGORITMOS DE BÚSQUEDAS A CIEGAS SOBRE EL NÚMERO
DE ITERACIONES.

Búsqueda Ite. 1 Ite. 2 Ite. 3 Ite. 4 Ite. 5

Fig. 1. Pseudocódigo del grafo aleatorio.

Amplitud 9 9 9 9 9
Profundidad 11 11 9 7 11
C. Resultado del Grafo Aleatorio Bidireccional 4 3 4 4 3
El grafo que se muestra a continuación tiene las siguientes
características: Profundidad Iterativa 54 34 66 34 34

 Número de Nodos: 10 Costo Uniforme 7 8 10 11 10

 Número máximo de hijos: 2

50
40
30
20
10
0

Fig. 2. Grafo Aleatorio de 10 nodos.

Fig. 3. Diagrama de barras del número de iteraciones de cada algoritmo.
 4

amplitud y profundidad prácticamente son iguales ya que

TABLA II disponen de tiempo e iteraciones similares. El cuanto a la
PRUEBAS DE LOS ALGORITMOS DE BÚSQUEDAS A CIEGAS SOBRE EL NÚMERO búsqueda por costo uniforme, se puede decir que, ofrece
DE TIEMPOS DE EJECUCIÓN EN MICROSEGUNDOS.
iteraciones reducidas con un mayor tiempo, pero encuentra
Tem Temp. Temp. Temp. una ruta con un coste mínimo. Y por último, para este caso la
Búsqueda Temp. 5
p. 1 2 3 4 búsqueda en profundidad iterativa resultó nada eficiente ya
que nos ofrece un número elevado de iteraciones realizadas en
Amplitud 320 153 152 179 110 un tiempo largo.
Profundidad 295 138 112 84 80 En cuanto a la longitud del código se puede decir que las
búsquedas más básicas tienen menor extensión, no siendo así
Bidireccional 344 70 86 96 49 las búsquedas iterativas y bidireccionales que ocupan un
Profundidad mayor espacio; por lo que se puede decir que estas últimas
860 364 11408 327 2460 tienen cierto grado de complejidad mayor que el resto o que en
Iterativa su defecto, la implementación no está realizada
Costo eficientemente.
47563 169 175 141 133
Uniforme
B. Búsquedas Heurísticas

TABLA IV
1000 PRUEBAS DE LOS ALGORITMOS DE BÚSQUEDAS HEURÍSTICAS SOBRE EL
NÚMERO DE ITERACIONES.
800
600 Búsqueda Ite. 1 Ite. 2 Ite. 3 Ite. 4 Ite. 5
400 Gradiente 5 2 5 2 2
200
0 Primero el Mejor 14 8 13 8 8

A* 7 9 9 9 11
Avara 12 11 9 11 5

Fig. 4. Diagrama de barras del tiempo de ejecución de cada algoritmo.

50
TABLA III 40
ANÁLISIS DE FUNCIONAMIENTO Y EFICIENCIA DE LOS ALGORITMOS DE
30
BÚSQUEDAS A CIEGAS.
20
Tiempo Encuentra Líneas de
Búsqueda Iteraciones 10
(us) Meta código
0
Amplitud 183.49 Si 9 17
Profundidad 142.032 Si 9.8 21
Bidireccional 129.52 Si 3.6 32
Fig. 5. Diagrama de barras del número de iteraciones de cada algoritmo.
Solo si la
meta se
TABLA V
Profundidad encuentra PRUEBAS DE LOS ALGORITMOS DE BÚSQUEDAS HEURÍSTICAS SOBRE EL TIEMPO
3084.36 44.4 38
Iterativa dentro del DE EJECUCIÓN EN MICROSEGUNDOS.

nivel de Temp. Temp. Temp. Temp. Temp.

Búsqueda
búsqueda 1 2 3 4 5
Costo Gradiente 237,0 37,15 83,50 552,30 37,15
9636.69 Si 9.2 22
Uniforme
Primero el
578,7 134,41 1893,5 329,40 89,45
Mejor
Con lo que podemos decir que en las búsquedas a ciegas, la
búsqueda bidireccional va a ser la más eficiente ya que A* 363,1 157,39 123,17 1391,0 91,89
dispone de menos tiempo y menos iteraciones para saber si
Avara 3,00 203,82 174,98 208,71 59,63
hay meta, pero no encuentra una ruta. Las búsquedas en
 5

800.00 En la parte final del proyecto se tuvo problemas en la

integración del algoritmo del grafo aleatorio con las diferentes
600.00
búsquedas, ya que en un principio cada búsqueda realizaba su
400.00 proceso dándole parámetros de nodos, y al realizar el grafo, se
200.00 lo hacía creando nodos basados en los nombres, por lo que
0.00 había una incongruencia de variables de tipo “Nodo” y de tipo
“String”. Para solucionar esto se cambió la estructura de la
clase Nodo, para que los cree basados directamente en el
nombre y no solo en la etiqueta.

Fig. 6. Diagrama de barras del tiempo de ejecución de cada algoritmo.

IX. DISCUSIONES Y CONCLUSIONES
TABLA VI  Con los resultados obtenidos en las pruebas, se puede decir
ANÁLISIS DE FUNCIONAMIENTO Y EFICIENCIA DE LOS ALGORITMOS DE que las búsquedas heurísticas son mejores, ya que parten
BÚSQUEDAS HEURÍSTICAS. de un conocimiento previo lo que hace que se ahorre, tanto
Tiempo Encuentra Líneas de en tiempo como en iteraciones.
Búsqueda Iteraciones
(us) Meta código  Las búsquedas heurísticas basan su proceso en las
Solo si el búsquedas a ciegas, utilizando a métodos de amplitud,
camino profundidad y sobre todo de costo uniforme, siendo este
Gradiente 189.43 escogido 3.2 24 último la clave para realizarlos, por lo que se facilitó
llega a la mucho la implementación de las heurísticas, ya que solo se
meta modificaban o añadían ciertos aspectos o atributos.
Primero el
605.09 Si 10.5 27  Para este problema en general, siempre hemos encontrado
Mejor
el camino, pero hay que tomar en cuenta que van a existir
A* 425.33 Si 9 22
casos en los que algunos algoritmos no llegan a la meta,
Avara 130.03 Si 50.01 25
siendo los más comunes en este caso por ejemplo el de
búsqueda en profundidad iterativa o el del gradiente, que
Para este caso, la búsqueda por el método del gradiente fue
van a depender del nivel al que se le mande a buscar o si
muy efectiva, realizando su proceso en un tiempo e iteraciones
muy bajas. Después le sigue la búsqueda avara. Se nota que la cogió el camino adecuado.
búsqueda A* dispone de un tiempo e iteraciones promedio, ya  Los tiempos que vemos son relativamente elevados, esto es
que esta se encarga de la eficiencia de los costes del camino porque la máquina en la que se trabajó es un modelo
con menor iteraciones, en este caso encuentra el mejor camino antiguo en el que su procesador ya tiene un desgaste de
en 9 iteraciones. Por último se tiene a la búsqueda primero el más de siete años.
mejor, que en este grafo resultó poco efectivo en cuanto al  A pesar de que la búsqueda bidireccional fue
tiempo utilizado. implementado sin hilos, se logra ver que es un algoritmo
En cuanto a la longitud del código se puede notar que todas muy potente que resuelve el problema con recursos de
las búsquedas tienen una extensión similar, y de hecho tienen tiempo e iteraciones muy bajas, siendo incluso más
una longitud aproximada a la de búsqueda de costo uniforme, efectivo que las búsquedas heurísticas. Lo único que le
esto se debe a que todo los algoritmos de las heurísticas son faltaría, es dar la ruta hacia la meta con su debido costo.
parecidos en su funcionamiento, pero cada uno difiere por una  El número de líneas de código es un poco ambiguo ya que
pequeña mejora que se hace para resolver distintas situaciones puede dar un sentido de eficiencia o de complejidad al
que se presenten. La cantidad de líneas que se han utilizado
software, siendo eficiencia si un problema complejo es
(aprox. 22), dan a pensar que el código es eficiente.
solucionado en pocas líneas.

C. Inconvenientes
Se tuvieron varios problemas a lo largo de la REFERENCIAS
implementación de los algoritmos de búsqueda, la mayoría [1] S. Lucci and D. Kopec, Artificial intelligence in the 21st
radicaba en la falta de conocimiento sobre el lenguaje de century: a living introduction, 2. ed. Dulles, Va.: Mercury
programación Java, la misma que nos ha limitado en cuanto al Learning and Information, 2015.
tiempo y en cuanto a mejoras ya sea de eficiencia o de [2] V. Saquicela, “Resolución de problemas mediante búsqueda.”
estética. Universidad de Cuenca, 10-Nov-2015.
[3] V. Saquicela, V. Proaño, and J. Crespo, “Búquedas a ciegas.”
Se ha querido realizar el algoritmo de búsqueda
Universidad de Cuenca, 10-Nov-2015.
bidireccional mediante hilos, pero al no tener mucho [4] V. Saquicela, J. Coronel, and D. Chimbo, “Búsquedas
conocimiento se tuvo muchos errores y no se logró Heurísticas.” Universidad de Cuenca, 10-Nov-2015.
implementar eso, por lo que se tuvo que hacer un algoritmo [5] G. Pajares Martinsanz and M. Santos Peñas, Inteligencia
netamente secuencial; pero a pesar de ser secuencial se logra artificial e ingeniería del conocimiento. Paracuellos del Jarama
ver el poder del algoritmo. (Madrid: RA-MA, 2005.