Métodos básicos de BúsquedaMétodos básicos de Búsqueda

¿Cómo resolver el problema de control en ¿Cómo resolver el problema de control en sistemas de reglas de producción?sistemas de reglas de producción?

Técnicas básicas para encontrar caminos enTécnicas básicas para encontrar caminos en

redes de estadosredes de estados..

Por el momento:Por el momento:

- no se intenta encontrar la solución óptima- no se intenta encontrar la solución óptima

- desarrollo de ‘árbol de búsqueda’- desarrollo de ‘árbol de búsqueda’

2

Un ejemplo:Un ejemplo:

Dos tareas posibles:Dos tareas posibles: 1. ENCONTRAR un (el) camino. 1. ENCONTRAR un (el) camino. = costo = costo

computacional computacional

2. RECORRER el camino. 2. RECORRER el camino. = costo de recorrido= costo de recorrido

2. Encontrar caminos óptimos (próximo capítulo). 2. Encontrar caminos óptimos (próximo capítulo).

Red implícitaRed implícita

AA

DD

BB

EE

CC

FFGG

SS

33

44

44

44

55 55

44

3322

3

AA

DD

BB

EE

CC

FFGGSS

33

44

44

44

55 55

44

33

El árbol asociado de El árbol asociado de caminos parciales caminos parciales -sin ciclos--sin ciclos-

22

SSAA DD

BB DD EEAA

CC EE EE BB BB FF

DD FF BB FF CC EE AA CC GG

GG CC GG FF

GG

33

33 33

33

33

22

22

2244

44

4444

44

4444

44

44

44

44

44

5555

55 55

5555

4

Comentarios:Comentarios: Por el momento no estamos interesados en caminos Por el momento no estamos interesados en caminos

óptimos, entonces podemos omitir los costos.óptimos, entonces podemos omitir los costos.

SSAA DD

BB DD EEAA

CC EE EE BB BB FF

DD FF BB FF CC EE AA CC GG

GG CC GG FF

GG

Los nodos representan el camino parcial desde la raíz Los nodos representan el camino parcial desde la raíz a ellos!!a ellos!!

Significa:Significa:SASA Significa:Significa:

SDASDA

Signif.:Signif.: SDEBASDEBA

5

Terminología:Terminología:

Nodo, ramaNodo, rama Progenitor, hijo, ancestro, descendienteProgenitor, hijo, ancestro, descendiente Nodo raiz, nodo objetivoNodo raiz, nodo objetivo Expandir / Nodo Abierto/ Nodo cerrado/factor de Expandir / Nodo Abierto/ Nodo cerrado/factor de

ramificaciónramificación

SSAA DD

BB DD EEAA

CC EE EE BB BB FF

DD FF BB FF CC EE AA CC GG

GG CC GG FF

GG

Métodos de búsqueda a ciegasMétodos de búsqueda a ciegas

Métodos que no usan ningún conocimiento Métodos que no usan ningún conocimiento específico acerca del problema:específico acerca del problema:

Primero en profundidadPrimero en profundidad

Primero en amplitudPrimero en amplitud

Búsqueda No-determinísticaBúsqueda No-determinística

Profundización IterativaProfundización Iterativa

Búsqueda Bi-direccionalBúsqueda Bi-direccional

Búsqueda primero en profundidadBúsqueda primero en profundidad

Expandir el árbol tan profundamente Expandir el árbol tan profundamente como sea posible, como sea posible,

retornando a niveles superiores cuando retornando a niveles superiores cuando sea necesario.sea necesario.

8

Búsqueda primero en Búsqueda primero en profundidadprofundidad

= seguim. Cronológ.hacia atrás= seguim. Cronológ.hacia atrás

Seleccionar un hijo Seleccionar un hijo convención: izq.-a-convención: izq.-a-

derechaderecha Repetidamente ir al hijo Repetidamente ir al hijo

siguiente, tanto como siguiente, tanto como sea posible.sea posible.

Volver a las alternativas Volver a las alternativas no visitadas (nivel más no visitadas (nivel más alto) solo cuando fuere alto) solo cuando fuere necesario.necesario.

BB

CC EE

DD FF

GG

SS

AA

9

Algoritmo búsqueda primero en Algoritmo búsqueda primero en profundidad:profundidad:

1. 1. COLACOLA <-- camino que solo contiene la raiz; <-- camino que solo contiene la raiz;

2. 2. WHILEWHILE COLACOLA no vacía no vacía ANDAND objetivo no alcanzado objetivo no alcanzado

