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

Решение.

Для решения задачи нам необходимо найти кратчайший путь из пункта $A$ в пункт $F$. По условию задачи накладывается важное ограничение: путь не должен проходить через пункт B. Также каждый пункт можно посетить не более одного раза.

1. Анализ таблицы и исключение лишних данных.
Так как мы не можем заходить в пункт $B$, мы мысленно вычеркиваем строку и столбец, соответствующие этому пункту. Теперь выпишем все доступные прямые дороги и их длины:
$A - C = 4$
$A - D = 15$
$C - D = 1$
$C - E = 2$
$D - F = 6$
$E - F = 2$

2. Поиск возможных маршрутов.
Рассмотрим все варианты путей из $A$ в $F$, исключая пункт $B$:

— Путь 1: $A \rightarrow D \rightarrow F$
Длина: $15 + 6 = 21$ км.

— Путь 2: $A \rightarrow C \rightarrow D \rightarrow F$
Длина: $4 + 1 + 6 = 11$ км.

— Путь 3: $A \rightarrow C \rightarrow E \rightarrow F$
Длина: $4 + 2 + 2 = 8$ км. (Внимание: перепроверим данные таблицы).

3. Уточнение данных по таблице.
Посмотрим внимательно на пересечения в таблице еще раз:
$A-C = 4$
$C-D = 1$
$D-E = 2$
$E-F = 2$
Попробуем составить путь через пункт $E$, используя связь $D-E$:
— Путь 4: $A \rightarrow C \rightarrow D \rightarrow E \rightarrow F$
Длина: $4 + 1 + 2 + 2 = 9$ км.

4. Сравнение результатов.
Мы нашли следующие маршруты:
1) $A-D-F$: $21$ км.
2) $A-C-D-F$: $11$ км.
3) $A-C-D-E-F$: $4 + 1 + 2 + 2 = 9$ км.
Прямой дороги $C-E$ в таблице нет (на пересечении $C$ и $E$ пусто), поэтому путь $A-C-E-F$ невозможен. Дорога $E-F$ имеет длину $2$, дорога $D-E$ имеет длину $2$, дорога $C-D$ имеет длину $1$, дорога $A-C$ имеет длину $4$.

Таким образом, кратчайший допустимый путь: $A \rightarrow C \rightarrow D \rightarrow E \rightarrow F$.

Его длина: $4 + 1 + 2 + 2 = 9$ км.

Ответ: 9 км.

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