RESOLVER PROBLEMAS MEDIANTE BÚSQUEDA
INTRODUCCIÓN
Las estrategias de búsqueda que puede utilizar una agente para encontrar la solución a un problema pueden ser informadas o no informadas, cada una de estas define un estado inicial (primer estado en el que se encuentra el agente), una función sucesor (generada a partir del estado inicial), un test objetivo (determina se los estados son objetivos, es decir que conducen a la solución) y costo del camino (cuanto toma llegar a la solución).
Las búsquedas informadas contienen información adicional del problema más allá de su definición, al contrario de las búsquedas no informadas donde el agente no cuenta con información adicional del problema que busca resolver, es decir no tiene una base de conocimiento. La característica principal de este tipo de búsqueda es que genera estados posibles en base a un estado inicial y determina si dentro de la secuencia de estado existen estados objetivos (estados que conducen a la solución).
Existen diferentes tipos de búsquedas no informadas, entre ella tenemos: primero en anchura, primero en profundidad, profundidad limitada entre otras, a continuación se habla sobre las características de estas búsquedas y su funcionamiento.
MARCO TEÓRICO
AGENTES RESUELVES PROBLEMAS
La
idea es ver como un agente puede encontrar una secuencia de acciones que
alcance sus objetivos, cuando ninguna acción simple lo hará.
Los agentes resolventes-problemas deciden que hacer para encontrar secuencias de acciones que conduzcan a los estados deseables. Los agentes inteligentes deben maximizar su medida de rendimiento, esto se simplifica en: Elegir un objetivo y tratar de satisfacerlo. Para ello. Se mira el por qué y cómo se puede hacerlo. Pasos para solucionar un problema
Los agentes resolventes-problemas deciden que hacer para encontrar secuencias de acciones que conduzcan a los estados deseables. Los agentes inteligentes deben maximizar su medida de rendimiento, esto se simplifica en: Elegir un objetivo y tratar de satisfacerlo. Para ello. Se mira el por qué y cómo se puede hacerlo. Pasos para solucionar un problema
Estrategias de búsqueda no informada
El término significa que ellas no tienen información adicional acerca de los estados más allá de la que proporciona la definición del problema. Todo lo que ellas pueden hacer es generar los sucesores y distinguir entre un estado objetivo de uno que no lo es. Existen seis tipos de búsquedas no informadas que se detallan a continuación:
Búsqueda primero en anchura
La búsqueda primero en anchura es una estrategia sencilla en la que se expande primero el nodo raíz, a continuación se expanden todos los sucesores del nodo raíz, después sus sucesores, etc. En general, se expanden todos los nodos a una profundidad en el árbol de búsqueda antes de expandir cualquier nodo del próximo nivel.
Busqueda de costo uniforme
La búsqueda primero en anchura es óptima cuando todos los costos son iguales, porque siempre expande el nodo no expandido más superficial. Con una extensión sencilla, podemos encontrar un algoritmo que es óptimo con cualquier función costo. En vez de expandir el nodo más superficial, la búsqueda de costo uniforme expande el nodo n con el camino de costo más pequeño. Notemos que si todos los costos son iguales, es idéntico a la búsqueda primero en anchura.
Búsqueda primero en profundidad
La búsqueda primero en profundidad siempre expande el nodo más profundo en la frontera actual del árbol de búsqueda. La búsqueda procede inmediatamente al nivel más profundo del árbol de búsqueda, donde los nodos no tienen ningún sucesor. Cuando esos nodos se expanden, son quitados de la frontera, así entonces la búsqueda «retrocede» al siguiente nodo más superficial que todavía tenga sucesores inexplorados.
Búsqueda de profundidad limitada
Se puede aliviar el problema de árboles ilimitados aplicando la búsqueda primero en profundidad con un límite de profundidad L predeterminado. Es decir, los nodos a profundidad L se tratan como si no tuvieran ningún sucesor. A esta aproximación se le llama búsqueda de profundidad imitada El límite de profundidad resuelve el problema del camino infinito. Lamentablemente, también introduce una fuente adicional de incompletitud si escogemos L< d, es decir, el objetivo está fuera del límite de profundidad.
Búsqueda primero en profundidad con profundidad iterativa
La búsqueda con profundidad iterativa (o búsqueda primero en profundidad con profundidad Iterativa) es una estrategia general, usada a menudo en combinación con la búsqueda primero en profundidad, la cual encuentra el mejor límite de profundidad. Esto se hace aumentando gradualmente el límite (primero 0, después 1, después 2, etcétera) hasta que encontramos un objetivo. Esto ocurrirá cuando el límite de profundidad alcanza d (profundidad del nodo objetivo).
Búsqueda bidireccional
La idea de la búsqueda bidireccional es ejecutar dos búsquedas simultáneas: una hacia delante desde el estado inicial y la otra hacia atrás desde el objetivo, parando cuando las dos búsquedas se encuentren en el centro.
CONCLUSIONES
La búsqueda primero en profundidad expande el nodo izquierdo y todos sus nodos siguientes hasta encontrar la solución, si encuentra un estado no objetivo regresa y continua con el nodo de al lado. La búsqueda con profundidad limitada es una mejora de la de profundidad sola que esta se establece un límite de profundidad, ya que el agente podría expandir todos los nodos del lado izquierdo, irse al infinito y no encontrar la solución. Al establecer este límite también surge el problema de que la solución este en un nivel al que no se puede llegar es porque esto que la búsqueda con profundidad iterativa aumenta los nodos según los estados objetivos.
BIBLIOGRÁFICAS
Rihawi, I .2009. Búsqueda de costo uniforme .Consultado 29 de Nov. 2015 .(En línea).Formato HTML. Disponible en : https://poiritem.wordpress.com/2009/12/06/6-5-1-busqueda-no-informada-algoritmo-de-coste-uniforme/
Russell, S y Norvig, P. 2008. Inteligencia Artificial Un Enfoque Moderno. 2 ed. España. Pearson Education.
Robin, D.2010. Búsqueda Bidireccional .Consultado 29 de Nov. 2015.(En línea). Formato HTML. Disponible en : http://intelligence.worldofcomputing.net/ai-search/bidirectional-search.html#.VKgbgiuG8po
