Презентация по теме: "Решение задач. Формальные описания реальных объектов и процессов."

Формальные описания реальных объектов и процессов

Решение задач

Взвешенные графы

2

8

A

C

A

A

B

B

12

C

C

12

8

D

D

8

5

5

6

6

2

4

4

5

12

4

D

B

6

Весовая матрица

Кратчайший путь (перебор)

Определите кратчайший путь между пунктами A и D.

A

A

B

B

2

C

C

2

4

4

D

D

E

1

1

E

6

6

5

5

1

1

3

3

A

2

6

4

С

E

B

4

6

2

1

1

3

С

С

D

9

7

3

5

1

D

E

8

4

дерево возможных путей

3

D

7

Путь из А в Е через С

№ 3. Кратчайший путь (перебор)

A

A

B

B

C

2

  2

C

  3

D

D

  3

E

E

F

5 

  5

F

  5

  4

  4

  5

  2

  2

  3

3 

Определите кратчайший путь между пунктами A и F.

№ 3.

Определите кратчайший путь между пунктами A и F.

A

A

B

B

C

2

  2

C

  3

D

D

  3

E

E

5 

F

  5

F

  5

  5

  4

  4

  2

  2

  3

3 

Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего пути между пунктами  A  и  Е , проходящего через пункт  С .

№ 4.

Определите длину кратчайшего пути между пунктами  A  и  Е , проходящего через пункт  С .

Ответ:  8

№ 5. Кратчайший путь (перебор)

Между населёнными пунктами  А, В, С, D, Е, F  построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину  кратчайшего пути  между пунктами  А  и  F .  Передвигаться можно только по дорогам, протяжённость которых указана в таблице.

A

A

B

B

C

5

C

5

D

5

5

D

2

E

4

2

4

E

F

F

1

1

1

1

3

3

1

1

№ 5.

Определите длину  кратчайшего пути   между пунктами  А  и  F .  

A

A

B

B

C

5

5

C

D

5

D

5

4

E

2

E

4

2

F

F

1

1

1

1

3

3

1

1