Inteligencia Artificial. La estrategia de búsqueda

[pic 1][pic 2]

[pic 3]

• 4.2 Búsqueda de soluciones

La búsqueda de soluciones nos sirve para para poder solucionar algún problema existente. Para ello se debe realizar un análisis de las posibles soluciones, Buscando su pro y contra. Con ello podremos encontrar la solución más exacta.

• 4.3 Estrategia de búsqueda no informada

La estrategia de búsqueda es un conjunto de operaciones y procesamientos que un individuo realiza. Con el fin de poder obtener los datos necesarios para poder resolver un problema.

• 4.4 Búsqueda primero en anchura, de costo uniforme, de profundidad limitada.

Búsqueda primero anchura:

• Principio: Expandir el nodo menos profundo que no haya sido expandido.
• La frontera es una cola FIFO (Lo primero que entra lo primero que sale)

Crear una lista con un solo elemento consistente en una trayectoria o camino de longitud cero: En nodo raíz Hasta que el primer camino de la lista llegue al nodo objetivo o se llegue a la lista vacía hacer

1. Extraer el primer camino de la lista
2. Expandir el nodo final de este camino a todos los vecinos del nodo terminal.
3. Eliminar los ciclos de los caminos expandidos
4. Insertar estos nuevos caminos expandidos
5. Insertar estos nuevos caminos al final de la lista

• Fin Hasta
• Si se halla el nodo meto se notifica el éxito, si no el fracaso[pic 4]

          Busqueda de costo uniforme:

Trabaja con arboles y grafos binarios , su principal caracteristicas es asignarle un costo a su recorridonexpandiendo los nodos que son visitados. Este algoritmo esta relacionado con la busqueda primero por anchura. Lo podemos diferencial porque tiene un coste toal que basa y traza sus deciciones.este algoritmo se usa para problemas complejos.[pic 5]

 Búsqueda de profundidad limitada:

 La búsqueda en profundidad limitada se encarga de encontrar una solución si esta se encuentra dentro del limite de profundidad. El proceso que realiza consiste en visitar todos los nodos de forma ordenada pero no uniforme. Dejando caminos sin evitar en su proceso, imponiendo un límite máximo de profundidad  

• 4.5 Búsqueda primero en profundidad con profundidad iterativa.

1. Completitud: El algoritmo siempre encontrara la solución
2. Complejidad Temporal: parecida a la misma que búsqueda de anchura. El regenerar el árbol en cada interacción solo añada un factor constante a la función de coste.
3. Complejidad espacial: Parecida a la búsqueda en profundidad.
4. Optimalidad: La solución es optima igual que en la búsqueda de anchura.

• 4.6 Búsqueda bidireccional

Es la búsqueda en dos direcciones al mismo tiempo: Uno hacia adelante desde el estado inicial y la otra haca atrás  de la parte final. Esto se hace generalmente mediante la expansión de árbol con factor de ramificación B y la distancia desde el principio hasta el objetivo es d. Es un algoritmo de búsqueda de tipo fuerza bruta que requiere un estado objetivo explicito en lugar de simplemente una prueba para una condición meta La idea de esta búsqueda es recucir el tiempo de búsqueda mediante la búsqueda hacia adelante comienzo y hacia atrás de la estancia simultánea.

• 4.7 Evitar estados repetidos

Para evitar los estados repetidos son los siguientes:

1. No regresando al estado que se acaba de llegar
2. No crear rutas que contengan ciclos
3. No generar algún estado que se haya generado anteriormente

• 4.8 Búsqueda de información parcial. Problemas sin sensores, de contingencia

Cuando el conocimiento de los estados o acciones son incompletos encontramos que los diversos tipos de incompletitud conduce a tres tipos de problemas distintos.

1. Problema sin sensores (también llamados problemas conformados): si el agente no tiene ningún sensor, podría estar en uno de los posibles estados iniciales y cada acción por lo tanto podría conducir a uno de los posibles estados sucesores.
2. Problema de contingencia: Si el entorno es parcialmente observable o si las acciones son inciertas, entonces las percepciones del agente proporcionan información después de cada acción. Cada percepción posible define una contingencia que debe de planearse. A un problema se le llama entre adversarios di la incertidumbre esta causada por las acciones de otro agente.
3. Problemas de explotación: Cuando se desconocen los estados y las acciones del entorno, el agente debe actuar para descubrirlos. Los problemas de explotación pueden verse como un caso externo de problemas de contingencia.

• 4.9 Métodos de búsqueda respaldados con información.

• 4.9.1 Estrategias de búsqueda informada (Heurística).

1. La búsqueda no informada es ineficiente en la mayoría de los caos
2. El propósito de la búsqueda informada es utilizado conocimiento específico del problema para alcanzar el objetivo de manera mas eficiente.
3. La idea es ser capaces de medir la” la calidad” de un estado.
4. Eso nos permitirá dirigir la búsqueda por los estados mejores que estarán “mas cerca” del objetivo y no seguir estrategias en anchura o profundidad que no tiene en cuenta la calidad de los estados.
5. Las estrategias de búsqueda informada son mucho m as eficientes que las no informadas.

• 4.9.2 Funciones Heurísticas:

1. Funciones de evaluación f(n) mide la calidad de n
2. Un nodo tendrá calidad cuanto menor sea la distancia al objetivo
3. F(n) estima la distancia desde ese nodo n a un nodo objetivo
4. Las búsquedas informadas expanden primero los nodos que están mas cerca del objetivo; I.E. aquellos en los que la función F(n) asigna un menor valor  

• 4.9.3 Algoritmos de búsqueda local y problemas de optimización.

Los algoritmos de búsqueda local funcionan con un solo estado actual y generalmente se mueven a los vecinos del estado

Los algoritmos de búsqueda local no son sistemáticos, tienen dos ventajas claves. 1 usan muy poca memoria y 2 pueden encontrar a menudo soluciones razonables en espacios de estados grandes o infinitos (continuos) para los cuales son inadecuados los algoritmos sistemáticos.

...