DODO remover el primer camino de la remover el primer camino de la COLACOLA;; crear nuevos caminos (a todos los hijos);crear nuevos caminos (a todos los hijos); rechazar los nuevos caminos con ciclos;rechazar los nuevos caminos con ciclos;

agregar al agregar al frentefrente de de COLA COLA los nuevoslos nuevos caminos;caminos;3. 3. IFIF objetivo alcanzado objetivo alcanzado THENTHEN éxito; éxito; ELSEELSE falla; falla;

10

AA

DD

BB

EE

CC

FFGGSS

33

44

44

44

55 55

44

3322

1. 1. COLACOLA <-- camino que solo contiene la <-- camino que solo contiene la raiz;raiz;2. 2. WHILEWHILE COLACOLA no vacía no vacía ANDAND objetivo no alcanzado objetivo no alcanzado DODO remover el primer camino de la remover el primer camino de la COLACOLA;; crear nuevos caminos (a todos los crear nuevos caminos (a todos los hijos);hijos); rechazar los nuevos caminos con rechazar los nuevos caminos con ciclos;ciclos;

agregar al agregar al frentefrente de de COLA COLA los los nuevosnuevos caminos;caminos;3. 3. IFIF objetivo alcanzado objetivo alcanzado THENTHEN éxito; éxito; ELSEELSE falla; falla;

11

Traza de depth-first Traza de depth-first para el ejemplo:para el ejemplo:

(S) (S) S removido, (SA,SD) computados y agregados S removido, (SA,SD) computados y agregados (SA, SD)(SA, SD) SA removido, (SAB,SAD,SAS) computados, SA removido, (SAB,SAD,SAS) computados,

(SAB,SAD) agregados(SAB,SAD) agregados (SAB,SAD,SD) (SAB,SAD,SD) SAB removido, (SABA,SABC,SABE) SAB removido, (SABA,SABC,SABE)

comput., comput., (SABC,SABE) agregados (SABC,SABE) agregados (SABC,SABE,SAD,SD) (SABC,SABE,SAD,SD) SABC removido, (SABCB) computados, SABC removido, (SABCB) computados,

nada agragadonada agragado (SABE,SAD,SD)(SABE,SAD,SD) SABE removido, (SABEB,SABED,SABEF) SABE removido, (SABEB,SABED,SABEF)

computados, computados, (SABED,SABEF)agragados(SABED,SABEF)agragados

(SABED,SABEF,SAD,SD) (SABED,SABEF,SAD,SD) SABED removido, SABED removido, (SABEDS,SABEDA.SABEDE) computados, (SABEDS,SABEDA.SABEDE) computados, nada agregadonada agregado

((SABEF,SAD,SD) SABEF,SAD,SD) SABEF removido, (SABEFE,SABEFG) SABEF removido, (SABEFE,SABEFG) computados, (SABEFG) computados, (SABEFG)

agregadoagregado (SABEFG,SAD,SD)(SABEFG,SAD,SD) objetivo alcanzado: reportar éxitoobjetivo alcanzado: reportar éxito

12

Criterios de evaluación:Criterios de evaluación: Completitud:Completitud:

¿El algoritmo siempre encuentra un camino?¿El algoritmo siempre encuentra un camino? (para toda RED en que al menos un camino exista)(para toda RED en que al menos un camino exista)

VelocidadVelocidad (complejidad de tiempo en las peores (complejidad de tiempo en las peores cond.)cond.) :: ¿Cuál es el máximo número de nodos que puede ser ¿Cuál es el máximo número de nodos que puede ser

necesario que sean creados?necesario que sean creados? MemoriaMemoria (complejidad de espacio en las peores cond.)(complejidad de espacio en las peores cond.) : :

¿Cuál es la máxima cantidad de nodos que puede ¿Cuál es la máxima cantidad de nodos que puede ser necesario almacenar?ser necesario almacenar?

Expresado en términos de: Expresado en términos de: d = profundidad del árbold = profundidad del árbol b = factor de ramific. (promedio) del árbolb = factor de ramific. (promedio) del árbol m = profundidad de la solución menos profunda m = profundidad de la solución menos profunda

13

Nota: aproximaciones !!Nota: aproximaciones !!

En nuestro análisis de complejidad, no tenemos En nuestro análisis de complejidad, no tenemos en cuenta la en cuenta la detección de ciclosdetección de ciclos . .

Los resultados solo se aplican ‘formalmente’ a las Los resultados solo se aplican ‘formalmente’ a las variantes de nuestros algoritmos variantes de nuestros algoritmos SINSIN verificación verificación de ciclos.de ciclos.

