Al usar agente que buscan la solucion a un problema estos agentes emplean un arbol de busqueda que es generado por un estado inicial y una funcion sucesora que determina el camino a seguir. Ahora bien la estrategia de busqueda es la que nos determina la forma como expandiremos los distintos nodos del arbol de soluciones.
Las estrategias de busqueda se pueden calsificar como estrategias no informadas y estrategias informadas; las primeras solo pueden generar los nodos solucion del arbol y verificar si han llegado a la solucion o no, dado que solo conocen cual es el estado inicial y el estado final; las segundas pueden determinar cual nodo solucion es mas prometedor valiendose de distintos tipos de informacion.
En este post trataremos las estrategias de busqueda no informadas.
Busqueda primero en anchura
Es una estrategia sencilla, basado en buscar por niveles, expande un nivel del arbol y busca dentro de los nodos solucion de ese nivel, si no encuentra la solucion, expandira el siguiente nivel y buscara en ese nuevo nivel.
Aunque es sencillo es un metodo costoso en terminos de recursos incluso para una computadora, sobre todo si consideramos problemas en los que los arboles crecen de forma exponencial al ir expandienso las ramas.
Busqueda primero en profundidad
En esta estraegia se opta por descender hasta el ultimo nodo de una rama y si no es la solucion regresamos para visitar otra rama hasta el ultimo nodo, es decir vamos rama por rama. a continuacion vemos una imagen que ejemplifica el proceso, la imagen es tomada del libro Russell y Norvig, un excelente material para el estudio de la inteligencia artificial.
Busqueda en profundidad iterativa
Esta estrategia es una variante de la estrategia en profundidad, emplea una busqueda en profundidad limitada, es decir no llega hasta el ultimo nodo de una rama, sino que se detiene en un cierto nivel, si de esta forma no encuentra ninguna solucion, cambiara el nivel de profundidad y volvera a buscar hasta encontrar un nivel optimo de busqueda.
Si lo analizamos a detalle es una combinacion de busqueda en profundidad y en anchura.
Busqueda en grafos
Consiste en usar grafos en lugar de arboles; en este caso; esta estrategia de busqueda usa lo que se denomina una lista cerrada, en la que cada nodo recuerda a cada uno de los nodos que los precedieron, de tal forma que en lugar de buscar en un arbol podemos buscar en una rejilla en la que podemos identificar caminos que nos llevan a la misma solucion, y descartar uno de ellos.
Busqueda con retroceso
En esta tecnica de busqueda se construyen soluciones parciales a medida que se avanza en la busqueda; esto significa que se marca un nodo en particular en el cual se cumplen ciertas restricciones del problema para poder volver a este nodo en caso de que al buscar mas profundamente en una de sus ramas no lleguemos a una solucion, el inconveniente es que para ciertos problemas llega resultar igual que la busqueda en profundidad
Sistemasumma.com 