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

Решение.

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

Выпишем все возможные маршруты, следуя правилу: в одном пути нельзя посещать один и тот же пункт дважды.

1) Рассмотрим пути, начинающиеся из A в B (длина $2$ км):
- Из B можно поехать в C: $A \to B \to C$. Длина: $2 + 3 = 5$ км. Из C есть дорога в D: $A \to B \to C \to D$. Длина: $5 + 3 = 8$ км. Из D дорог в E нет. (Путь тупиковый или не ведет к цели напрямую).
- Из B можно поехать в D: $A \to B \to D$. Длина: $2 + 3 = 5$ км. Из D можно поехать в C: $A \to B \to D \to C$. Длина: $5 + 3 = 8$ км. Из C есть дорога в E: $A \to B \to D \to C \to E$. Длина: $8 + 2 = 10$ км.

2) Рассмотрим пути, начинающиеся из A в D (длина $1$ км):
- Из D можно поехать в B: $A \to D \to B$. Длина: $1 + 3 = 4$ км. Из B можно поехать в C: $A \to D \to B \to C$. Длина: $4 + 3 = 7$ км. Из C есть дорога в E: $A \to D \to B \to C \to E$. Длина: $7 + 2 = 9$ км.
- Из D можно поехать в C: $A \to D \to C$. Длина: $1 + 3 = 4$ км. Из C есть дорога в E: $A \to D \to C \to E$. Длина: $4 + 2 = 6$ км.
- Из D можно поехать в B, а из B в A — нельзя (повтор).

3) Проверим, есть ли другие варианты. В таблице указано, что из пункта E можно попасть только в C (длина $2$ км). Значит, любой маршрут в E обязательно должен заканчиваться участком $... \to C \to E$.
Посмотрим кратчайший путь до C:
- $A \to B \to C$ (длина $2 + 3 = 5$)
- $A \to D \to C$ (длина $1 + 3 = 4$)
- $A \to B \to D \to C$ (длина $2 + 3 + 3 = 8$)
- $A \to D \to B \to C$ (длина $1 + 3 + 3 = 7$)

Самый короткий путь до C равен $4$ км (маршрут $A \to D \to C$).
Прибавляем последний участок $C \to E$: $4 + 2 = 6$ км.

Сравним все найденные законченные маршруты до E:
1. $A \to B \to D \to C \to E$: $10$ км.
2. $A \to D \to B \to C \to E$: $9$ км.
3. $A \to D \to C \to E$: $6$ км.

Минимальное значение составляет $6$ км.

Ответ: 6 км

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