Задание 4

Анализировать простейшие модели объектов · 81 задание

Задание №4
№4
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего пути…
Графы
Задание №4
№4
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего п…
Графы
Задание №4
№4
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего пути…
Графы
Задание №4
№4
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. Определите длину кратчайшего пути между пункт…
Графы
Задание №4
№4
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего п…
Графы
Задание №4
№4
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего пути…
Графы
Задание №4
№4
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего пути…
Графы
Задание №4
№4
Между населёнными пунктами A , B , C , D , E , F построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайш…
Графы
Задание №4
№4
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых приведена в таблице. Определите длину кратчайшего пути между пунктами…
Графы
Задание №4
№4
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего пути…
Графы
Задание №4
№4
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых приведена в таблице. Определите длину кратчайшего пути между пунктами…
Графы
Задание №4
№4
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего пути…
Графы

Задание №4 — Теоретические основы информатики

Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых приведена в таблице.

	A	B	C	D	E
A		5			3
B	5		1	5
C		1		1	5
D		5	1		6
E	3		5	6

Определите длину кратчайшего пути между пунктами A и D (при условии, что передвигаться можно только по указанным в таблице дорогам). Каждый пункт можно посетить только один раз.

Правильный ответ

Пояснение

Решение. Для решения этой задачи мы построим дерево возможных путей из пункта $A$ в пункт $D$ , подсчитывая длину каждого маршрута. Нам нужно найти самый короткий из них, учитывая условие, что в каждый пункт можно заходить не более одного раза.

Выпишем все доступные дороги и их протяжённость из таблицы:
$A-B = 5$
$A-E = 3$
$B-C = 1$
$B-E = 5$
$C-D = 1$
$C-E = 5$
$D-E = 6$

Теперь рассмотрим все возможные маршруты из точки $A$ в точку $D$ :

1) Путь через пункт B:
Из $A$ идем в $B$ (длина $5$ ).
- Из $B$ можно пойти в $C$ : $A \to B \to C$ . Длина: $5 + 1 = 6$ . Из $C$ идем в $D$ .
Маршрут $A \to B \to C \to D$ . Длина: $5 + 1 + 1 = 7$ .
- Из $B$ можно пойти в $E$ : $A \to B \to E$ . Длина: $5 + 5 = 10$ . Из $E$ можно пойти в $D$ или $C$ .
Маршрут $A \to B \to E \to D$ . Длина: $5 + 5 + 6 = 16$ .
Маршрут $A \to B \to E \to C \to D$ . Длина: $5 + 5 + 5 + 1 = 16$ .

2) Путь через пункт E:
Из $A$ идем в $E$ (длина $3$ ).
- Из $E$ можно пойти в $D$ :
Маршрут $A \to E \to D$ . Длина: $3 + 6 = 9$ .
- Из $E$ можно пойти в $B$ : $A \to E \to B$ . Длина: $3 + 5 = 8$ . Из $B$ идем в $C$ , затем в $D$ .
Маршрут $A \to E \to B \to C \to D$ . Длина: $3 + 5 + 1 + 1 = 10$ .
- Из $E$ можно пойти в $C$ : $A \to E \to C$ . Длина: $3 + 5 = 8$ . Из $C$ идем в $D$ .
Маршрут $A \to E \to C \to D$ . Длина: $3 + 5 + 1 = 9$ .

Сравним длины всех найденных маршрутов:
$A-B-C-D = 7$
$A-B-E-D = 16$
$A-B-E-C-D = 16$
$A-E-D = 9$
$A-E-B-C-D = 10$
$A-E-C-D = 9$

Минимальное значение среди всех вариантов равно $7$ .

Ответ: 7

Источник: ФИПИ