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

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

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