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

Решение.

Для решения задачи мы проанализируем таблицу и построим дерево возможных путей из пункта A в пункт E. Числа в таблице означают длину дороги между соответствующими городами. Если ячейка пуста, значит, прямой дороги нет.

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

1) Прямой путь A — B — E:
Из A можно попасть в B (длина $3$).
Из B можно попасть напрямую в E (длина $6$).
Длина пути: $3 + 6 = 9$ км.

2) Путь через пункты B и C: A — B — C — E:
Из A в B (длина $3$).
Из B в C (длина $1$).
Из C в E (длина $3$).
Длина пути: $3 + 1 + 3 = 7$ км.

3) Путь через пункты B и D: A — B — D — E:
Из A в B (длина $3$).
Из B в D (длина $2$).
Из D в E (длина $3$).
Длина пути: $3 + 2 + 3 = 8$ км.

4) Путь через пункты B, C и D: A — B — C — D — E:
Из A в B (длина $3$).
Из B в C (длина $1$).
Из C в D (длина $3$).
Из D в E (длина $3$).
Длина пути: $3 + 1 + 3 + 3 = 10$ км.

5) Путь через пункты B, D и C: A — B — D — C — E:
Из A в B (длина $3$).
Из B в D (длина $2$).
Из D в C (длина $3$).
Из C в E (длина $3$).
Длина пути: $3 + 2 + 3 + 3 = 11$ км.

Сравним полученные результаты: $9$ км, $7$ км, $8$ км, $10$ км, $11$ км. Самым коротким является путь $A \rightarrow B \rightarrow C \rightarrow E$, длина которого составляет $7$ км.

Ответ: 7 км

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