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

Решение.

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

Выпишем все возможные маршруты, исходя из таблицы расстояний:

1. Прямой путь или путь через один промежуточный пункт:
— $A \to D$. Длина: $5$ км.
— $A \to B \to D$. Длина: $1 + 3 = 4$ км.
— $A \to C \to D$. В таблице нет прямой дороги из $C$ в $D$, значит, этот вариант требует дополнительных пунктов.

2. Пути через два промежуточных пункта:
— $A \to B \to E \to D$. Длина: $1 + 2 + 1 = 4$ км.
— $A \to C \to E \to D$. Длина: $4 + 2 + 1 = 7$ км.
— $A \to E \to B \to D$. Длина: $6 + 2 + 3 = 11$ км.
— $A \to E \to D$. Длина: $6 + 1 = 7$ км.

3. Пути через три промежуточных пункта:
— $A \to B \to C \to E \to D$. Длина: $1 + 2 + 2 + 1 = 6$ км.
— $A \to C \to B \to E \to D$. Длина: $4 + 2 + 2 + 1 = 9$ км.

Теперь сравним длины всех найденных маршрутов:
$A \to D$: $5$ км
$A \to B \to D$: $4$ км
$A \to B \to E \to D$: $4$ км
$A \to B \to C \to E \to D$: $6$ км
$A \to C \to E \to D$: $7$ км
$A \to E \to D$: $7$ км

Минимальное значение среди всех возможных путей составляет $4$ км. Такую длину имеют сразу два маршрута: $A-B-D$ и $A-B-E-D$.

Ответ: 4

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