Universidad Nacional Federico Villarreal Escuela Profesional de Ingeniera de Sistemas

TEMA: METODOS DE BUSQUEDA A CIEGAS

Mag. Guissella Romero Horna *

Mtodos bsicos de BsquedaCmo resolver el problema de control en sistemas de reglas de produccin?Tcnicas bsicas para encontrar caminos enredes de estados.

Por el momento: - no se intenta encontrar la solucin ptima- desarrollo de rbol de bsqueda

*Un ejemplo:Dos tareas posibles:1. ENCONTRAR un (el) camino. = costo computacional

2. RECORRER el camino. = costo de recorrido 2. Encontrar caminos ptimos (prximo captulo).

*

*Comentarios:Por el momento no estamos interesados en caminos ptimos, entonces podemos omitir los costos.Los nodos representan el camino parcial desde la raz a ellos!!

*Terminologa:Nodo, ramaProgenitor, hijo, ancestro, descendienteNodo raiz, nodo objetivoExpandir / Nodo Abierto/ Nodo cerrado/factor de ramificacin

Mtodos de bsqueda a ciegasMtodos que no usan ningn conocimiento especfico acerca del problema:Primero en profundidadPrimero en amplitudBsqueda No-determinsticaProfundizacin IterativaBsqueda Bi-direccional

Bsqueda primero en profundidadExpandir el rbol tan profundamente como sea posible, retornando a niveles superiores cuando sea necesario.

*Bsqueda primero en profundidad= seguim. Cronolg.hacia atrs Seleccionar un hijo convencin: izq.-a-derechaRepetidamente ir al hijo siguiente, tanto como sea posible.Volver a las alternativas no visitadas (nivel ms alto) solo cuando fuere necesario.BCEDFGSA

* Algoritmo bsqueda primero en profundidad:1. COLA

*Criterios de evaluacin:Completitud:El algoritmo siempre encuentra un camino? (para toda RED en que al menos un camino exista)Velocidad (complejidad de tiempo en las peores cond.) : Cul es el mximo nmero de nodos que puede ser necesario que sean creados?Memoria (complejidad de espacio en las peores cond.) : Cul es la mxima cantidad de nodos que puede ser necesario almacenar?Expresado en trminos de: d = profundidad del rbol b = factor de ramific. (promedio) del rbol m = profundidad de la solucin menos profunda

*Nota: aproximaciones !!En nuestro anlisis de complejidad, no tenemos en cuenta la deteccin de ciclos .Los resultados solo se aplican formalmente a las variantes de nuestros algoritmos SIN verificacin de ciclos.Estudiar el efecto de la deteccin de ciclos en la complejidad es dificultoso: la recarga que implica esta verificacin PUEDE o NO ser compensada por la reduccin de tamao del rbol.

Adems: nuestro anlisis NO toma en cuenta la longitud (espacio) de representacin de caminos !!

*Completitud (depth-first)Completo para REDES FINITAS. (= REDES con nmero finito de nodos)IMPORTANTE: Esto is debido a la integracin de LOOP-checking en esta versin de Depth-First (y en todos los otros algoritmos que se presentarn) ! SI no removemos caminos con ciclos, entonces Depth-First no es completo (puede quedar atrapado en loops de una red finita)

Nota: NO necesar. encuentra el camino ms corto.

*Velocidad (depth-first)En el peor caso: el (nico) nodo objet. puede estar en la rama del extremo derecho, Gdb

Bsqueda primero en amplitudExpande el rbol capa por capa, Avanzando en profundidad.

*Breadth-first search:Moverse hacia abajo, nivel por nivel, hasta que el objetivo sea alcanzado.

*UNICA DIFERENCIA!Algoritmo prim.en amplitud:1. COLA

*Completitud (breadth-first)COMPLETA an para REDES implcitamente infinitas!Permanecera completa an sin nuestro loop-checking.

Nota: SIEMPRE encuentra el camino ms corto.

*Bsqueda No-determinstica:1. COLA

*Bsqueda por profundizacin iterativaRestringe una bsqueda depth-first a una profundidad fija.

Si no se encontr ningn camino, incrementar la profundidad y recomenzar la bsqueda.

*Depth-limited search:

*Algoritmo de profundizacin iterativa:

*Bsqueda bi-direccional Computa el rbol tanto desde el nodo de comienzo como desde el nodo objetivo, hasta que estos rboles se encuentran.

*Bsqueda bi-direccional SI podemos describir EXPLCITAMENTE el estado OBJETIVO, YContamos con reglas para razonamiento HACIA ADELANTE Y HACIA ATRAS:Objet.Inicio

*Algoritmo bi-direccional:1. COLA1