Resolver problemas mediante la busqueda

Comienza Ya. Es Gratis
ó regístrate con tu dirección de correo electrónico
Resolver problemas mediante la busqueda por Mind Map: Resolver problemas mediante la busqueda

1. Agentes resolventes-problemas

1.1. Problemas y soluciones bien definidos

1.1.1. Estado inicial

1.1.1.1. Estado en el que comienza un agente.

1.1.2. Función sucesor

1.1.2.1. Una descripción de las posibles acciones disponibles por el agente.

1.1.3. Espacio de los estados

1.1.3.1. Es el conjunto de todos los estados alcanzables desde el estado inicial.

1.1.4. Camino

1.1.4.1. Un camino en el espacio de estados es una secuencia de estados conectados por una secuencia de acciones.

1.1.5. Test objetivo

1.1.5.1. Determina si un estado es un estado objetivo

1.1.6. Costo del camino

1.1.6.1. Una función costo del camino que asigna un costo numérico a cada camino.

1.1.7. Solución óptima

1.1.7.1. Una solución óptima tiene el costo más pequeño del camino entre todas las soluciones.

1.2. Formular los problemas

1.2.1. Abstracción

1.2.1.1. Es el proceso de eliminar detalles.

2. Ejemplos de problemas

2.1. Problema Juguete

2.1.1. 8 reinas

2.1.1.1. Formulación Incremental

2.1.1.1.1. Inicia con un estado vacío y aumenta la descripción del estado.

2.1.1.2. Formulación completa de estados

2.1.1.2.1. Inicia con las ocho reunas en el tablero.

2.1.2. 8 puzle

2.1.3. Mundo de la aspiradora

2.2. Problema del mundo real

2.2.1. Problema de búsqueda de una ruta

2.2.1.1. Problemas turísticos

2.2.1.2. Problema del viajante de comercio

2.2.2. Distribución VLSI

2.2.3. Navegación de robot

2.2.4. Secuenciación para el ensamblaje automatico

2.2.4.1. Diseño de proteínas

2.2.5. Búsqueda en internet

3. Búsqueda de soluciones

3.1. Árbol de búsqueda

3.1.1. Generado por el estado inicial y la función sucesor, definiendo así el espacio de estados.

3.2. Medir el rendimiento de la resolución del problema

3.2.1. Completitud

3.2.1.1. ¿Está garantizado que el algoritmo encuentre una solución cuando esta exista?

3.2.2. Optimización

3.2.2.1. ¿Encuentra la estrategia la solución óptima?

3.2.3. Complejidad en tiempo

3.2.3.1. ¿Cuánto tarda en encontrar una solución?

3.2.4. Complejidad en espacio

3.2.4.1. ¿Cuánta memoria se necesita para el funcionamiento de la búsqueda?

4. Estrategias de búsqueda no informada

4.1. No tienen información adicional acerca de los estados más allá de la que proporciona la definición del problema.

4.2. Búsqueda primero en anchura

4.2.1. Es una estrategia sencilla en la que se expande primero el nodo raíz, a continuación se expanden todos los sucesores del nodo raíz, después sus sucesores, etc.

4.3. Búsqueda de costo uniforme

4.3.1. Estrategia en la que se expande no a todos los nodos sucesores, si no que se expande al que tenga el menor costo.

4.4. Búsqueda primero en profundidad

4.4.1. Se expande al nodo más profundo.

4.5. Búsqueda de profundidad limitada

4.5.1. Misma búsqueda que la de profundidad pero se maneja un limite.

4.6. Comparación de las estrategias de búsqueda no informada

5. Evitar estados repetidos

5.1. Guardar más nodos en la memoria

5.1.1. Lista cerrada

5.1.2. Lista abierta

6. Búsqueda con información parcial

6.1. Problemas sin sensores

6.2. Problemas de contigencia

6.3. Problemas de exploración