BÚSQUEDA HEURÍSTICA

Comienza Ya. Es Gratis
ó regístrate con tu dirección de correo electrónico
Rocket clouds
BÚSQUEDA HEURÍSTICA por Mind Map: BÚSQUEDA HEURÍSTICA

1. Se apoyan

1.1. En información adicional para realizar su proceso de búsqueda.

1.2. Para mejorar la eficiencia de la búsqueda.

1.3. Costo del camino.

1.3.1. Coste necesario para ir del nodo raíz al nodo meta por dicho camino.

1.4. La función que guía el proceso toma el nombre de función heurística.

1.5. Potencia heurística.

1.5.1. Capacidad de un método de exploración para obtener la solución con un coste lo más bajo posible.

2. Función de evaluación heurística

2.1. Adquirir conocimiento en base a la experiencia.

2.2. Utiliza una función de evaluación.

2.3. Se aplica tanto operadores como la función.

2.4. F(n)=conocimiento.

2.5. F(n)=cuantas fichas están descolocadas en comportamiento con el nodo inicial.

3. Características de los métodos heurísticos.

3.1. No se garantiza que se encuentre una solución.

3.1.1. Aunque exista soluciones.

3.2. Si encuentra una solución.

3.2.1. No se asegura que tenga las mejores propiedades o de menor coste óptimo.

3.3. En ocaciones encontrar una solución en un tiempo razonable.

4. Puede tener.

4.1. Dos tipos de interpretaciones.

4.1.1. La funcion puede se una estimacion de lo proximoque se encuentra el estado de un estado objetivo.

4.1.1.1. los estados de menor valor heurístico son los mas preferidos.

4.1.2. Otro caso pueden suceder que lo que convenga sera maximizar esta función.

5. Caracterización.

5.1. Algoritmo A*.

5.1.1. Combina.

5.1.1.1. Métodos en anchura y en profundidad.

5.1.2. Se generan todos los posibles sucesores.

5.1.2.1. Se expande el que sea mas prometedor de una función heurística.

5.1.2.1.1. Estima coste del camino desde cada nodo al objetivo.

5.1.2.1.2. Coste uniforme minimiza el coste del camino hasta el nodo.

5.1.2.2. Combinando las dos funciones de evaluación simplemente sumándolas

5.1.2.2.1. f(n) = g(n) + h(n).

5.1.2.3. g(n) proporciona el coste del camino desde el nodo de inicio hasta el nodo n.

5.1.2.4. h(n) es el coste estimado del camino de menos coste desde n hasta el objetivo.

5.1.2.5. f(n) es el coste estimado de la solución de menor coste que atraviesa el nodo n.

5.1.3. Ventajas

5.1.3.1. Soluciones más cercanas a la raíz.

5.1.4. Inconvenientes

5.1.4.1. La función de evaluación se complica.

5.2. Algoritmo IDA*.

5.2.1. (Iterative-Deepening A*)

5.2.2. Se basa en la información heurística que posee para determinar el siguiente límite de la iteración.

5.2.3. El funcionamiento del algoritmo es el siguiente.

5.2.3.1. Una búsqueda en profundidad hasta donde se lo permita su límite de coste.

5.2.3.2. Cada vez que se visita todo el grafo de búsqueda.

5.2.3.2.1. El algoritmo incrementa el límite de coste.

5.3. Algoritmo DFID.

5.3.1. (Depth-First Iterative-Deepening).

5.3.2. Primera vez en 1977 cuando Slate y Atkin presentaron un programa de ajedrez.

5.3.3. Ventajas.

5.3.3.1. De la búsqueda en anchura y de la búsqueda en profundidad.

5.3.4. El desarrollo del algoritmo es el siguiente.

5.3.4.1. En cada iteración el algoritmo realiza una búsqueda limitada en profundidad.

5.3.4.2. Si en dicha iteración no se alcanza la solución óptima, entonces se incrementa dicho límite en una unidad de profundidad y se vuelve a realizar la búsqueda.

5.4. Algoritmo SMA*.

5.4.1. (Simplified Memory-bounded A*)

5.4.2. Aparece en cierta medida debido a los problemas del IDA* en espacios reducidos de memoria.

5.4.3. Realiza un control estricto de la memoria.

5.4.4. La implementación de éste resulta muy dificultosa.

6. Referencias WEB

6.1. http://www.dc.fi.udc.es/ai/~barreiro/iadocen/puzzle8-98/introprocedimiento.html

6.2. http://superinteligencia.galeon.com/aficiones1221281.html

6.3. https://www.nebrija.es/~cmalagon/ia/transparencias/busqueda_heuristica.pdf