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

Решение.

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

Выпишем все возможные пути, начиная из пункта $A$:

1. Из пункта $A$ можно попасть в $B$ (длина $4$) или в $C$ (длина $9$).

Ветка через пункт B:
Из $B$ можно пойти в $C$ (длина $2$) или в $D$ (длина $3$).
— Если пойдём $A \to B \to C$ (длина $4 + 2 = 6$):
    Из $C$ можно пойти в $D$ (длина $2$) или в $E$ (длина $2$).
    • Путь $A \to B \to C \to E$. Длина: $4 + 2 + 2 = 8$ км.
    • Путь $A \to B \to C \to D \to E$. Длина: $4 + 2 + 2 + 3 = 11$ км.
— Если пойдём $A \to B \to D$ (длина $4 + 3 = 7$):
    Из $D$ можно пойти в $C$ (длина $2$) или в $E$ (длина $3$).
    • Путь $A \to B \to D \to E$. Длина: $4 + 3 + 3 = 10$ км.
    • Путь $A \to B \to D \to C \to E$. Длина: $4 + 3 + 2 + 2 = 11$ км.

Ветка через пункт C:
Из $C$ можно пойти в $B$ (длина $2$), в $D$ (длина $2$) или в $E$ (длина $2$).
— Путь $A \to C \to E$. Длина: $9 + 2 = 11$ км.
— Путь $A \to C \to D \to E$. Длина: $9 + 2 + 3 = 14$ км.
— Путь $A \to C \to B \to D \to E$. Длина: $9 + 2 + 3 + 3 = 17$ км.

Сравним полученные результаты:
$A \to B \to C \to E = 8$
$A \to B \to D \to E = 10$
$A \to B \to C \to D \to E = 11$
$A \to B \to D \to C \to E = 11$
$A \to C \to E = 11$
$A \to C \to D \to E = 14$
$A \to C \to B \to D \to E = 17$

Минимальное значение среди всех возможных вариантов составляет $8$ км.

Ответ: 8

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