BÚSQUEDA INFORMADA Y DE EXPLORACIÓN
- José Mera
- 18 jul 2015
- 3 Min. de lectura
INTRODUCIÓN
En el tema anterior se mostraron las estrategias de búsquedas no informadas y la manera en que funcionan las mismas, al momento de encontrar una solución. A continuación se presentan las estrategias de búsquedas informadas, es decir aquellas que utilizan una base de conocimiento específica sobre el problema a resolver.
Entre las estrategias de búsqueda informada tenemos: Búsqueda Voraz Primero el Mejor, Búsqueda A*, y las Búsquedas con Memoria Acotada.
MARCO TEÓRICO
BÚSQUEDA VORAZ PRIMERO EL MEJOR
Es un tipo de búsqueda en la cual se trata de expandir el nodo más cercano al objetivo, para ello se trabaja con los valores dados por la función heurística, es decir que debemos tener una especie de tabla con los valores o costo de estar en un nodo. Ejemplo:
Teniendo en cuenta estos valores el algoritmo elige la mejor ruta o la más cercana, para ello tiene en cuenta el número de nodos que expande.
Este tipo de Búsqueda tiene una similitud con la búsqueda primero en profundidad, ya que ambos siguen un camino hacia el objetivo, pero regresan al encontrar un callejón sin salida, del mismo modo comparten la desventaja de ir hacia abajo en un camino infinito y no regresar.
BÚSQUEDA A*: MINIMIZAR EL COSTO ESTIMADO TOTAL DE LA SOLUCIÓN
Es una forma más amplia o una nueva versión de la búsqueda primero el mejor, en la cual el coste del nodo se obtiene del coste para alcanzar el nodo g(n) + el coste de ir hacia el nodo h(n).
f(n) = g(n) + h(n)
Siendo f(n) el coste más barato estimado de la solución a través del nodo.
De esta manera, cuando tratamos de encontrar la solución más económica usamos primero el nodo con costo más bajo de f(n), por lo que si la función heurística satisface ciertas condiciones, la búsqueda se convierte en completa y óptima.
Si notamos en la imagen anterior se van expandiendo los nodos con más bajos.
Cabe mencionar que aunque esta búsqueda es bastante completa, tiene la desventaja de que utiliza demasiado espacio en la memoria, lo cual implica un gasto de recursos.
BÚSQUEDA HEURÍSTICA CON MEMORIA ACOTADA
Una de las maneras de reducir la exigencia de memoria requerida por la búsqueda A* es adaptarla a la idea de la iteración.
Dentro de las búsquedas con memoria acotada tenemos: Búsqueda recursiva de primero el mejor, A*MS
La búsqueda recursiva primero el mejor (BRPM), es un algoritmo bastante sencillo, como su nombre lo indica es recursivo e intenta imitar el funcionamiento de la búsqueda primero el mejor estándar, pero únicamente un espacio lineal. Su estructuración es similar a la búsqueda primero el mejor con profundidad iterativa, con la diferencia que no sigue un camino hacia abajo, simplemente mantiene una pista del valor del nodo antepasado, y si el siguiente nodo excede ese valor entonces regresa, y como se usa recursividad los valores son reemplazados.
Este es un algoritmo muy eficiente, aunque sufre de regeneración excesiva de los nodos.
La búsqueda A*MS, al igual que la A* empieza por expandir la mejor opción hasta que la memoria se llene, una vez llena la memoria no se puede regresar (realizar otro árbol de búsqueda), por lo que se debe reemplazar una hoja (nodo) que tenga el valor más alto. De este modo, el antepasado de un subárbol olvidado sabe la calidad del mejor camino en el subárbol. Con esta información, A*MS vuelve a generar el subárbol sólo cuando todos los otros caminos parecen peores que el camino olvidado.
CONCLUSIONES
Las búsquedas informadas usan una base de conocimiento para de esta manera poder llegar a una conclusión u objetivo de una manera mucho más rapida, pero esto solo se hace cuando tenemos una idea del problema a resolver.
Estas búsquedas aunque son mucho más rápidas tienen sus desventajas ya que usan demasiado la memoria.
BIBLIOGRAFÍA
Comments