Técnicas de Búsqueda

Técnicas de búsqueda en IA

登録は簡単!. 無料です
または 登録 あなたのEメールアドレスで登録
Técnicas de Búsqueda により Mind Map: Técnicas de Búsqueda

1. Busquedas Ciegas

1.1. Características

1.1.1. No se posee información respecto a cuantos pasos se necesita o la distancia de la meta.

1.1.2. Hace crecer el árbol de forma sistemática.

1.1.3. No realiza análisis entre el estado obtenido y la solución.

1.1.4. Utiliza información acerca de si un estado es o no objetivo para guiar su proceso de búsqueda.

1.2. Tipos

1.2.1. Búsqueda en amplitud

1.2.1.1. Para cada uno de los nodos de un nivel se aplican todos los posibles operadores.

1.2.1.2. No se expande ningún nodo de un nivel antes de haber expandido todos los del nivel anterior.

1.2.1.3. Se implementa con una estructura FIFO

1.2.1.4. Si existe una solución, la encuentra en la menor profundidad posible.

1.2.1.5. Explosión combinatoria aparece frecuentemente debido a la alta complejidad espacial y temporal de esta técnica.

1.2.2. Búsqueda en profundidad

1.2.2.1. Se realiza por una sola rama del árbol hasta encontrar una solución o hasta que se tome la decisión de terminar la búsqueda por esa dirección.

1.2.2.2. Terminar la búsqueda por una dirección se debe a que no hay posibles operadores que aplican sobre el nodo hoja o por haber alcanzado un nivel de profundidad muy grande. Si esto ocurre se produce una vuelta atrás y se sigue por otra rama hasta visitar todas las ramas del árbol si es necesario.

1.2.2.3. Tiene menor complejidad espacial que la búsqueda en amplitud.

1.2.2.4. Se pueden encontrar soluciones que están mas alejadas de la raíz que otras

1.2.2.5. Existe el riesgo de presencia de bucles infinitos.

1.2.3. Otras búsquedas ciegas

1.2.3.1. Búsqueda en profundidad progresiva

1.2.3.2. Búsqueda bidireccional

2. Búsquedas heurísiticas

2.1. Caracterísiticas

2.1.1. Se posee información sobre el problema para elegir operadores más convenientes.

2.1.2. El crecimiento del árbol se hace inyectando conocimiento.

2.1.3. El conocimiento permite calcular la distancia entre el estado obtenido y el estado final

2.1.4. Usan el conocimiento para avanzar buscando la solución al problema.

2.1.5. Hace uso de funciones de evaluación en la cual es importante mantener el equilibrio entre eficiencia y complejidad para evitar una explosión combinatoria.

2.2. Estratégias

2.2.1. Tentativas

2.2.1.1. Se puede abandonar la exploración de una rama y pasar a explorar otra en cualquier momento del problema.

2.2.2. Irrevocables

2.2.2.1. no se puede abandonar la exploración de la rama por la que se comenzó

2.3. Tipos

2.3.1. Búsqueda Best-First

2.3.1.1. También conocidas como búsquedas avaras

2.3.1.2. Intentan predecir qué tan cerca está el final de una ruta de una solución.

2.3.1.3. Las rutas que se consideran más cercanas a una solución se amplían primero.

2.3.1.4. La selección del mejor candidato se implementa usando una cola de prioridad

2.3.1.5. Aunque casi siempre es posible calcular el costo aproximado hasta la meta, es difícil hacerlo con precisión.

2.3.2. Búsqueda A*

2.3.2.1. Algoritmo de búsqueda de recorrido y recorrido de gráfico utilizada debido a su integridad, optimización y eficiencia óptima.

2.3.2.2. Almacena todos los nodos generados en la memoria.

2.3.2.3. Determina el camino a extender basándose en el costo de la ruta y una estimación del costo requerido para extender la ruta hasta la meta

2.3.2.4. El algoritmo de Dijkstra , como otro ejemplo de un algoritmo de búsqueda de costo uniforme, puede verse como un caso especial de A *

2.3.2.5. A * se usa a menudo para el problema común de búsqueda de rutas en aplicaciones como videojuegos.

2.3.3. Búsqueda Hill-Climbing

2.3.3.1. Técnica de optimización matemática que pertenece a la familia de los algoritmos de búsqueda local.

2.3.3.2. Suele llamarse algoritmo voraz local, porque toma un estado vecino "bueno" sin pensar en la próxima acción.

2.3.3.3. A partir de un estado, se realiza un bucle que constantemente se desplaza en la dirección ascendente, hasta encontrar una solución o atascarse.

2.3.3.4. Sus principales problemas son:

2.3.3.4.1. Máximos locales

2.3.3.4.2. Mesetas

2.3.3.4.3. Riscos

2.3.4. Enfriamiento simulado

2.3.4.1. Proceso de optimización global en sistemas de comportamiento estocástico.

2.3.4.2. Si el programa de enfriamiento es muy rápido las transiciones ocurren desordenadamente. Si es lelento se consigue mejor estabilidad.

2.3.4.3. Este método garantiza un óptimo global si la temperatura baja con suavidad.

2.3.4.4. El sistema inicialmente es libre de explorar el espacio de búsqueda, más tarde se centra en regiones con estados de baja energía y al final cambia solo a estados con energía menor donde alcanza un mínimo

3. Esquemas de representación del conocimiento, que mediante algoritmos nos permiten resolver problemas desde el punto de vista de la I.A.

4. Proceso de evaluar las distintas secuencias de acciones para encontrar las que lleven del estado inicial al estado objetivo.

4.1. Elementos:

4.1.1. Conjunto de estados

4.1.2. Estados iniciales

4.1.3. Estados finales

4.1.4. Operadores