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

Решение. Для решения этой задачи мы построим дерево всех возможных путей из пункта $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 км

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