Estrategias de Búsqueda No Informada

ESTRATEGIAS DE
BÚSQUEDA NO
INFORMADA
◂ Las búsquedas no informadas
“ también son denominadas búsqueda

a ciegas, y esto es porque no tienen
información suficiente acerca de los
estados.
El Puzzle 8 es un
ejemplo ya que no se
tiene información
acerca de los
estados posibles.
2
Búsqueda en espacios de estados
◂ La resolución de un problema con esta
representación pasa por explorar el
espacio de estados
◂ Partimos del estado inicial evaluando
cada paso hasta encontrar un estado
final
◂ Definiremos una representación del
espacio de estados para poder
implementar algoritmos que busquen
3
Estructura de espacios de estados
◂ Estructuras de datos: Árboles y Grafos
◂ Estados = Nodos
◂ Operadores = Arcos entre nodos
(dirigidos)
◂ Árboles: Solo un camino lleva a un nodo
◂ Grafos: Varios caminos pueden llevar a
un nodo
4
Algoritmo Básico
Basado en búsqueda y recorrido en árboles y grafos.
◂ La estructura la construimos a medida que hacemos la
búsqueda.
◂ Algoritmo para una solución:
◂ Seleccionar el primer estado como el estado actual
◂ mientras el estado actual no es el estado final hacer
Generar y guardar sucesores del estado actual (expansión)
Escoger el siguiente estado entre los pendientes
(selección)
◂ – fin-mientras
◂ La selección del siguiente nodo determinará el tipo de
búsqueda. (orden de selección o expansión).
◂ Es necesario definir un orden entre los sucesores de un nodo
(orden de generación). 5
Evaluación de las Estrategias
Completitud Complejidad temporal
¿La estrategia garantiza ¿Cuánto tiempo se
encontrar una solución, necesitará para
si ésta existe? encontrar una solución?
Complejidad espacial Optimización
¿Cuánta memoria se ¿Con esta estrategia se
necesita para efectuar la encontrará una solución
búsqueda? de la más alta calidad, si
hay varias soluciones?
6
TIPOS DE
BÚSQUEDA
1. BUSQUEDA
PRIMERO EN ANCHURA
Tiene una estructura de
cola FIFO, es decir, el
primero en extender es
el primero en extender a
nuevos nodos y así
sucesivamente.
8
1. BUSQUEDA PRIMERO ANCHURA
◂ Completitud: Es completo si el número
de estados posibles es finito.
◂ Optimización: No es tan óptimo si el
factor de ramificación es infinito.
◂ Complejidad del tiempo: Existe
complejidad de tiempo.
◂ Complejidad de espacio: Se debe
guardar en memoria los nodos
expandidos.
9
2. BÚSQUEDA
PRIMERO EN
PROFUNDIDAD
Place your screenshot here
Consiste en buscar
verticalmente.
Se puede decir que tiene
una estructura de cola
LIFO.
10
2. BÚSQUEDA PRIMERO EN PROFUNDIDAD
◂ Completitud: Es incompleto si se hace
una mala elección en la rama, se podría
nunca llegar a la solución.
◂ Optimización: No es óptimo cuando hay
un sin número de estados posibles, ya que
no hay solución optima.
◂ Complejidad del tiempo: El tiempo
puede ser infinito si se toma un mal
camino.
◂ Complejidad de espacio: No necesita
tanta memoria, ya que almacena un solo
camino.
11
3. BUSQUEDA
BIDIRECCIONAL
Es aquella en la que se
puede tomar dos
direcciones, hacia
adelante desde el estado
inicial o hacia atrás
desde el estado objetivo,
estas direcciones se
toman al mismo tiempo.
12
3. BUSQUEDA BIDIRECCIONAL
◂ Completitud: Es completo ya que si la
búsqueda hacia adelante y la búsqueda
hacia atrás están en la misma frontera, al
encontrarse e habrá encontrado la
solución.
◂ Optimización: Es óptimo debido a que se
encuentra la solución en menos pasos q
las otras búsquedas
◂ Complejidad del tiempo: Se optimiza el
tiempo ya que la solución siempre está en
medio.
◂ Complejidad de espacio: al menos una
de las búsquedas debe ser guardad en
memoria.
13
4. BUSQUEDA DE
COSTO UNIFORME
hace una expansión de
los nodos que tengan un
costo de camino más Place your screenshot here
pequeño, por lo tanto

esta búsqueda no se
enfoca en el número de
pasos a seguir sino más
bien en el costo que
estos pasos tienen.
14
4. BUSQUEDA DE COSTO UNIFORME
◂ Completitud: Es incompleto si la
búsqueda se da por un nivel que tenga un
coste muy bajo pero conlleve realizar los
mismos pasos infinitamente.
◂ Optimización: Si el costo es mayor a
alguna constante positiva pequeña se
puede asegurar la optimización.
◂ Complejidad del tiempo: Esta
búsqueda podría ser infinita si se elige
una acción que tenga un coste de cero
pero que haga que se repitan los estados
una y otra vez.
◂ Complejidad de espacio: No tiene
mayor complejidad con la memoria.
15
CONCLUSIONES
◂ Las estrategias de búsqueda no informada
son utilizadas cuando no se sabe del
problema más que su estado inicial y su
estado objetivo, estas estrategias sirven para
encontrar una solución a un problema.
◂ Existen distintas estrategias, cada una tiene
una variación en cuanto a los 4 factores más
importantes en la resolución de un problema,
los cuales son la optimización, completitud, la
complejidad de espacio y la complejidad de
tiempo.
16
¡GRACIAS!

Estrategias de Búsqueda No Informada

Cargado por

Copyright:

Formatos disponibles

Estrategias de Búsqueda No Informada

Cargado por

Información del documento

Descripción original:

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Estrategias de Búsqueda No Informada

Cargado por

Copyright:

Formatos disponibles

ESTRATEGIAS DE

“ también son denominadas búsqueda

pequeño, por lo tanto

También podría gustarte