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

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

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

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

2) Пути через пункт $B$:
— $A \to B \to C \to D$: длина равна $2 + 1 + 5 = 8$ км.
— $A \to B \to C \to E \to D$: длина равна $2 + 1 + 1 + 3 = 7$ км.

3) Пути через пункт $C$:
— $A \to C \to D$: длина равна $4 + 5 = 9$ км.
— $A \to C \to B$: (путь $A \to C \to B \to \dots$ не имеет смысла рассматривать отдельно, так как мы уже проверили варианты с $B$ и $C$).
— $A \to C \to E \to D$: длина равна $4 + 1 + 3 = 8$ км.

4) Пути через пункт $E$:
— $A \to E \to D$: длина равна $6 + 3 = 9$ км.
— $A \to E \to C \to D$: длина равна $6 + 1 + 5 = 12$ км.
— $A \to E \to C \to B$: (путь $A \to E \to C \to B \to \dots$ приведет в тупик или увеличит длину).

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

Минимальное значение среди всех возможных вариантов составляет $7$ км. Это путь $A \to B \to C \to E \to D$.

Ответ: 7

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