Задание 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		2	7		6
B	2		3
C	7	3		5	2
D			5		3
E	6		2	3

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

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

Пояснение

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

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

Рассмотрим все возможные маршруты из $A$ в $D$ :

1) Прямого пути $A-D$ в таблице нет.

2) Пути через пункт $B$ :
— $A \to B \to C \to D$ . Длина: $2 + 3 + 5 = 10$ км.
— $A \to B \to C \to E \to D$ . Длина: $2 + 3 + 2 + 3 = 10$ км.

3) Пути через пункт $C$ :
— $A \to C \to D$ . Длина: $7 + 5 = 12$ км.
— $A \to C \to E \to D$ . Длина: $7 + 2 + 3 = 12$ км.
— $A \to C \to B$ . (Путь в $D$ через $B$ невозможен без повторного посещения $A$ или $C$ ).

4) Пути через пункт $E$ :
— $A \to E \to D$ . Длина: $6 + 3 = 9$ км.
— $A \to E \to C \to D$ . Длина: $6 + 2 + 5 = 13$ км.
— $A \to E \to C \to B$ . (Тупиковый путь, так как из $B$ можно попасть только в $A$ или $C$ , которые уже посещены).

Сравним полученные результаты:
Маршрут $A-B-C-D$ : $10$ км.
Маршрут $A-B-C-E-D$ : $10$ км.
Маршрут $A-C-D$ : $12$ км.
Маршрут $A-C-E-D$ : $12$ км.
Маршрут $A-E-D$ : $9$ км.
Маршрут $A-E-C-D$ : $13$ км.

Самым коротким оказался путь $A \to E \to D$ , его длина составляет $9$ км.

Ответ: 9 км

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