Algoritmos busquedas

Análisis de Algoritmos

Programación dinámica(Dynamic Programming)

Modificado Modificado

por Leonardo Bernal Zamorapor Leonardo Bernal Zamora

Análisis deAlgoritmos Terminología Grafos

Monterrey

Reynosa

Tampico

Cd. VictoriaSaltillo

México DFARCOARCO

(carretera)(carretera)NODONODO(ciudad)(ciudad)

SUBGRAFOSUBGRAFO

Análisis deAlgoritmos

Terminología...

Monterrey

Reynosa

Tampico


México DF

AdyacentesAdyacentes


Terminología...

Monterrey

Reynosa

Tampico


México DF

Vecinos de Vecinos de Cd. VictoriaCd. Victoria


Terminología...

Monterrey

Reynosa

Tampico


México DF

CAMINOCAMINO


Terminología...

A

B

C

E

D

A

B

C

E

D

Grafo No-DirigidoGrafo No-Dirigido Grafo Dirigido (Digrafo)Grafo Dirigido (Digrafo)


Terminología...

Monterrey

Reynosa

Tampico


México DF

4532

21

9657

1319

GrafoGrafoPonderadoPonderado


Terminología...

Monterrey

Reynosa

Tampico


México DF

CicloCiclo


9

Ruta mas corta

Un grafo con pesos es un grafo en el cual se asignan valores a las aristas y que la longitud de un camino en un grafo con pesos es la suma de los pesos de las aristas en el camino. Con frecuencia se desea determinar la ruta mas corta entre dos vértices dados.

Los algoritmos más usados para este fin son:

DIJSKSTRA

FLOYD / WARSHALL


10

Algoritmo de Dijkstra• Suponemos que los pesos son números positivos.• Se desea determinar el camino mas corto de a hasta z.• El grafo es conexo.• Sea L(v) la etiqueta del vértice v.• En algún momento algunos vértices tienen etiquetas temporales y

otros permanentes.• Sea T el conjunto de tienen etiquetas temporales.• En principio todos los vértices tienen etiquetas temporales.• En cada iteración el algoritmo modifica el estado de una etiqueta de

temporal a permanente.• El algoritmo concluye cuando z recibe una etiqueta permanente, L(z)

proporciona la longitud mínima de a hasta z.• El peso de la arista (i,j) es w(i,j)

Análisis deAlgoritmosFuncion Dijkstra (L[1..n,1..n]):matriz[2..n]

D: matriz[2..n], P:matriz[2..n]C=2,3,...,n {S=N-C}

Para i=2 hasta nD[i]=L[1,i]

Fin_ParaRepetir n-2 veces

v=algún elemento de C que minimice D[v]C = C – {v} {S = S U {v}}Para cada w∈CSi D[w]>D[v]+L[v,w] entonces

D[w] = D[v] + L[v,w]P[w] = v

Fin_siFin_para

Fin_RepetirDevolver D

50

5

34

1

2

10 50

10 5

100 30

20

L 1 2 3 4 5

1 0 50 30 100 10

2 ∞ 0 ∞ ∞ ∞

3 ∞ 5 0 ∞ ∞

4 ∞ 20 50 0 ∞

5 ∞ ∞ ∞ 10 0D

2 3 4 5

P

2 3 4 5C S 1

5

v

5

w={2}D[2]>D[5]+L[5,2] Now={3}D[3]>D[5]+L[5,3] Now={4}D[4]>D[5]+L[5,4] SiD[4]=D[5]+L[5,4]D[4]=20P[4]=5

20

5

4

w={2}D[2]>D[4]+L[4,2] SiD[2]=40P[2]=4w={3}D[3]>D[4]+L[4,3] No

4

40

4

3

3

w={2}D[2]>D[3]+L[3,2] SiD[2]=35P[2]=3

35

3


Algoritmo de Floyd

• Propuesta basada en la técnica de la programación dinámica…

• Se basa en la representación del grafo en una matriz de adyacencias bajo las siguientes condiciones:– M[i,j] guarda el peso del arco del nodo i al nodo j.– M[i,j] guarda el valor 0 cuando i = j– M[i,j] guarda el valor ∞ cuando no hay arco entre

el nodo i y el nodo j.


Algoritmo de Floyd

• Dada la matriz de adyacencias, obtener la matriz del camino más corto en donde el elemento [i,j] es el valor del camino más corto para ir del nodo i al nodo j…

• El algoritmo también se puede utilizar para mostrar el camino más corto (no sólo el valor)…

