Задание 4

Анализировать простейшие модели объектов · 81 задание

Задание №4
№4
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего пути…
Графы
Задание №4
№4
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего п…
Графы
Задание №4
№4
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего пути…
Графы
Задание №4
№4
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. Определите длину кратчайшего пути между пункт…
Графы
Задание №4
№4
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего п…
Графы
Задание №4
№4
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего пути…
Графы
Задание №4
№4
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего пути…
Графы
Задание №4
№4
Между населёнными пунктами A , B , C , D , E , F построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайш…
Графы
Задание №4
№4
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых приведена в таблице. Определите длину кратчайшего пути между пунктами…
Графы
Задание №4
№4
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего пути…
Графы
Задание №4
№4
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых приведена в таблице. Определите длину кратчайшего пути между пунктами…
Графы
Задание №4
№4
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего пути…
Графы

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

Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.

	A	B	C	D	Е
A		3	3
B	3		2	1	4
C	3	2		5
D		1	5
Е		4

Определите длину кратчайшего пути между пунктами A и D. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.

Правильный ответ

Пояснение

Решение.

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

Выпишем все доступные дороги и их длину из таблицы:
$A-B = 3$
$A-C = 3$
$B-C = 2$
$B-D = 1$
$B-E = 4$
$C-D = 5$
$D-E = 5$

Теперь рассмотрим возможные маршруты из $A$ в $D$ :

1) Прямого пути $A-D$ в таблице нет.

2) Путь через пункт $B$ :
$A \rightarrow B \rightarrow D$
Длина: $3 + 1 = 4$ км.

3) Путь через пункт $C$ :
$A \rightarrow C \rightarrow D$
Длина: $3 + 5 = 8$ км.

4) Путь через пункты $C$ и $B$ :
$A \rightarrow C \rightarrow B \rightarrow D$
Длина: $3 + 2 + 1 = 6$ км.

5) Путь через пункты $B$ и $C$ :
$A \rightarrow B \rightarrow C \rightarrow D$
Длина: $3 + 2 + 5 = 10$ км.

6) Пути через пункт $E$ :
Чтобы попасть в $D$ через $E$ , нужно сначала доехать до $E$ из $B$ .
$A \rightarrow B \rightarrow E \rightarrow D$
Длина: $3 + 4 + 5 = 12$ км.
Или через $C$ : $A \rightarrow C \rightarrow B \rightarrow E \rightarrow D$ , что будет еще длиннее.

Сравним полученные результаты: $4$ , $8$ , $6$ , $10$ , $12$ . Самым коротким является путь $A \rightarrow B \rightarrow D$ , длина которого составляет $4$ км.

Ответ: 4

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