Раздел A • Категория A2 (демонстрационный вариант-2012)
Условие задачи
| A | B | C | D | E | F | |
| A | 2 | 4 | ||||
| B | 2 | 1 | 7 | |||
| C | 4 | 1 | 3 | 4 | ||
| D | 3 | 3 | ||||
| E | 7 | 4 | 3 | 2 | ||
| F | 2 |
Дано:
между населенными пунктами А, B, C, D, E, F построены дороги, протяжность которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет).
Вопрос:
определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).
Варианты ответа:
1) 9 2) 10 3) 11 4) 12
Методические указания
Решение данной задачи будет проводить с использованием специализированной структуры данных - объектный граф.
Объектный граф - это совокупность ребер и узлов, соединяющих данные узлы.
В качестве узлов графа выступают населенные пункты, а в качестве ребер графа выступают дороги, между населенными пунктами.
Решение
Схематично отобразим дороги между населенными пунктами в виде объектного графа.
В качестве вершин объектного графа выступают названия населенных пунктов: A, B, C, D, E, F.
В качестве ребер объектного графа выступают дороги между населенными пунктами с указанием протяженности.
Пример №1: рассмотрим населенные пункты B и E. Как видно из заданной таблицы, между данными пунктами существует дорога, следовательно, и на графе между данными вершинами будет существовать ребро. Протяженность дороги составляет 7 единиц.
Пример №2: рассмотрим населенные пункты A и D. Как видно из заданной таблицы, между данными пунктами нет дороги, следовательно, и на объектном графе между данными узлами нет соединительного ребра.
Рассмотрим первый вариант пути из пункта А в пункт F:
Маршрут имеет вид: A -> B -> C -> D -> E -> F.
A -> B = 2
B -> C = 1
C -> D = 3
D -> E = 3
E -> F = 2
Просуммируем выписанные значения:
A -> F = 2 + 1 + 3 +3 + 2 = 11 [ед].
Промежуточный вывод: чтобы добраться из населенного пункта A в населенный пункт F потребуется проехать 11 [ед].
Рассмотрим второй вариант пути из пункта А в пункт F:
Маршрут имеет вид: A -> B -> C -> E -> F.
A -> B = 2
B -> C = 1
C -> E = 4
E -> F = 2
Просуммируем выписанные значения:
A -> F = 2 + 1 + 4 + 2 = 9 [ед].
Промежуточный вывод: чтобы добраться из населенного пункта A в населенный пункт F потребуется проехать 9 [ед].
Рассмотрим третий вариант пути из пункта А в пункт F:
Маршрут имеет вид: A -> B -> E -> F.
A -> B = 2
B -> E = 7
E -> F = 2
Просуммируем выписанные значения:
A -> F = 2 + 7 + 2 = 11 [ед].
Промежуточный вывод: чтобы добраться из населенного пункта A в населенный пункт F потребуется проехать 11 [ед].
Рассмотрим четвертый вариант пути из пункта А в пункт F:
Маршрут имеет вид: A -> C -> D -> E -> F.
A -> C = 4
C -> D = 3
D -> E = 3
E -> F = 2
Просуммируем выписанные значения:
A -> F = 4 + 3 + 3 + 2 = 12 [ед].
Промежуточный вывод: чтобы добраться из населенного пункта A в населенный пункт F потребуется проехать 12 [ед].
Рассмотрим пятый вариант пути из пункта А в пункт F:
Маршрут имеет вид: A -> C -> E -> F.
A -> C = 4
C -> E = 4
E -> F = 2
Просуммируем выписанные значения:
A -> F = 4 + 4 + 2 = 10 [ед].
Промежуточный вывод: чтобы добраться из населенного пункта A в населенный пункт F потребуется проехать 10 [ед].
Консолидируем проверенные маршруты и выберем тот, имеющий минимальную протяженность:
A -> B -> C -> D -> E -> F: 11
A -> B -> C -> E -> F : 9
A -> B -> E -> F : 11
A -> C -> D -> E -> F : 12
A -> C -> E -> F : 10
Очевидно, что минимальная протяженность составила 9 [ед].
Вывод: |
длина кратчайшего пути между пунктами A и F составила 9 [ед]. |
Резюме
A -> B -> C -> D -> E -> F: 11
A -> B -> C -> E -> F : 9
A -> B -> E -> F : 11
A -> C -> D -> E -> F : 12
A -> C -> E -> F : 10
Ответ: |
1 |
Комментарии