• Este algoritmo tiene un comportamiento de orden O(nO(n33)).


Ejemplo

MATRIZ DE ADYACENCIAS

A B C D EA 0 2 ∞ 10 ∞B ∞ 0 9 ∞ 5C 12 ∞ 0 6 ∞D ∞ ∞ ∞ 0 7E ∞ ∞ 3 ∞ 07

A B

C

D E

2

59

310

12

6


Ejemplo

MATRIZ DEL CAMINO MÁS CORTO

A B C D EA 0 2 10 10 7B 20 0 8 14 5C 12 14 0 6 13D 22 24 10 0 7E 15 17 3 9 07

A B

C

D E

2

59

310

12

6


Algoritmo de Floyd

• Sea Dk una matriz del camino más corto, en donde cada elemento [i,j] indica:– Cuál es el camino más corto desde el nodo i hasta el nodo j,– Pasando solamente por los nodos desde 1 hasta k…

• D0 es la matriz con los caminos más cortos sin pasar por otros vértices…– Por lo tanto, es la matriz de adyacencias original.

• Dn será la matriz con los caminos más cortos pasando por TODOS los nodos posibles…– ESTA ES LA MATRIZ QUE SE BUSCA.


Algoritmo de Floyd

• ¿Cómo obtener a la matriz Dn dada la matriz D0?• El enfoque de la PROGRAMACIÓN DINÁMICA

preguntaría si:– A partir de la matriz D0 se puede obtener D1…– Si obteniendo a D1, se puede obtener a D2…– Y así sucesivamente hasta obtener a Dn, que es lo

que buscamos.


Algoritmo de Floyd

• Se debe escoger el mínimo de 2 caminos:– El que no incluye al nodo k, o– El que sí incluye al nodo k.

i jDk-1 [i, j]

kD

k-1 [k, j]Dk-

1 [i, k

]


Ejemplo

D0 A 1 B 2 C 3 D 4 E 5A 1 0 2 ∞ 10 ∞B 2 ∞ 0 9 ∞ 5C 3 12 ∞ 0 6 ∞D 4 ∞ ∞ ∞ 0 7E 5 ∞ ∞ 3 ∞ 0

D1 A 1 B 2 C 3 D 4 E 5A 1 0 2 ∞ 10 ∞B 2 ∞ 0 9 ∞ 5C 3 12 1414 0 66 ∞D 4 ∞ ∞ ∞ 0 7E 5 ∞ ∞ 3 ∞ 0

C-A + A-B = 12 + 2

Mínimo entre:C-D y C-A + A-D

7

A B

C

D E

2

59

310

12

6

Nota : si existe un valor y la sumatoria es indefinida Se deja el valor que se encuentre, y si es superior la suma se deja el mínimo


Ejemplo

D1 A 1 B 2 C 3 D 4 E 5A 1 0 2 ∞ 10 ∞B 2 ∞ 0 9 ∞ 5C 3 12 14 0 6 ∞D 4 ∞ ∞ ∞ 0 7E 5 ∞ ∞ 3 ∞ 0

D2 A 1 B 2 C 3 D 4 E 5A 1 0 2 1111 10 77B 2 ∞ 0 9 ∞ 5C 3 12 14 0 66 1919D 4 ∞ ∞ ∞ 0 7E 5 ∞ ∞ 3 ∞ 0

A-B + B-C = 2 + 9

A-B + B-E = 2 + 5

Mínimo entre:C-D y C-B + B-D

C-B + B-E = 14 + 5

7

A B

C

D E

2

59

310

12

6


Ejemplo

D3 A 1 B 2 C 3 D 4 E 5A 1 0 2 11 1010 77B 2 2121 0 9 1515 5C 3 12 14 0 6 19D 4 ∞ ∞ ∞ 0 7E 5 1515 1717 3 99 0

D2 A 1 B 2 C 3 D 4 E 5A 1 0 2 11 10 7B 2 ∞ 0 9 ∞ 5C 3 12 14 0 6 19D 4 ∞ ∞ ∞ 0 7E 5 ∞ ∞ 3 ∞ 0

E-C + C-A = 3 + 12

B-C + C-A = 9 + 12

Mínimo entre:A-E y A-C + C-E

Mínimo entre:A-D y A-C + C-D

7

A B

C

D E

2

59

310

12

6


Ejemplo

D4 A 1 B 2 C 3 D 4 E 5A 1 0 2 11 10 77B 2 21 0 9 15 5C 3 12 14 0 6 1313D 4 ∞ ∞ ∞ 0 7E 5 15 17 3 9 0

