busquedas en arboles

Búsquedas Búsquedas Arboles y GrafosArboles y Grafos

Modificado y Adaptado:

Leonardo Bernal Zamora Asignatura Inteligencia Artificial Universidad de Boyacá.

2

Definición de ÁrbolDefinición de Árbol

Un árbol dirigido es una estructura:

3

Representación de un Árbol.Representación de un Árbol.

Mediante diagramas de Venn

Mediante círculos y flechas

Mediante paréntesis anidados:( a ( b (e,f), c, d ) )

a

b c de

fa

c db

e f

4

Conceptos Básicos Conceptos Básicos Si hay un camino de A hasta B, se dice que A es

antecesor de B, y que B es sucesor de A. Padre es el antecesor inmediato de un nodo Hijo, cualquiera de sus desc}ientes inmediatos. Descendiente de un nodo, es cualquier sucesor de

dicho nodo. Hermano de un nodo, es otro nodo con el mismo

padre. Generación, es un conjunto de nodos con la misma

profundidad.

5

Conceptos Básicos (cont.)Conceptos Básicos (cont.)

Raíz es el nodo que no tiene ningún predecesor (sin padre).

Hoja es el nodo que no tiene sucesores (sin hijos) (Terminal). Los que tienen predecesor y sucesor se llaman nodos interiores.

Rama es cualquier camino del árbol. Bosque es un conjunto de árboles desconectados. Nivel o profundidad de un nodo, es la longitud del

camino desde la raíz hasta ese nodo.El nivel puede de}irse como 0 para la raíz y nivel (predecesor)+1 para los demás nodos.

6

Conceptos Básicos (cont.)Conceptos Básicos (cont.)

Los nodos de la misma generación tienen el mismo nivel. Grado de un nodo, es el número de flechas que salen

de ese nodo (hijos). El número de las que entran siempre es uno.

Grado de un árbol, es el mayor grado que puede hallarse en sus nodos.

Longitud del camino entre 2 nodos: es el número de arcos que hay entre ellos.

Conceptos BásicosConceptos Básicos

R a ízh ijo

H e r m a n o

P a d r e

h o ja

S u b á r b o l

= 7N iv e l d e p r o f u n d id a d = 3G r a d o d e u n n o d o = 3G r a d o d e l á r b o l

El modo evidente de moverse a través de las ramas de un árbol es siguiendo los punteros de los nodos, del mismo modo en que nos movíamos a través de las listas.

Esos recorridos dependen en gran medida del tipo y propósito del árbol, pero hay ciertos recorridos que usaremos frecuentemente.

Hay tres formas de recorrer un árbol completo, y las tres se pueden implementar mediante recursividad. En los tres casos se sigue siempre a partir de cada nodo todas las ramas una por una.

Recorridos por árboles:

A B E K F D H J N O

30

15 47

10 44 51

40 4613

Realice el recorrido para el Realice el recorrido para el siguiente Árbolsiguiente Árbol

12

Recorridos de un árbol de Búsqueda Recorridos de un árbol de Búsqueda Binaria (ABB)Binaria (ABB)

30

15 47

10 44 51

40 4613

Preorden = 30 15 10 13 47 44 40 46 51

Inorden = 10 13 15 30 40 44 46 47 51

Postorden = 13 10 15 40 46 44 51 47 30

Reconstrucción de un árbol binario a Reconstrucción de un árbol binario a partir de sus recorridospartir de sus recorridos

Si un árbol binario no tiene elementos repetidos, es posible reconstruirlo a partir de las secuencias de vértices producidas por dos de sus recorridos (preorden e inorden o postorden e inorden).

Encontrar la raíz, que siempre es el primer elemento del recorrido en preorden, y localizarla en el recorrido en inorden.

Conociendo el número de nodos de cada uno de los subárboles, que se determina por la longitud de las dos subsecuencias obtenidas en el paso anterior, puede extraerse del recorrido en preorden del árbol originar, los recorridos en preorden de los subárboles.

Repetir los pasos 1 y 2 con cada uno de los subárboles encontrados

Método de resolución de problemasMétodo de resolución de problemas

Sistemas de resolución de problemas en IA, están basados en búsqueda.

Se comienza en un estado inicial y la meta es llegar a un estado final u objetivo

El proceso de evaluación de las alternativas para llegar desde el estado inicial al objetivo se designa como búsqueda

El conjunto de pasos posibles para llegar desde un estado inicial al objetivo, es llamado el espacio de búsqueda.

Método de resolución de problemas...Método de resolución de problemas...

Las principales diferencias que pueden aparecer en las diferentes técnicas de búsqueda, son:◦ La dirección en la cual se conduce la búsqueda (hacia

adelante o hacia atrás). ◦ La estrategia de control, o forma de seleccionar las

