INTRODUCCIÓN:
Seguimos estudiando esas técnicas que hacen que nuestras búsquedas sean posibles para la aplicación en la Inteligencia Artificial, en las publicaciones anteriores se habían tratado sobre técnicas de búsqueda como la heuristica, el sistemas de producción todas estas su fin ultimo es buscar, que lo que se le indique, esto es aplicado ya aun problema real, para este caso las llamadas búsqueda ciega solo utiliza información de si el estado donde se aya es objetivo o no esto le sirve para poder guiar su proceso de búsqueda.
BÚSQUEDA CIEGA:
Conocida como búsqueda no informada, es decir solo conoce de donde procede pero no considera a donde va ni la utilidad, ventaja, distancias, simplemente recorre los todos los nodos de un árbol por así decirlo existen entre estas técnicas llamadas búsqueda en anchura y amplitud.
De manera general la descripción de cada uno de ellos es la siguiente
BÚSQUEDA EN ANCHURA: Esta técnica su fin es recorrer todos los nodos del mismo nivel que de donde se encuentra como todo siempre la posición sera el inicio y como final el objetivo buscado, por ejemplo
como se representa en la imagen, cada figura de color verde representa una posición o un nodo, entonces según la definición sera recorrer todos las posiciones del mismo nivel de donde se encuentre, justo en ese momento hasta encontrar el objetivo y cada que se encuentre en un estado se preguntara si es el objetivo sino se ara un avance si hay mas nodos o un retroceso. Ventajas: si el problema tiene una solución este procedimiento garantiza el encontrarla. Si hubiera varias soluciones se obtiene la de menor coste (la óptima), es decir, la que requiere un menor número de pasos (si consideramos un coste uniforme de aplicación de los operadores).
Desventajas: si el nivel de profundidad asociado a la solución es significativamente menor que el factor de ramificación se expandirían demasiados nodos inútilmente. Por otro lado la principal desventaja de este método es el espacio de almacenamiento requerido. Esto lo hace prácticamente inviable para problemas complejos, como suelen ser los del mundo real.
ver mas.
- ALGORITMO BÚSQUEDA EN ANCHURA:
Sea G = (V, A) un grafo conexo, V’ = V un conjunto de vértices, A’ un vector de arcos inicialmente vacío y P un vector auxiliar inicialmente vacío:
- Se introduce el vértice inicial en P y se elimina del conjunto.
- Mientras V’ no sea vacío repetir los puntos 3 y 4. En otro caso parar.
- Se toma el primer elemento de P como vértice activo.
- Si el vértice activo tiene algún vértice adyacente que se encuentre en V’:
Se toma el de menor índice.
Se inserta en P como último elemento.
Se elimina de V’.
Se inserta en A’ el arco que le une con el vértice activo.
Si el vértice activo no tiene adyacentes se elimina de P.
BÚSQUEDA EN PROFUNDIDAD: Se refiere en buscar esta vez no por niveles sino según sea el camino que se aya elegido recorrerlo hasta que ya no existan mas nodos al final, es decir en expandir un único camino desde la raíz hasta el ultimo en esa rama si ya no existen mas nodos retrocede y selecciona otro camino a los siguientes nodos por descubrir.por ejemplo:
En la imagen se muestra la forma de búsqueda en profundidad se recorre cada nodo buscando el objetivo en cada nodo si no esta el objetivo se retrocede y se busca en una nueva rama de nodos seguidamente hasta conseguir el final de cada rama.
Ventajas: la principal ventaja de esta algoritmo radica en el reducido valor de su complejidad espacial. Cuando existen múltiples soluciones posibles la eficiencia del algoritmo aumenta.
Desventajas: la dificultad estriba en el tiempo requerido. El algoritmo puede dedicarse a recorrer un camino demasiado largo que no conduzca a ninguna solución. Es más, si no se guarda constancia de los nodos que forman el camino recorrido se podría caer en ciclos y el proceso no acabaría. El problema por tanto es determinar cuál debe ser lp. Si éste es inferior a la longitud real del camino de la solución, ésta nunca se encontraría, y si es mucho mayor sería ineficiente. Esta es la razón por la que lp debería llamarse límite de exploración.
Ventajas: la principal ventaja de esta algoritmo radica en el reducido valor de su complejidad espacial. Cuando existen múltiples soluciones posibles la eficiencia del algoritmo aumenta.
Desventajas: la dificultad estriba en el tiempo requerido. El algoritmo puede dedicarse a recorrer un camino demasiado largo que no conduzca a ninguna solución. Es más, si no se guarda constancia de los nodos que forman el camino recorrido se podría caer en ciclos y el proceso no acabaría. El problema por tanto es determinar cuál debe ser lp. Si éste es inferior a la longitud real del camino de la solución, ésta nunca se encontraría, y si es mucho mayor sería ineficiente. Esta es la razón por la que lp debería llamarse límite de exploración.
- ALGORITMO BÚSQUEDA EN PROFUNDIDAD:
Sea G = (V, A) un grafo conexo, V’ = V un conjunto de vértice, A’un vector de arcos inicialmente vacío y P un vector auxiliar inicialmente vacío:
- Se introduce el vértice inicial en P y se elimina del conjunto V’.
- Mientras V’ no sea vacío repetir los puntos 3 y 4. En otro caso parar.
- Se toma el último elemento de P como vértice activo.
- Si el vértice activo tiene algún vértice adyacente que se encuentre en V’:
Se toma el de menor índice.
Se inserta en P como último elemento.
Se elimina de V’.
Se inserta en A’ el arco que le une con el vértice activo.
Si el vértice activo no tiene adyacentes se elimina de P.
CONCLUSIONES:
Las búsquedas para las aplicaciones de la IA son tan relevantes que para poder aplicarlas en un problema real se necesita de la compresión de cada uno de las técnicas de búsqueda, mi manera de comprender es que por cada problema real se necesita una cierta aplicación de las técnicas que hasta ahorita hemos estado haciendo mencion, cada una de ellas tiene ventajas y desventajas por el uso de memoria algunas mas necesitan recolectar mas información para poder ejecutar de manera optima su búsqueda, consiguiendo así resolver problemas que requieren de cierta inteligencia los mas reflejados son los juegos de ajedrez que necesitan algoritmos de búsqueda de soluciones optimas que lo llevaran a la victoria, como el que se le aplica a un artefacto que de tal forma pueda resolver un laberinto necesita información para poder salir, eso se logra a través de la recolección de caminos y rutas de forma que le permitan llegar al objetivo, o como los juegos donde se logra obtener el siguiente salto del usuario para ellos el algoritmo debe estar ya preparado lógicamente que averigüe cual sera el siguiente movimiento y muchas mas aplicaciones en la Inteligencia Artificial.
REFERENCIAS:
http://www.dma.fi.upm.es/java/matematicadiscreta/busqueda/
http://blog.vidasconcurrentes.com/programacion/busqueda-en-profundidad-y-busqueda-en-anchura/
