Busquedas_ortega Canul Jonathan Aldair Ortega Canul.docx

TECNOLÓGICO NACIONAL DE MÉXICO

Instituto Tecnológico Superior de Valladolid Alumno: Jonathan Aldair Ortega Canul.

Número de matrícula: 18070037

Asignatura: Matemáticas Discretas.

Docente: M.M Jorge Manuel Pool Cen.

Actividad: Busquedas.

Fecha: 19-noviembre-2018

TECNOLÓGICO NACIONAL DE MÉXICO

Iteración 1

Iteración 5

T = {a, b, c, d, e, f, g, h, i, j, z}

T= {d, e, f, g, i, j, z}

V=a L(a)=0

V= e L(e)=5

L(b)= min {∞, 0 + 3} = 3

L(f)= min {7, 5 + 4} = 7

L(e)= min {∞, 0 + 5} = 5

Iteración 6

L(h)= min {∞, 0 + 4} = 4

T = {d, f, g, i, j, z}

Iteración 2 T= {b, c, d, e, f, g, h, i, j, z} V= b L(b)=3 L(c)= min {∞, 3 + 2} = 5 L(e)= min {5, 3 + 5} = 5

V= i L(i)=6 L(f)= min {7, 6 + 4} = 7 L(j)= min {∞, 6 + 6} = 12 Iteración 7

L(f)= min {∞, 3 + 7} = 10

T= {d, f, g, j, z}

Iteración 3

V= f L(f)= 7

T= { c, d, e, f, g, h, i, j, z}

L(g)= min {11, 7 + 4} = 11

V=h L(h) =4

L(j)= min {12, 7 + 3} = 10

L(e)= min {5, 4 + 7} = 5

Iteración 8

L(i)= min {∞, 4 + 2} = 6

T= {d, g, j, z}

L(f)= min {10, 4 + 5} = 9 Iteración 4 T= {c, d, e, f, g, i, j, z} V= c L(c)= 5 L(d)= min {∞, 5 + 3} = 8 L(f)= min {9, 5 + 2} = 7 L(g)= min {∞, 5 + 6} = 11

V= d L(d)= 8 L(g)= min {11, 8 + 7} = 11 L(z)= min {∞, 8 + 2} = 10 Iteración 9 T= {g, j, z}

V= j L(j)= 10

L(g)= min {11, 10 + 4} = 11 L(z)= min {10, 10 + 5} = 10

TECNOLÓGICO NACIONAL DE MÉXICO

Iteración 10

Iteración 4

T= {g, z}

T= {d, e, f, g, i, j, z}

V=z L(z)= 10

V=f L(f)=4

L(g)= min {11, 10 + 6} = 11.

L(e)= min {5, 4 + 4} = 8

Resultados del 1 al 3.

L(h)= min {7, 4 + 5} = 7

1. {7; (a, b, c, f)} 2. {11; (a, b, c, g)} 3. {10; (a, b, c, d, z)}

L(i)= min {∞, 4 + 4} = 8 L(g)= min {8, 4 + 4} = 8 L(j)= min {∞, 4 + 3} = 7 Iteración 5 T= {d, e, g, i, j, z}

Búsqueda del 4. b, j

V= e L(e)= 5 L(h)= min {7, 5 + 7} = 7

Iteración 1

Iteración 6

T = {a, b, c, d, e, f, g, h, i, j, z}

T= {d, g, i, j, z}

V=b L(b)=0

V=d L(d)=5

L(a)= min {∞, 0 + 3} = 3

L(g)= min {8, 5 + 7} = 7

L(e)= min {∞, 0 + 5} = 5 L(f)= min {∞, 0 + 7} = 7 L(c)= min {∞, 0 + 2} = 2 Iteración 2

L(z)= min {∞, 5 + 2} = 7 Iteración 7 T= { g, i, j, z}

T = {a, c, d, e, f, g, h, i, j, z}

V=j L(j)= 7

V= c L(c)=2

L(i)= min {8, 7 + 6} = 8

L(f)= min {7, 2 + 2} = 4

L(g)= min {8, 7 + 4} = 8

L(d)= min {∞, 2 + 3} = 5

L(z)= min {7, 7 + 7} = 7

L(g)= min {∞, 2 + 6} = 8

Resultado de la búsqueda de b, j

Iteración 3 T = {a, d, e, f, g, h, i, j, z} V=a L(a)=3 L(e)= min {5, 3 + 5} = 5 L(h)= min {∞, 3 + 4} = 7

4. {7;(b, c, f, j)}

TECNOLÓGICO NACIONAL DE MÉXICO

Búsqueda del 5. h, d.

Iteración 6

Iteración 1

T = {b, d, e, g, j, z}

T = {a, b, c, d, e, f, g, h, i, j, z} V=h L(h)=0 L(a)= min {∞, 0 + 4} = 4 L(e)= min {∞, 0 + 7} = 7 L(f)= min {∞, 0 + 5} = 5 L(i)= min {∞, 0 + 2} = 2 Iteración 2 T = {a, b, c, d, e, f, g, i, j, z} V=i L(i)=2 L(f)= min {5, 2 + 4} = 5 L(j)= min {∞, 2+ 6} = 8 Iteración 3 T = {a, b, c, d, e, f, g, j, z} V=a L(a)=4 L(b)= min {∞, 4+ 3} = 7 L(e)= min {7, 4+ 5} = 7 Iteración 4 T = {b, c, d, e, f, g, j, z} V=f L(f)=5 L(b)= min {7, 5+ 7} = 7 L(e)= min {7, 5+ 4} = 7 L(j)= min {8, 5+ 3} = 8

V=b L(b)=7 L(e)= min {7, 7 + 5} = 7 Iteración 7 T= { d, e, g, j, z} V=e L(e)=7 No hay ninguno para evaluar por lo tanto e se elimina. Iteración 8 T= { d, g, j, z} V=j L(j)=8 L(g)= min {9, 8+ 4} = 9 L(z)= min {∞, 8+ 5} = 13 Iteración 9 T= {d, g, z} V=g L(g)= 9 L(d)= min {10, 9+ 7} = 10 L(z)= min {13, 9+ 6} = 13 Iteración 10 T= { d, z} V=d L(d)= 10 L(z)= min {13, 10 + 2} = 12 Resultado de la búsqueda del 5. h,d 5. {10;(h, f, c, d)}

L(g)= min {∞, 5+ 4} = 9 L(c)= min {∞, 5+ 3} = 7 Iteración 5 T = {b, c, d, e, g, j, z} V= c L(c)=7 L(b)= min {7, 7+ 2} = 7 L(g)= min {9, 7+ 6} = 9 L(d)= min {∞, 7+ 3} = 10

Respuesta del problema del par de la ruta mas corta es es: 1. {7; (a, b, c, f)} 4. {7;(b, c, f, j)}