D3 A 1 B 2 C 3 D 4 E 5A 1 0 2 11 10 7B 2 21 0 9 15 5C 3 12 14 0 6 19D 4 ∞ ∞ ∞ 0 7E 5 15 17 3 9 0

Mínimo entre:C-E y C-D + D-E

Mínimo entre:A-E y A-D + D-E

7

A B

C

D E

2

59

310

12

6


Ejemplo

D4 A 1 B 2 C 3 D 4 E 5A 1 0 2 11 10 7B 2 21 0 9 15 5C 3 12 14 0 6 13D 4 ∞ ∞ ∞ 0 7E 5 15 17 3 9 0

Mínimo entre:B-A y B-E + E-A

Mínimo entre:A-C y A-E + E-C

D-E + E-A = 7 + 15

D5 A 1 B 2 C 3 D 4 E 5A 1 0 2 1010 10 7B 2 2020 0 88 1414 5C 3 12 14 0 6 13D 4 2222 2424 1010 0 7E 5 15 17 3 9 0

MATRIZ META

7

A B

C

D E

2

59

310

12

6


Algoritmo de Floyd

• Generalizando…

Dk[i,j] = minimo(Dk-1[i,j] , Dk-1[i,k] + Dk-1[k,j])

• Esta relación recursiva, es el planteamiento de solución al problema…

• La técnica de la programación dinámica, sugiere que se obtenga el caso más pequeño y a partir de ese, se construyan los casos superiores, almacenando resultados si se requieren...


Algoritmo de Floyd

• Por lo tanto, el algoritmo se puede plantear de la siguiente manera…

D = matriz de adyacencias

for k = 1 to n do

for i = 1 to n do

for j = 1 to n do

D[i,j] = minimo(D[i,j], D[i,k]+D[k,j]);


Algoritmo de Floyd

• ¿Porqué se puede usar una sola matriz y NO se requieren ‘n’ matrices intermedias?

• Los valores de la k-ésima columna y el k-ésimo renglón NO cambian en la k-ésima iteración…– D[i,k] = minimo(D[i,k], D[i,k]+D[k,k]) = D[i,k]– D[k,j] = minimo(D[k,j], D[k,j]+D[k,k]) = D[k,j]

• Puesto que D[i,j] en la k-ésima iteración se calcula con su propio valor previo y los de la k-ésima columna y el k-ésimo renglón que se mantienen de la iteración anterior, NO HAY PROBLEMA en usar la propia matriz...


Algoritmo de Floyd

• ¿Cómo encontrar los nodos que conforman el camino más corto?

• Almacenar en una matriz auxiliar, el índice más grande del nodo intermedio por el que se pasa en el camino más corto del nodo i al nodo j.

• Utilizando esa matriz, si para ir del nodo i al nodo j se pasa por el nodo k, entonces se pasa también por el nodo con el índice más grande del camino más corto del nodo i al nodo k, y del nodo k al nodo j...


Algoritmo de Floyd

• Para obtener la matriz con el último nodo visitado en el camino más corto…D = matriz de adyacencias

P = matriz de último nodo inicializada en ceros.

for k = 1 to n do

for i = 1 to n do

for j = 1 to n do

if (D[i,k]+D[k,j] < D[i,j]) then

P[i,j] = k;

D[i,j] = D[i,k]+D[k,j];


Algoritmo de Floyd

• Para desplegar el camino más corto…

Modulo camino (inicio, fin)

if (P[inicio, fin] <> 0) then

camino(inicio, P[inicio,fin]);

write(P[inicio,fin]);

camino(P[inicio,fin], fin);

• Recordar que P[inicio, fin] es el nodo intermedio con el índice más grande en el camino más corto de inicio a fin.


Ejemplo

5

1 2

4 3

35

34

2

2

1

9

31

1 2 3 4 52 0 1 3 1 43 8 0 3 2 54 10 11 0 4 75 6 7 2 0 36 3 4 6 4 0

D5

1 2 3 4 52 0 0 4 0 43 5 0 0 0 44 5 5 0 0 45 5 5 0 0 06 0 1 4 1 0

P

Modulo camino (inicio, fin)if (P[inicio, fin] <> 0) then camino(inicio, P[inicio,fin]); write(P[inicio,fin]); camino(P[inicio,fin], fin);

Análisis deAlgoritmos El principio de

optimalidad

• Todo problema de optimización, se puede resolver con la técnica de la programación dinámica, si la solución cumple con el principio de optimalidadprincipio de optimalidad…

