Tarea IO2 Rutas PDF

Preview

Summary

9.Usted debe hacer un viaje en auto a una ciudad que nunca ha visitado. Estudia un plano para determinar la ruta más corta hasta su destino. Según la ruta que elija, hay otras cinco ciudades (llamadas A,B,C,D,E) por las que puede pasar el camino. El plano muestra las millas de cada carretera que son...

Description

9.3.2

Usted debe hacer un viaje en auto a una ciudad que nunca ha visitado. Estudia un plano para determinar la ruta más corta hasta su destino. Según la ruta que elija, hay otras cinco ciudades (llamadas A,B,C,D,E) por las que puede pasar el camino. El plano muestra las millas de cada carretera que son conexión directa entre dos ciudades sin que otra intervenga. Estas cifras se resumen en la siguiente tabla, donde un guion indica que no hay conexión directa entre dos ciudades sin que otra intervenga.

Nodo resuelto más cercano a

Nodo no resuelto más cercano

Distancia total involucrada

n-esimo nodo más cercano

Distancia mínima

Ultima conexión

nodo no resuelto Origen Origen Origen A A C A B B B C A B B C A B E E D E

conectado A C B B B B D D E C E D D E E D D DESTINO D DESTINO DESTINO

40 50 50 40+10 50+20 40+70 50+55 50+40 50+20 50+50 40+70 50+55 40+70 50+55 40+70 50+55 90+80 90+10 105+60 90+80

A C

40 50

ORIGEN-A ORIGEN-C

B

50

A-B

C

70

B-C

E

90

B-E

D DESTINO

100 165

E-D D-DESTINO

RUTA MAS CORTA ORIGEN-A-B-E-D-DESTINO TOTAL=160

d) si se obtiene el mismo resultado ya que el costo también sería el mínimo, y la forma de tabla o grafico dan una buena idea de cómo llegar a lo mínimo posible o máximo dependiendo de la intención. e)

9.3.3 Una compañía de aéreo local piensa comprar un tractor nuevo para mover el tren de carros que llevan y traen el equipaje de los aviones que aterrizan en un pequeño aeropuerto que está en pleno crecimiento. Dentro de tres años se instalará un nuevo sistema mecanizado de transporte de equipaje, por lo que después no se necesitará el tracto. No obstante, tendrá una carga de trabajo pesada y los costos de operación y mantenimiento aumentarán rápido con el tiempo y podría resultar costeable reemplazo en uno o dos años.

Nodo Nodo no resuelto resuelto más más cercano cercano a nodo no conectado resuelto

0 0 1 0 1 1

1 2 2 3 3 2

2 1

3 3

2

3

RUTA MAS CORTA: 0-1-3

Distancia total involucrada

n-esimo nodo más cercano

Distancia mínima

Ultima conexión

13000 28000

1 2

13000 17000

0-1 0-2

17000+1300 0

2

30000

1-2

33000+1300 0

3

46000

1-3

$46000

9.3-4. Utilice el algoritmo descrito en la sección 9.3 para encontrar la ruta más corta a través de las redes a) y b), en las cuales los números representan las distancias reales entre los nodos correspondientes. a)

Nodo resuelto más cercano a nodo no resuelto

Nodo no resuelto más cercano conectado

Distancia total involucrada

n-esimo nodo más cercano

Distancia mínima

Ultima conexión

O O O A A B B B D D

A B C B D C D E E T

4 6 5 1 7 2 5 4 1 6

A

4

O-A

B

1

A-B

D

5

B-D

T

6

D-T

n-esimo nodo más cercano

Distancia mínima

Ultima conexión

RUTA MAS CORTA: O-A-B-D-T=16

b)

Nodo resuelto más cercano a nodo no resuelto

Nodo no resuelto más cercano conectado

Distancia total involucrada

O O O A B A C B C C D E D F E F G E H G H I

A B C C C D D E E F F F G G H H H I I T T T

4 3 6 9 9 7 11 9 11 8 9 10 11 10 11 13 12 14 14 17 19 18

C C C D D E

6

OC

F

8

CF

G

10

FG

T

T

GT

Distancia mínima

Ultima conexión

RUTA MAS CORTA: O-C-F-G-T=17

Nodo resuelto más cercano a nodo no resuelto

Nodo no resuelto más cercano conectado

Distancia total involucrada

n-esimo nodo más cercano

SE SE

A B

4.6 4.7

A B

SE C C E F

C E F LN LN

4.2 7.7 7.6 11.3 11.5

C E F LN

4.2 3.5 3.4 11.3

RUTA MAS CORTA: SE-C-E-LN=11.30

SE-C C-E C-F E-LN...