I. INTRODUCCIÓN
Habiendo entendido en los temas anteriores, qué es un agente resolvente de problemas y cuáles son los tipos de problemas que existen, lo siguiente que se necesita saber, es cómo se encuentra una solución al problema.
Cuando se nos presenta un problema, a menudo analizamos las acciones que podemos realizar para resolverlo, casi siempre existen al menos dos opciones para llegar a un estado deseado, al igual que para llegar a una ciudad existen distintos caminos, así mismo existen varios caminos que pueden llevar a una solución, sin embargo, un camino puede ser más apropiado que otro pese a que ambos lleven al mismo destino, aspectos como: el tráfico, la distancia, el estado de la carretera, entre otros, conllevan a que un camino sea mejor que otro al momento de elegir por qué camino ir para llegar un destino.
Al igual que elegir un camino, los agentes resolventes de problemas también tienen varios caminos con los cuales pueden llegar a una solución, estos caminos son acciones que pueden realizar, y dichas acciones tienen consecuencias que provocan un estado, si este estado es el deseado entonces se sabe que el camino o la acción que se realizó es correcta, si no, se puede concluir que ese camino no es adecuado y se deben buscar en los siguientes.
Lo anteriormente dicho, puede asemejar lo que son las estrategias de búsqueda, la búsqueda constituye las acciones a realizar para encontrar la solución y las estrategias son la elección de los distintos caminos, ya que de la elección de los mismos depende el éxito de la solución del problema.
II. OBJETIVO
La finalidad de ésta publicacion es conocer las estrategias de búsqueda no informada que realizan los agentes resolventes de problemas, para llegar a una solución deseada.
III. MARCO TEÓRICO
Las búsquedas no informadas también son denominadas búsqueda a ciegas, y esto es porque no tienen información suficiente acerca de los estados.
Imagen 1. El Puzzle 8 es un ejemplo ya que no se tiene información acerca de los estados posibles.
Los tipos de búsqueda no informada que existen se muestran en el siguiente gráfico:
Gráfico 1. Estrategias de búsqueda no informada
3.1. BÚSQUEDA PRIMERO EN ANCHURA
La búsqueda en anchura consiste en buscar horizontalmente los nodos, es decir expandir de izquierda a derecha, todos los nodos de un nivel, para así poder pasar al siguiente nivel, es una búsqueda óptima cuando el espacio de estados no es infinito, sin embargo esta búsqueda tiene complejidad de espacio ya que se deben guardar en memoria, los nodos extendidos.
La búsqueda en anchura tiene una estructura de cola FIFO, es decir, el primero en extender es el primero en extender a nuevos nodos y así sucesivamente.
Gráfico 2. Ejemplo de búsqueda primero en anchura
Completitud: Es completo si el número de estados posibles es finito.
Optimización: No es tan óptimo si el factor de ramificación es infinito.
Complejidad del tiempo: Existe complejidad de tiempo.
Complejidad de espacio: Se debe guardar en memoria los nodos expandidos.
3.2. BÚSQUEDA PRIMERO EN PROFUNDIDAD
La búsqueda primero en profundidad consiste en buscar verticalmente es decir, el nodo raíz se expande , luego el hijo es expandido, a los siguientes de manera vertical y por la izquierda, en caso de que el nodo este repetido se pasa al siguiente nodo de la derecha, esto se realiza hasta terminar en el último nodo de esa rama. Se puede decir que tiene una estructura de cola LIFO.
Gráfico 3. Ejemplo de búsqueda por profundidad
Completitud: Es incompleto si se hace una mala elección en la rama, se podría nunca llegar a la solución.
Optimización: No es óptimo cuando hay un sin número de estados posibles, ya que no hay solución optima.
Complejidad del tiempo: El tiempo puede ser infinito si se toma un mal camino.
Complejidad de espacio: No necesita tanta memoria, ya que almacena un solo camino.
La búsqueda primero en profundidad tiene 3 variantes explicadas en el siguiente gráfico.
Gráfico 4. Variantes de la búsqueda primero en profundidad
3.3. BUSQUEDA BIDIRECCIONAL
Es aquella en la que se puede tomar dos direcciones, hacia adelante desde el estado inicial o hacia atrás desde el estado objetivo, estas direcciones se toman al mismo tiempo.
La búsqueda bidireccional es considerada una búsqueda que posee un algoritmo llamado de fuerza bruta, debido a que necesita tener un estado objetivo planteado, es decir que necesita conocer cuál será el objetivo, por ki tanto no es simplemente una prueba para una condición deseada(Robin. 2009)
Gráfico 5. Ejemplo de búsqueda bidireccional
Completitud: Es completo ya que si la búsqueda hacia adelante y la búsqueda hacia atrás están en la misma frontera, al encontrarse e habrá encontrado la solución.
Optimización: Es óptimo debido a que se encuentra la solución en menos pasos q las otras búsquedas
Complejidad del tiempo: Se optimiza el tiempo ya que la solución siempre está en medio.
Complejidad de espacio: al menos una de las búsquedas debe ser guardad en memoria.
Esta búsqueda utiliza dos algoritmos los cuales son front to back y front to front y un ejemplo de la utilización de ésta búsqueda, podría ser el algoritmo DIJSKTRA publicado en 1959 que resuelve una ruta dando un árbol de las mismas, a continuación es explicado en el siguiente video.
3.4. BUSQUEDA DE COSTO UNIFORME
Esta búsqueda hace una expansión de los nodos que tengan un costo de camino más pequeño, por lo tanto esta búsqueda no se enfoca en el número de pasos a seguir sino más bien en el costo que estos pasos tienen. (Ruiz, J; Alonso, J; Martín, M; Hidalgo, M. 2012).
Este tipo de búsqueda trabaja con grafos binarios y su funcionamiento es asignar un costo al camino que recorre, la búsqueda de costo uniforme se relaciona mucho con la búsqueda primero en anchura, diferenciandose en el costo que asigna la primera en la elección de las acciones que realiza. (Rihawi, I .2009).
Gráfico 6. Ejemplo de búsqueda de costo uniforme
Completitud: Es incompleto si la búsqueda se da por un nivel que tenga un coste muy bajo pero conlleve realizar los mismos pasos infinitamente.
Optimización: Si el costo es mayor a alguna constante positiva pequeña se puede asegurar la optimización.
Complejidad del tiempo: Esta búsqueda podría ser infinita si se elige una acción que tenga un coste de cero pero que haga que se repitan los estados una y otra vez.
Complejidad de espacio: No tiene mayor complejidad con la memoria.
IV. CONCLUSIÓN
Las estrategias de búsqueda no informada son utilizadas cuando no se sabe del problema más que su estado inicial y su estado objetivo, estas estrategias sirven para encontrar una solución a un problema.
Existen distintas estrategias, cada una tiene una variación en cuanto a los 4 factores más importantes en la resolución de un problema, los cuales son la optimización, completitud, la complejidad de espacio y la complejidad de tiempo.
Pese a que cada una de estas estrategias es distinta, su fin es común es resolver un problema, sin embargo, se debe elegir correctamente la estrategia que puede resolver el problema que el agente tiene, ya que cada una de las estrategias de búsqueda no informada, sirve para algún tipo de problema específico.
V. BIBLIOGRAFÍA
Hermoso, R y Centeno, R. 2010. Inteligencia Artificial. ES. Consultado el 20 de abr. 2015. Formato PDF. Disponible en: www.ia.urjc.es/cms/sites/default/files/userfiles/.../tema01_to_print.pdf
Peréz, R. 2007. Estrategias de resolución de problemas. (En línea). ES. Consultado, 20 de abr.2015. Formato PDF. Disponible en: http://www.unizar.es/ttm/2007-08/ESTRATEGIASI.pdf
Rihawi, I .2009. Búsqueda de costo uniforme .Consultado 21 de Abr .(En línea).Formato HTML. Disponible en : https://poiritem.wordpress.com/2009/12/06/6-5-1-busqueda-no-informada-algoritmo-de-coste-uniforme/
Robin, D.2010. Búsqueda Bidireccional .Consultado 21 de Abr 2015.(En línea). Formato HTML. Disponible en : http://intelligence.worldofcomputing.net/ai-search/bidirectional-search.html#.VKgbgiuG8po
Ruiz, J; Alonso, J; Martín, M; Hidalgo, M. 2012. Problemas de satisfacción de restricciones. ES. Consultado 21 de Abr .(En línea).Formato HTML. Disponible en : https://www.cs.us.es/cursos/ia1/temas/tema-05.pdf
Russell, S y Norvig, P. 2008. Inteligencia Artificial Un Enfoque Moderno. 2 ed. España. Pearson Education. p 1242