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