Estudiar el efecto de la detección de ciclos en la Estudiar el efecto de la detección de ciclos en la complejidad es dificultoso: complejidad es dificultoso: la recarga que implica esta verificación PUEDE o la recarga que implica esta verificación PUEDE o

NO ser compensada por la reducción de tamaño del NO ser compensada por la reducción de tamaño del árbol. árbol.

AdemásAdemás: nuestro análisis : nuestro análisis NONO toma en cuenta la toma en cuenta la longitud (espacio) de representación de caminos !!longitud (espacio) de representación de caminos !!

14

Completitud Completitud (depth-first)(depth-first)

Completo para REDES FINITAS.Completo para REDES FINITAS. (= REDES con número finito de nodos)(= REDES con número finito de nodos)

IMPORTANTE:IMPORTANTE: Esto is debido a la integración de LOOP-checking Esto is debido a la integración de LOOP-checking

en esta versión de Depth-First (y en todos los otros en esta versión de Depth-First (y en todos los otros algoritmos que se presentarán) !algoritmos que se presentarán) ! SI no removemos caminos con ciclos, entonces SI no removemos caminos con ciclos, entonces

Depth-First no es completo (puede quedar Depth-First no es completo (puede quedar atrapado en loops de una red finita)atrapado en loops de una red finita)

Nota:Nota: NO necesar. encuentra el camino más NO necesar. encuentra el camino más corto. corto.

15

AA

DD

BB

EE

CC

FFGGSS

33

44

44

55 55

44

3322

SSAA DD

BB DD EEAA

CC EE EE BB BB FF

DD FF BB FF CC EE AA CC GG

GG CC GG FF

GG

33

33 33

33

33

22

22

2244

44

4444

44

4444

44

44

44

44

44

5555

55 55

5555

16

Velocidad Velocidad (depth-first)(depth-first)

En el peor caso: En el peor caso: el (único) nodo objet. puede estar en la rama del el (único) nodo objet. puede estar en la rama del

extremo derecho, extremo derecho,

GG

ddbb

Complej. de tiempo == bComplej. de tiempo == bd d ++ bbd-1 d-1 + … + + … + 11 = = bbd+1 d+1 --11 Luego: O(bLuego: O(bdd) ) b - 1b - 1

17

Memoria Memoria (depth-first)(depth-first)

El número máximo de nodos en COLA se El número máximo de nodos en COLA se alcanza en el nodo del extremo izquierdo alcanza en el nodo del extremo izquierdo inferior.inferior.

Ejemplo: d = 3, b = 3 :Ejemplo: d = 3, b = 3 :

......

COLA contiene nodos . Es decir: 7.COLA contiene nodos . Es decir: 7. En General: ((b-1) * d) + 1En General: ((b-1) * d) + 1 Orden: O(d*b)Orden: O(d*b)

Búsqueda primero en amplitudBúsqueda primero en amplitud

Expande el árbol capa por capa, Expande el árbol capa por capa,

Avanzando en profundidad.Avanzando en profundidad.

19

Breadth-first search:Breadth-first search:

Moverse Moverse hacia abajo, hacia abajo, nivel por nivel por nivel, hasta nivel, hasta que el que el objetivo sea objetivo sea alcanzado.alcanzado.

SS

AA DD

BB DD AA EE

CC EE EE BB BB FF

DD FF BB FF CC EE AA CC GG

GG

GGGG FFCC

20

UNICA UNICA DIFERENCIA!DIFERENCIA!

Algoritmo prim.en amplitud:Algoritmo prim.en amplitud:

1. 1. COLACOLA <-- camino que solo contiene la raiz; <-- camino que solo contiene la raiz;

2. 2. WHILEWHILE COLACOLA no vacía no vacía ANDAND objetivo no alcanzado objetivo no alcanzado

DODO remover el primer camino de la remover el primer camino de la COLACOLA;; crear nuevos caminos (a todos los crear nuevos caminos (a todos los hijos);hijos); rechazar los caminos nuevos con ciclos;rechazar los caminos nuevos con ciclos; agregar los nuevos caminos al final de agregar los nuevos caminos al final de COLACOLA;;

3. 3. SISI objetivo alcanzado objetivo alcanzado THENTHEN éxito; éxito; ELSEELSE falla; falla;

21

Traza de breadth-first Traza de breadth-first en el ejemplo:en el ejemplo:

(S) (S) S removido, (SA,SD) computados y agregados S removido, (SA,SD) computados y agregados (SA, SD)(SA, SD) SA removido, (SAB,SAD,SAS) computados, SA removido, (SAB,SAD,SAS) computados,

