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

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

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

1) Прямой дороги из $A$ в $D$ нет (в таблице на пересечении $A$ и $D$ пусто), поэтому рассмотрим пути через промежуточные пункты.

2) Путь через пункт $B$:
Из $A$ в $B$ расстояние равно $2$ км.
Из $B$ можно поехать в $C$ (расстояние $1$ км).
Из $C$ можно поехать в $D$ (расстояние $4$ км).
Маршрут $A \to B \to C \to D$: длина $2 + 1 + 4 = 7$ км.
Из $C$ также можно поехать в $E$ (расстояние $3$ км), а из $E$ в $D$ (расстояние $3$ км).
Маршрут $A \to B \to C \to E \to D$: длина $2 + 1 + 3 + 3 = 9$ км.

3) Путь через пункт $C$:
Из $A$ в $C$ расстояние равно $4$ км.
Из $C$ можно поехать напрямую в $D$ (расстояние $4$ км).
Маршрут $A \to C \to D$: длина $4 + 4 = 8$ км.
Из $C$ можно поехать в $B$, но мы там уже были в предыдущем пункте (или это удлинит путь).
Из $C$ можно поехать в $E$ (расстояние $3$ км), а из $E$ в $D$ (расстояние $3$ км).
Маршрут $A \to C \to E \to D$: длина $4 + 3 + 3 = 10$ км.

4) Путь через пункт $E$:
Из $A$ в $E$ расстояние равно $5$ км.
Из $E$ можно поехать в $D$ (расстояние $3$ км).
Маршрут $A \to E \to D$: длина $5 + 3 = 8$ км.
Из $E$ можно поехать в $C$ (расстояние $3$ км), а из $C$ в $D$ (расстояние $4$ км).
Маршрут $A \to E \to C \to D$: длина $5 + 3 + 4 = 12$ км.

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

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

Ответ: 7 км

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