ЕГЭ-2015 задание 5.
Анализ информационных моделей
При решении задач данного вида используется знания информационных моделей (таблицы, диаграммы, графики) и перебор вариантов, выбор лучшего по какому-то признаку
Теория
- особых знаний, кроме умения перебирать варианты (не пропустив ни одного!) здесь, как правило, не требуется
- полезно знать, что такое граф (это набор вершин и соединяющих их ребер) и как он описывается в виде таблицы, хотя, как правило, все необходимые объяснения даны в формулировке задания
- чаще всего используется взвешенный граф, где с каждым ребром связано некоторое число (вес), оно может обозначать, например, расстояние между городами или стоимость перевозки
- рассмотрим граф (рисунок слева), в котором 5 вершин (A, B, C, D и E); он описывается таблицей, расположенной в центре; в ней, например, число 5 на пересечении строки В и столбца С означает, что, во-первых, есть ребро, соединяющее В и С, и во-вторых, вес этого ребра равен 5; пустая клетка на пересечении строки А и столбца В означает, что ребра из А в В нет
- обратите внимание, что граф по заданной таблице (она еще называется весовой матрицей) может быть нарисован по-разному; например, той же таблице соответствует граф, показанный на рисунке справа от нее
- в приведенном примере матрица симметрична относительно главной диагонали; это может означать, например, что стоимости перевозки из В в С и обратно равны (это не всегда так)
- желательно научиться быстро (и правильно) строить граф по весовой матрице и наоборот
Задача
Между населенными пунктами A, B, C, D, E, F, G построены дороги, протяженность которых приведена в таблице. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.
A | B | C | D | E | F | G | |
A | 2 | 6 | |||||
B | 2 | 5 | 3 | ||||
C | 5 | 1 | 8 | ||||
D | 6 | 3 | 1 | 9 | 7 | ||
E | 9 | 5 | |||||
F | 7 | 7 | |||||
G | 8 | 5 | 7 |
Определите длину кратчайшего пути между пунктами A и G (при условии, что передвигаться можно только по построенным дорогам).
Решение
Из пункта A за 1 шаг можно попасть в пункты B и D. AB(2) и AD(6) - в скобках указана длина маршрута.
Из пункта B можно попасть в пункты C и D. ABC(2+5=7) и ABD(2+3=5).
Из пункта C можно попасть в пункты D и G. ABCD(2+5+1=8) (этот путь длиннее прямого AD и его можно не рассматривать дальше) и ABCG(2+5+8=15) - первый способ добраться в конечный пункт длиной 15.
Из пункта D можно попасть в пункты E и F, причем будем учитывать только кратчайший маршрут ABD длиной 5. Соответственно ABDE (2+3+9=14) и ABDF (2+3+7=11).
Из пункта E попадаем в G и общая длина пути ABDEG (2+3+9+5=19) равна 19.
Из пункта F попадаем в G и общая длина пути ABDFG (2+3+7+7=19) тоже равна 19.
Правильный ответ: 15.
- Подробности
- Опубликовано: 29 Апрель 2015
- Просмотров: 5462