(SAB,SAD) agregados(SAB,SAD) agregados (SD,SAB,SAD) (SD,SAB,SAD) SD removido, (SDA,SDE,SDS) computados, SD removido, (SDA,SDE,SDS) computados,

(SDA,SDE) agregados(SDA,SDE) agregados (SAB,SAD,SDA,SDE) (SAB,SAD,SDA,SDE) SAB removido, (SABA,SABE,SABC) SAB removido, (SABA,SABE,SABC)

computados, (SABE,SABC) agregadoscomputados, (SABE,SABC) agregados (SAD,SDA,SDE,SABE,SABC)(SAD,SDA,SDE,SABE,SABC) SAD removido, (SADS,SADA, SAD removido, (SADS,SADA,

SADE) computados, (SADE) agregadosSADE) computados, (SADE) agregados etc, hasta que COLA contiene:etc, hasta que COLA contiene:

(SABED,SABEF,SADEB,SADEF,SDABC,SDABE,SDEBA,SDEBC, (SABED,SABEF,SADEB,SADEF,SDABC,SDABE,SDEBA,SDEBC, SDEFG) SDEFG) el objetivo es alcanzado: reportar éxitoel objetivo es alcanzado: reportar éxito

22

Completitud Completitud (breadth-first)(breadth-first)

COMPLETACOMPLETA aún para REDES implícitamente infinitas!aún para REDES implícitamente infinitas!

Permanecería completa aún sin nuestro loop-Permanecería completa aún sin nuestro loop-checking.checking.

Nota:Nota: SIEMPRE encuentra el camino más corto. SIEMPRE encuentra el camino más corto.

23

Velocidad Velocidad (breadth-first)(breadth-first) Si un nodo objetivo es encontrado a profundidad Si un nodo objetivo es encontrado a profundidad mm del del

árbol, todos los nodos hasta esa profundidad son creados.árbol, todos los nodos hasta esa profundidad son creados.

ddGGbb

mm

LuegoLuego: O: O((bbmm) ) nota: depth-first podría haber visitado nodos más profundos.nota: depth-first podría haber visitado nodos más profundos.

24

Memoria Memoria (breadth-first)(breadth-first)

El mayor número de nodos en COLA se alcanza El mayor número de nodos en COLA se alcanza en el nivel en el nivel mm del nodo objetivo. del nodo objetivo.

GGddbb

mm

GG COLA contiene nodos y . COLA contiene nodos y . (Es decir: 4)(Es decir: 4) . . En General: bEn General: bmm

Esto es generalm. Esto es generalm. MUCHOMUCHO peor que depth-first !! peor que depth-first !!

25

Evaluación práctica:Evaluación práctica:

Depth-first:Depth-first:SI el espacio de búsqueda contiene ramas muy SI el espacio de búsqueda contiene ramas muy

profundas sin solución, ENTONCES Depth-first profundas sin solución, ENTONCES Depth-first puede desperdiciar mucho tiempo en ellas.puede desperdiciar mucho tiempo en ellas.

Breadth-first:Breadth-first: Demanda MUCHA memoria !Demanda MUCHA memoria !

¿ Soluciones ?¿ Soluciones ?Búsqueda No-determinísticaBúsqueda No-determinística Profundización iterativaProfundización iterativa

26

Búsqueda No-determinística:Búsqueda No-determinística:

1. 1. COLACOLA <-- camino que solo contiene la raiz; <-- camino que solo contiene la raiz;

2. 2. WHILEWHILE COLACOLA no vacía no vacía ANDAND objetivo no alcanzado objetivo no alcanzado

DODO remover el primer camino de la remover el primer camino de la COLACOLA;; crear nuevos caminos (a todos los hijos);crear nuevos caminos (a todos los hijos); rechazar los nuevos caminos con ciclos;rechazar los nuevos caminos con ciclos; agregar los nuevos cam. en lug. al azar en agregar los nuevos cam. en lug. al azar en COLACOLA;;

3. 3. IFIF objetivo alcanzado objetivo alcanzado THENTHEN exito; exito; ELSEELSE falla; falla;

27

Búsqueda por profundización Búsqueda por profundización iterativaiterativa

Restringe una búsqueda depth-first a una Restringe una búsqueda depth-first a una profundidad fija.profundidad fija.

Si no se encontró ningún camino, incrementar Si no se encontró ningún camino, incrementar la profundidad y recomenzar la búsqueda.la profundidad y recomenzar la búsqueda.

28

