Анализировать простейшие модели объектов · 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 построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего пути…
Графы
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице.
A | B | C | D | E | F | |
A | 3 | 5 | 15 | |||
B | 3 | 4 | ||||
C | 5 | 3 | ||||
D | 4 | 3 | 2 | 6 | ||
E | 2 | 2 | ||||
F | 15 | 6 | 2 |
Определите длину кратчайшего пути между пунктами A и F. Передвигаться можно только по дорогам, указанным в таблице. Каждый пункт можно посетить только один раз.
Правильный ответ
11
Пояснение
Решение. Для решения этой задачи мы воспользуемся методом построения дерева возможных путей от начального пункта A до конечного пункта F. Наша цель — найти маршрут с минимальной суммарной длиной, учитывая условие, что каждый пункт можно посетить только один раз.
Выпишем все возможные пути из пункта A, последовательно переходя к соседним вершинам согласно таблице:
1) Путь через B:
Из A можно пойти в B (длина 3).
Из B можно пойти в D (длина 4).
Из D есть два варианта: в E или в F.
- Если пойдём в F: A→B→D→F. Длина: 3+4+6=13 км.
- Если пойдём в E: A→B→D→E. Из E можно попасть в F (длина 2).
Путь: A→B→D→E→F. Длина: 3+4+2+2=11 км.
2) Путь через C:
Из A можно пойти в C (длина 5).
Из C можно пойти в D (длина 3).
Из D есть два варианта: в E или в F.
- Если пойдём в F: A→C→D→F. Длина: 5+3+6=14 км.
- Если пойдём в E: A→C→D→E. Из E можно попасть в F (длина 2).
Путь: A→C→D→E→F. Длина: 5+3+2+2=12 км.
3) Прямой путь:
В таблице указана прямая дорога из A в F.
Путь: A→F. Длина: 15 км.
Сравним полученные результаты:
- A→B→D→F=13 км
- A→B→D→E→F=11 км
- A→C→D→F=14 км
- A→C→D→E→F=12 км
- A→F=15 км
Самым коротким является путь A→B→D→E→F, его длина составляет 11 км.
Ответ: 11
Источник: ФИПИ