reglas que pueden ser aplicables. Los principales requerimientos de una buena estrategia de control son: que cause desplazamiento en el espacio de estado; y, que sea sistemático.

◦ La forma de representar cada nodo del proceso de búsqueda (representación del conocimiento).

Método de resolución de problemas...Método de resolución de problemas...

Muchas veces, tratar el proceso como búsqueda en un grafo en lugar de una búsqueda en un árbol, puede reducir el esfuerzo que se gasta en explorar senderos, esencialmente iguales, varias veces. Sin embargo, los requisitos asociados, son: ◦ Cada vez que se genere un nodo se debe chequear para

ver si ha sido generado antes. ◦ Se deben introducir procedimientos especiales para que

la búsqueda no quede atrapada en algún lazo.

DFS (Depth Firts Search )DFS (Depth Firts Search )

En la búsqueda "primero en profundidad" o "Depth First" se selecciona un nodo del primer nivel, descendiendo por alguna de las ramas que nacen de este nivel y que nos llevan al siguiente nivel, así sucesivamente hasta llegar a un nodo terminal.

Si se llega a un estado terminal sin satisfacer nuestro objetivo, se vuelve al estado inicial y se elige otro camino hasta llegar a un nuevo nodo terminal.

Este tipo de búsqueda es más eficiente que la búsqueda en anchura, si el espacio de búsqueda tiene muchos niveles.

Búsqueda DEPTH FIRST...Búsqueda DEPTH FIRST...

Este árbol es recorrido de la siguiente forma:

A,B,D,G,C,F,E

Database

Vuelo(symbol,symbol,integer)

Clauses

vuelo(santiago,la_serena,474).

vuelo(santiago,antofagasta,1361).

vuelo(santiago,arica,2062).

vuelo(santiago,calama,1574).

vuelo(santiago,copiapó,801).

vuelo(la_serena,copiapó,333).

vuelo(la_serena,chañaral,497).

vuelo(chañaral,copiapó,167).

vuelo(copiapó,el_salvador,282).

vuelo(antofagasta,tocopilla,188).

vuelo(arica,iquique,316).

vuelo(arica,calama,614).

vuelo(arica,copiapó1261).