Depth-limited search:Depth-limited search:1. 1. DEPTHDEPTH <-- <algun número natural> <-- <algun número natural> COLA COLA <-- camino que solo contiene la raiz; <-- camino que solo contiene la raiz;

2. 2. WHILEWHILE COLACOLA no vacía no vacía ANDAND objetivo no alcanzado objetivo no alcanzado

DODO remover el primer camino de la remover el primer camino de la COLACOLA;; IFIF el camino tiene long.menor que el camino tiene long.menor que DEPTHDEPTH crear nuevos caminos(a todos los hijos);crear nuevos caminos(a todos los hijos); rechazar los nuevos caminos con ciclos;rechazar los nuevos caminos con ciclos; agregar los nuevos caminos al frente de agregar los nuevos caminos al frente de COLACOLA;;

3. 3. IFIF objetivo alcanzado objetivo alcanzado THENTHEN exito; exito; ELSEELSE falla; falla;

29

Algoritmo de profundización Algoritmo de profundización iterativa:iterativa:

1. 1. DEPTHDEPTH <-- 1 <-- 1 2. 2. WHILEWHILE objetivo no alcanzado objetivo no alcanzado

DODO ejecutar Depth-limited search; ejecutar Depth-limited search; incrementar en 1 incrementar en 1 DEPTHDEPTH;;

30

Profundización iterativa:Profundización iterativa:la mejor búsqueda ‘a ciegas’.la mejor búsqueda ‘a ciegas’.

Completa: si - incluso encuentra el camino más Completa: si - incluso encuentra el camino más corto corto (como primero en amplitud)(como primero en amplitud) . .

b - 1b - 1 bbm-1m-1 ++ bbm-2m-2 + … + + … + 11 = = bbmm --1 = O(b1 = O(bm-1m-1))

En general: MUY buen trade-offEn general: MUY buen trade-off

El trabajo realizado en El trabajo realizado en DEPTHDEPTH = = mm is O(b is O(bmm))

Memoria: b*Memoria: b*m m (combina ventajas de depth- y breadth-first)(combina ventajas de depth- y breadth-first) Velocidad:Velocidad:

Si se halla el camino a Si se halla el camino a DepthDepth = = mm, ¿cuánto tiempo se , ¿cuánto tiempo se desperdició en la construcc.de los árboles más pequeños?desperdició en la construcc.de los árboles más pequeños?

31

Búsqueda bi-direccional Búsqueda bi-direccional

Computa el árbol tanto desde el nodo de Computa el árbol tanto desde el nodo de comienzo como desde el nodo objetivo, hasta comienzo como desde el nodo objetivo, hasta que estos árboles se encuentran.que estos árboles se encuentran.

32

Búsqueda bi-direccional Búsqueda bi-direccional SISI podemos describir EXPLíCITAMENTE el estado podemos describir EXPLíCITAMENTE el estado

OBJETIVO, OBJETIVO, YY Contamos con reglas para razonamiento HACIA Contamos con reglas para razonamiento HACIA

ADELANTE Y HACIA ATRAS:ADELANTE Y HACIA ATRAS:

Objet.Objet.InicioInicio

33

Algoritmo bi-direccional:Algoritmo bi-direccional:

1. 1. COLA1COLA1 <-- camino que solo contiene la raiz; <-- camino que solo contiene la raiz; COLA2COLA2 <-- camino que solo contiene el objetivo; <-- camino que solo contiene el objetivo;

2. 2. WHILEWHILE ambas ambas COLAiCOLAi no estén vacías no estén vacías ANDAND COLA1COLA1 y y COLA2 COLA2 NO compartan un estado NO compartan un estado

DODO remover sus primeros caminos; remover sus primeros caminos; crear sus nuevos caminos (a todos los hijos);crear sus nuevos caminos (a todos los hijos); rechazar sus nuevos caminos con ciclos;rechazar sus nuevos caminos con ciclos; agregar sus nuevos caminos al final;agregar sus nuevos caminos al final;

3. 3. IFIF COLA1COLA1 y y COLA2 COLA2 comparten un estadocomparten un estado THENTHEN éxito; éxito; ELSEELSE falla; falla;

34

Propiedades Propiedades (Bi-direccional)(Bi-direccional)::

Completa: Si.Completa: Si.

Velocidad: Si la verificación de estado común Velocidad: Si la verificación de estado común se puede realizar en tiempo constante se puede realizar en tiempo constante (hashing):(hashing): 2 * O(b2 * O(bm/2m/2) = O(b) = O(bm/2m/2) )

Memoria: similar: O(bMemoria: similar: O(bm/2m/2))