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