Estrategias de Búsqueda no Informada

INTRODUCCIÓN

Las búsquedas no informadas son algoritmos que no cuentan con información adicional (base de datos) y que solo cuentan con una serie de acciones o estados y que su éxito depende en saber cuándo un estado es un estado objetivo.

En el desarrollo de este tema conoceremos 6 estrategias de búsquedas no informadas.

MARCO TEÓRICO

BÚSQUEDAS NO INFORMADAS

Este tipo de búsquedas solo usan como información la definición del problema, es decir que para encontrar la solución primero deben conocer exactamente en que consiste el problema. Como se mencionó anteriormente no cuentan con información adicional del problema.

Existen 6 tipos de búsquedas no informadas (imagen 1), que serán detallas en cuanto a funcionamiento y en qué tipo de problemas se pueden utilizar.

PRIMERO EN ANCHURA

Es una estrategia sencilla que consiste en la expansión del nodo raíz, y luego todas sus sucesoras y así sucesivamente hasta expandir todos los nodos o hasta encontrar la solución.

Ejemplo:

Como nos podemos dar cuenta los nodos se expanden en cada nivel es decir, los hijos del nodo raíz, luego los hijos de estos nodos y así sucesivamente.

Evaluación de Rendimiento

Considerando que esta estrategia expande todos los nodos podemos considerarla completa si el objetivo o solución se encuentra en uno de estos nodos superficiales, pero de ser lo contrario este algoritmo tendría una desventaja y solo se debería usar en ocasiones en las que el costo de camino (pesos de entrada) sean similares, ya que de ser lo contrario se caería un costo elevado.

En cuestión de tiempo y espacio utilizados para encontrar la solución al expandir todos los nodos superficiales y suponiendo una serie de estados generados b al expandirlos tendremos b2 y luego en el siguiente nivel b2 y así en cada expansión, entonces tendremos una gran cantidad de nodos generados. Además cada nodo generado debe permanecer en memoria ya que es un antecesor del nodo por lo que su complejidad de espacio es similar a la del tiempo.

COSTO UNIFORME

Es similar a la búsqueda por anchura, con la diferencia que esta estrategia tomara en cuenta el costo del camino y expandirá el nodo que tenga el costo menor. Costo Uniforme no se preocupa por el número total de pasos a seguir, sino que solo toma en cuenta el costo que conlleva la solución, es por ello que se vuelve un poco incompleta en el caso de se repita una acción no le importara si el costo es menor, por lo que se convierte en un ciclo infinito.

Evaluación de Rendimiento

Como se mencionó anteriormente es completa en el caso de que el costo de cada acción sea igual o mayor a una constante positiva pequeña, de lo contrario se caerá en un ciclo infinito.

En cuestiones de tiempo y espacio es similar a la búsqueda por anchura.

PRIMERO EN PROFUNDIDAD

La estrategia de búsqueda primero en profundidad expande el nodo más profundo desde la parte izquierda, es común aplicar la búsqueda primero en profundidad con una función recursiva que se llama en cada uno de sus hijos.

Evaluación de Rendimiento

La búsqueda primero en profundidad tiene unos requisitos muy modestos de memoria. Necesita almacenar sólo un camino desde la raíz a un nodo hoja, junto con los nodos hermanos restantes no expandidos para cada nodo del camino.

PROFUNDIDAD LIMITADA

Como se puede apreciar en la imagen 8 el método de profundidad limitada tiene un límite o nodo máximo de expansión por lo que en muchas ocasiones no es muy completo u optimo debido a que la solución u estado objetivo podría no estar dentro de ese límite

PROFUNDIDAD ITERATIVA

El límite de la búsqueda incrementa en cada iteración (Imagen Anterior), esto sucederá hasta que se llegue a d, es decir al nodo objetivo.

BIDIRECCIONAL

CONCLUSIONES

Es necesario conocer el funcionamiento de cada una de las estrategias de búsquedas no informas para poder implementar la correcta en nuestro agente resolvente de problemas.

Cada una de estas estrategias de búsquedas tiene su forma de resolver un problema, por eso debemos saber cuál se acopla a nuestras necesidades, para no tener inconvenientes en cuanto a excesivo gasto de recursos

BIBLIOGRAFÍAS