¿Qué son las técnicas de búsqueda y cuáles son sus elementos?
Las técnicas de búsqueda son una serie de esquemas de
representación del conocimiento, que mediante diversos algoritmos nos permite
resolver ciertos problemas desde el punto de vista de la I.A.
Los elementos que integran las técnicas de búsqueda son:
- Conjunto de
estados: todas las configuraciones posibles
en el dominio.
- Estados iniciales: estados
desde los que partimos.
- Estados finales:
las soluciones del problema.
- Operadores: se
aplican para pasar de un estado a otro.
- Solucionador: mecanismo que nos permite evolucionar de un estado a otro mediante un algoritmo aplicando los siguientes pasos:
1. Elegir el estado a explorar
2. Establecer un
operador que trabaje sobre el estado
elegido en el paso 1
3. Comprobar si el
resultado obtenido es un estado final
(es una solución del problema). Sino ir al paso 1.
Tipos de búsqueda en I.A.
- Búsqueda a ciegas o de generación y prueba
- Búsquedas Heurísticas
- Busque por Escalada simple
- Búsqueda Por Máxima pendiente
- Búsqueda por primero mejor
Tipos de
solucionadores
Un buen solucionador será aquel que realice su función a
bajo coste según los siguientes parámetros:
- Complejidad
temporal: tiempo empleado en obtener la solución
- Complejidad
espacial: cantidad de recursos necesarios para
obtener la solución. Por ejemplo: memoria.
La explosión combinatoria es un fenómeno que hace que el
problema no se pueda abordar computacionalmente.
Para decidir como contestar a las preguntas del solucionador podemos usar dos tipos de búsqueda:
1.-Búsqueda ciega:
- Se hace crecer el árbol de forma sistemática
- No se realiza análisis entre el estado obtenido y la solución.
Ø Sólo utiliza información acerca de si un estado es o no
objetivo para guiar su proceso de búsqueda.
Antes de
explicar los tipos de búsqueda ciega, convendría dar una serie de definiciones:
ØExpandir un nodo: obtener
los posibles hijos de un nodo a partir de la aplicación de los distintos
operadores sobre él.
ØNodo cerrado: Se han aplicado todos
los posibles operadores sobre él, obteniéndose todos sus posibles hijos.
ØNodo abierto: No han actuado todos
los posibles operadores, con lo que podrían obtenerse nuevos hijos aplicando
los operadores restantes.
ØTIPOS DE BÚSQUEDA CIEGA:
Ø Búsqueda en amplitud.
Ø Búsqueda en
profundidad.
Ø Búsqueda en profundidad
progresiva.
Ø Búsqueda bidireccional.
2.- Búsqueda heurística:
- El crecimiento del árbol se hace inyectando conocimiento.
- Este conocimiento permite calcular la distancia entre el estado obtenido y el estado final.
•Las
técnicas de búsqueda heurística usan el conocimiento del dominio para adaptar
el solucionador y, de esta manera, éste sea más potente y consiga llegar a la
solución con mayor rapidez. Por tanto, estas técnicas utilizan el conocimiento
para avanzar buscando la solución al problema.
•
Definiciones:
- Costo
del camino: coste necesario para ir del nodo raíz al nodo meta por dicho
camino.
- Costo
para hallar la solución: coste necesario para encontrar el camino anteriormente
definido.
-Potencia
heurística: capacidad de un método de exploración para obtener la solución con
un coste lo más bajo posible.
Estrategias
de búsqueda heurística
• Tipos:
• Estrategias tentativas: aquellas en las que se puede
abandonar la exploración de una rama y pasar a explorar otra en cualquier
momento del problema.
• Estrategias irrevocables: aquellas en las que no se
puede abandonar la exploración de la rama por la que se comenzó.
•Métodos:
• Gradiente
• Primero el mejor
• Búsqueda en haz
• Algoritmo A
CONCLUSIÓN:
Yo considero que las técnicas de búsqueda son muy importante en la I.A., ya que gracias a ellas se puede dar solución a una problema a través de un programador. y debemos tomar en cuenta que para decidir como contestar a las preguntas del solucionador podemos usar dos tipos de búsqueda: la ciega y la heuristica, que son en las que nosotros nos enfocamos.
Saludos.
referencias:
No hay comentarios:
Publicar un comentario