• La solución óptima de la instancia de un problema siempre contiene las soluciones óptimas de todas las subinstancias que conforman la solución...

• Ejemplos: Camino más corto vs. más largo...


32

ARBOL GENERADOR

• Definición.- Sea G un grafo, un árbol generador de G es un subgrafo

conexo de G que tiene los mismos vértices que G y no tiene circuitos.


33

ARBOL GENERADOR

• Supongamos que a cada arista se le asocia un número positivo (su peso). Un árbol generador se dice de peso mínimo si la suma de los pesos de las aristas que lo componen es lo menor posible

• Para calcular el árbol de peso mínimo existen 2 algoritmos:

– Prim: Consiste en ir borrando las aristas de mayor peso posible y que no sean aristas de separación.

– Kruskal: Se van escogiendo las aristas de menor peso hasta conseguir un árbol de peso mínimo

• Puede haber más de un árbol generador de peso mínimo, pero todos deben tener el mismo peso.


34

ALGORITMO DE PRIM

La idea básica consiste en añadir, en cada paso, una arista de peso mínimo a un árbol previamente construido. Más explícitamente:

Paso 1. Se elige un vértice u de G y se considera el árbol S={u}

Paso 2. Se considera la arista e de mínimo peso que une un vértice de S y un vértice que no es de S, y se hace S=S+e

Paso 3. Si el nº de aristas de T es n-1 el algoritmo termina. En caso contrario se vuelve al paso 2


35

ALGORITMO DE PRIM


36

ALGORITMO DE PRIM


Marco Teórico

• El algoritmo incrementa continuamente el tamaño de un árbol, comenzando por un vértice inicial al que se le van agregando sucesivamente vértices cuya distancia a los anteriores es mínima. Esto significa que en cada paso, las aristas a considerar son aquellas que inciden en vértices que ya pertenecen al árbol.

• El árbol recubridor mínimo está completamente construido cuando no quedan más vértices por agregar.


Objetivo Algoritmo

–Encontrar el árbol recubridor mas corto

RequisitosRequisitos

Ser un grafo conexo Ser un grafo sin ciclos Tener todos los arcos etiquetados.


Ejemplo


45

ALGORITMO DE KRUSKAL • La idea básica consiste en elegir sucesivamente las aristas de mínimo

peso sin formar ciclos.

• Paso 1. Se elige la arista de mínimo peso e y se considera S={e}.

• Paso 2. Sea e’ la arista de mínimo peso tal que e’ÏS y S+e' es un grafo acíclico. Se hace S=S+e'.

• Paso 3. Si S tiene n-1 aristas, el algoritmo termina. En caso contrario se vuelve al paso 2.


46

ALGORITMO DE KRUSKAL


47

ALGORITMO DE KRUSKAL

http://lear.inforg.uniovi.es/ioperativa/TutorialGrafos/minimaexp/kruskal/appletKruskal.htm


¿Cómo funciona?• Se elige un punto de partida teniendo en cuenta la arista de menor peso.• Se marca la arista con menor valor. Si hay más de una, se elige cualquiera de ellas. • De las aristas restantes, se marca la que tenga menor valor, si hay más de una, se elige cualquiera

de ellas. • Repetir el paso 2 siempre que la arista elegida no forme un ciclo con las ya marcadas. • El proceso termina cuando tenemos todos los nodos del grafo en alguna de las aristas marcadas, es

decir, cuando tenemos marcados n-1 arcos, siendo n el número de nodos del grafo.

1 2

3

4

5 6

7

1

1

3

8

7

5 6

9

42


¿Para qué sirve

• Con este planteamiento se pueden resolver problemas tales como obtener una red arborescente óptima de interconexión entre un conjunto de ciudades dado, o agrupar este conjunto en subconjuntos de ciudades próximas entre sí.

• Optimizar rutas.(árbol)• MST (Árbol de Expansión Mínima )• sirve para solucionar problemas relaciones con

distribución de redes de energía, redes de comunicaciones y demás problemas donde se pueda llevar este a un modelo de grafos


Ejercicio

Dado un Grafo Conexo Ponderado No Dirigido G = (V, A, p), encontrar un Árbol de Recubrimiento de G, tal que la suma de los pesos de sus |V| − 1 aristas sea mínimo.

Desarrollo

Solución tomando “e” como Punto de parida


Webgrafia

• 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

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

Algoritmos busquedas

Documents

Transcript of Algoritmos busquedas