%Ejemplo de Búsqueda en ProfundidadClauses encuentra_ruta:- write(" Desde : "),readln(A), write(" con Destino a: "), readln(B),hay_vuelo(A,B,D), write("La distancia es:

",D),nl,not(muestra_ruta). % Ver si hay conexión entre dos ciudades con ruta directa hay_vuelo(C1,C2,D):-vuelo(C1,C2,D),agrega_a_ruta(C1). % Búsqueda en Profundidad hay_vuelo(C1,C2,D):- vuelo(C1,X,D2), agrega_a_ruta(C1), hay_vuelo(X,C2,D3), D=D2+D3. % Indica si llegó a punto sin destino hay_vuelo(C1,_,D):-write(" Punto muerto en ",C1),nl,D=0,fail.

agrega_a_ruta(C):-not(visitada(C)),assert(visitada(C)),!. agrega_a_ruta(_).

muestra_ruta:- write(" La ruta es "),nl, visitada(A),write(A),nl,fail,!.

BFS (Bread First Search)BFS (Bread First Search)

En la búsqueda "primero en anchura" o "Breadth First" se evalúa cada nodo en un determinado nivel antes de pasar al siguiente.

Si en alguno de los niveles se satisface el objetivo final la búsqueda se da por finalizada.

Este tipo de búsqueda no resulta ser práctica cuando para alcanzar el estado final se deben recorrer muchos niveles.

Búsqueda BREADTH FIRST Búsqueda BREADTH FIRST

Este árbol es recorrido de la siguiente forma:

A,B,C,D,G,F,E

% Ejemplo de Búsqueda en Anchura% Ruta directahay_vuelo(C1,C2,D):-vuelo(C1,C2,D),

agrega_a_ruta(C1). % hacer primero en anchura hay_vuelo(C,C2,D):-vuelo(C,X,D2),

vuelo(X,C2,D3), agrega_a_ruta(C), agrega_a_ruta(X), D=D2+D3. hay_vuelo(C,C2,D):- vuelo(C,X,D2), X<>C2,

agrega_a_ruta(C),hay_vuelo(X,C2,D3), D=D2+D3.

hay_vuelo(C1,_,D):- write("Punto muerto en ",C1), nl,D=0,fail.

Búsqueda HeurísticaBúsqueda Heurística Las técnicas de búsqueda descritas anteriormente no

reflejan ningún tipo de conducta inteligente, son búsquedas ciegas.

Para espacios de búsquedas más grandes y complejos, se requiere utilizar técnicas de búsquedas inteligentes, que sean capaces de reducir en forma eficiente el espacio de búsqueda.

Estas técnicas están basadas en la utilización de la heurística, es decir, utilizan la experiencia humana que ante determinadas situaciones es capaz de intuir caminos de solución, alternativas prometedoras, rechazar vías de exploración, reduciendo así el espacio de búsqueda.

Búsqueda Heurística...Búsqueda Heurística... "Una heurística es un tipo de estrategia que

limita en forma drástica la búsqueda de soluciones. La heurística no garantiza soluciones óptimas; de hecho, no garantiza el que haya una solución; todo lo que se puede decir para que una heurística sea útil es que ofrece soluciones que son suficientemente buenas la mayoría de las veces." (Feigenbaum y Feldman, citado en Mishkoff, 1988)

% Ejemplo de Búsqueda Heurística Remonte de Colinahay_vuelo(T,T2,D):-vuelo(T,T2,D),agrega_a_ruta(T). % hacer primero en anchurahay_vuelo(T,T2,D):-encontrar_mas_grande(T,X),

agrega_a_ruta(T),vuelo(T,X,D2),hay_vuelo(X,T2,D3), D=D2+D3.

hay_vuelo(T,T2,D):- vuelo(T,X,D2), X<>T2,agrega_a_ruta(T),hay_vuelo(X,T2,D3), D=D2+D3.

hay_vuelo(C1,_,D):- write(" Punto muerto en ",C1),nl,D=0,fail.

encontrar_mas_grande(A,B):- vuelo(A,X,D),vuelo(A,Y,D2),X<>Y, D2>D, B=Y.

% Ejemplo de Búsqueda Heurística Menor Coste

hay_vuelo(T,T2,D):-vuelo(T,T2,D),agrega_a_ruta(T). % hacer primero en anchurahay_vuelo(T,T2,D):- encontrar_mas_corta(T,X),

agrega_a_ruta(T),vuelo(T,X,D2), hay_vuelo(X,T2,D3), D=D2+D3.

hay_vuelo(T,T2,D):- vuelo(T,X,D2), X<>T2, agrega_a_ruta(T),hay_vuelo(X,T2,D3), D=D2+D3.

hay_vuelo(C1,_,D):- write(" Punto muerto en",C1), nl,D=0,fail.

encontrar_mas_corta(A,B):-vuelo(A,X,D),vuelo(A,Y,D2), X<>Y, D>D2, B=Y.

Recorridos sobre grafos.Recorridos sobre grafos. El recorrido puede ser tanto para grafos dirigidos

como no dirigidos. Es necesario llevar una cuenta de los nodos

visitados y no visitados.

varmarca: array [1, ..., n] de (visitado,

noVisitado)

operación BorraMarcaspara i:= 1, ..., n hacer

marca[i]:= noVisitado ..

31 Tema 4. Grafos.

Recorridos sobre grafos.Recorridos sobre grafos.

Búsqueda primero en Búsqueda primero en profundidad.profundidad.

Búsqueda primero en profundidad.Búsqueda primero en profundidad.

Muchos algoritmos de grafos necesitan visitar de un modo sistemático todos los vértices de un grafo. En la búsqueda en profundidad se avanza de vértice en vértice, marcando cada vértice visitado. La búsqueda siempre avanza hacia un vértice no marcado, internándose “profundamente” en el grafo sin repetir ningún vértice. Cuando se alcanza un vértice cuyos vecinos han sido marcados, se retrocede al anterior vértice visitado y se avanza desde éste.


..

34 Tema 4. Grafos.

operación bpp (v: nodo)marca[v]:= visitadopara cada nodo w adyacente a v hacer si marca[w] == noVisitado entonces

bpp(w)finpara

operación BúsquedaPrimeroEnProfundidadBorraMarcaspara v:= 1, ..., n hacer

si marca[v] == noVisitado entoncesbpp(v)

finpara


..

35 Tema 4. Grafos.

• El recorrido no es único: depende del nodo inicial y del orden de visita de los adyacentes.

• El orden de visita de unos nodos a partir de otros puede ser visto como un árbol: árbol de expansión en profundidad asociado al grafo.

• Si aparecen varios árboles: bosque de expansión en profundidad.

• Ejemplo.Grafonodirigido.

1 2

36

8

7

4

95


..

36 Tema 4. Grafos.

• Arcos no del árbol: si marca[v] == noVisitado ... se detectan cuando la condición es falsa. +

• Bosque de expansión en profundidad

1

2

3

6

8

7

4

9

5

1º

2º

4º

3º 6º

5º

8º

7º

9º

Arcos del árbol

Arcos no del árbol

Ejemplo.Grafonodirigido

Bús queda primero en:profundidad

Equivalente al recorrido en preorden de un árbol.


¿Cuánto es el tiempo de ejecución de la BPP? Imposible predecir las llamadas en cada ejecución. Solución: medir el “trabajo total realizado”. - ..

38 Tema 4. Grafos.

Bosque de expansión

b c

ed

a

1º 2º

4º

3º

5º

Arco de avance

Arco de retrocesoArco de

cruce

• Ejemplo: Grafo dirigido.

a b

c

e

d

Recorridos sobre grafos.Recorridos sobre grafos.

Búsqueda primero enBúsqueda primero enAnchura o Amplitud.Anchura o Amplitud.

La búsqueda en anchura es otro procedimiento para visitar sistemáticamente todos los vértices de un grafo. Es adecuado especialmente para resolver problemas de optimización, en los que se deba elegir la mejor solución entre varias posibles. Al igual que en la búsqueda en profundidad se comienza en un vértice v (la raíz) que es el primer vértice activo. En el siguiente paso se etiquetan como visitados todos los vecinos del vértice activo que no han sido etiquetados. Se continúa etiquetando todos los vecinos de los hijos de v (que no hayan sido visitados aún). En este proceso nunca se visita un vértice dos veces por lo que se construye un grafo sin ciclos, que será un árbol generador de la componente conexa que contiene a v.

Búsqueda primero en anchura (o amplitud).Búsqueda primero en anchura (o amplitud).

Búsqueda primero en anchura (o amplitud).Búsqueda primero en anchura (o amplitud). Búsqueda en anchura empezando en un nodo

v:◦ Primero se visita v.◦ Luego se visitan todos sus adyacentes.◦ Luego los adyacentes de estos y así sucesivamente.

El algoritmo utiliza una cola de vértices. Operaciones básicas:

◦ Sacar un nodo de la cola.◦ Añadir a la cola sus adyacentes no visitados.

operación BúsquedaPrimeroEnAnchuraBorraMarcaspara v:= 1, ..., n hacer

si marca[v] == noVisitado entonces bpa(v)

..

41 Tema 4. Grafos.

Búsqueda primero en anchura (o amplitud).Búsqueda primero en anchura (o amplitud).operación bpa (v: Nodo)var C: Cola[Nodo] x, y: Nodo

marca[v]:= visitadoInsertaCola (v, C)mientras NOT EsVacíaCola (C) hacer x:= FrenteCola (C) SuprimirCola (C) para cada nodo y adyacente a x hacer si marca[y] == noVisitado entonces

marca[y]:= visitado InsertaCola (y, C) finsi

finparafinmientras

..

42 Tema 4. Grafos.


..

43 Tema 4. Grafos.

• Ejemplo.Grafo nodirigido.

1 2

37

8

6

4

95

• Bosque de expansión en anchura.

1

2 3

7

8

6

4

95

Arcos de cruce

1º

2º

4º

3º

6º

5º

8º

7º

9º

+

• Ejemplo.Grafo nodirigido.

Bús queda primero :en anchura

Equivalente al recorrido de un árbol por niveles


¿Cuánto es el tiempo de ejecución de la BPA? ¿Cómo comprobar si un arco es de avance, cruce, etc.? Solución: Construir el bosque explícitamente. ..

45 Tema 4. Grafos.

Bosque de expansión

b c

ed

a

• Ejemplo: Grafo dirigido.

1º 2º

4º3º

5º

a b

c e

d

Recorridos sobre grafos.Recorridos sobre grafos. Construcción explícita del bosque de expansión: Usamos

una estructura de punteros al padre.marca: array [1, ..., n] de entero

marca[v] vale: -1 si v no está visitado0 si está visitado y es raíz de un árbolEn otro caso indicará cual es el padre de v

Modificar BorraMarcas, bpp y bpa, para construir el bosque de expansión.◦ Arco de avance <v, w>: w es hijo de v en uno de los árboles

del bosque.◦ Arco de retroceso <v, w>: v es hijo de w.◦ Arco de cruce <v, w>: si no se cumple ninguna de las

anteriores. ..

46 Tema 4. Grafos.

WebgrafiaWebgrafia http://www.google.com.co/search?hl=es&q=ejemplo+de+busqueda+en+profundidad+para+grafos&btnG=Buscar&meta=lr%3Dlang_es http://docencia.udea.edu.co/regionalizacion/teoriaderedes/profundidad.html http://www.algoritmia.net/articles.php?id=18

UNIVERSIDAD DE CARABOBO_ FACULTAD EXPERIMENTAL DE CIENCIAS Y TECNOLOGÍA.DEPARTAMENTO DE COMPUTACIÓN.CS218 ALGORITMOS Y PROGRAMACIÓN II- TEMA 7 ESTRUCTURAS JERÁRQUICAS: ÁRBOLES

http://www.google.com.co/search?hl=es&q=ejemplo+de+busqueda+en+profundidad+para+grafos&btnG=Buscar&meta=lr=lang_es

http://docencia.udea.edu.co/regionalizacion/teoriaderedes/profundidad.html

http://www.algoritmia.net/articles.php?id=18

busquedas en arboles

Documents