Определение оптимального маршрута (№3)

ОГЭ по информатике

Такой тип задач встречается под номером 3 в тексте ОГЭ по информатика.

Пример 1

Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).

Решение:

1. Построим граф – схему, соответствующую этой весовой матрице; из вершины А можно проехать в вершины B и C (длины путей соответственно 2 и 4):

2. Для остальных вершин можно рассматривать только часть таблицы над главной диагональю, которая выделена серым цветом; все остальные рёбра уже были рассмотрены ранее

3. Например, из вершины В можно проехать в вершины C и E (длины путей соответственно 1 и 7):

4. Новые маршруты из С – в D и E (длины путей соответственно 3 и 4):

5. Новый маршрут из D – в E (длина пути 3):

6. Новый маршрут из E – в F (длина пути 2):

7. Нужно проехать из А в F, по схеме видим, что в любой из таких маршрутов входит ребро EF длиной 2; таким образом, остается найти оптимальный маршрут из A в E

8. Попробуем перечислить возможные маршруты из А в Е:

  • А – В – Е длина 9
  • А – В – С – Е длина 7
  • А – В – C – D – Е длина 9
  • А –C – Е длина 8
  • А –C – B – Е длина 12
  • А –C – D – Е длина 10

9. Из перечисленных маршрутов кратчайший – A-B-C-E – имеет длину 7, таким образов общая длина кратчайшего маршрута A-B-C-E-F равна 7 + 2 = 9

10. Таким образом, правильный ответ - 9.

 

Пример 2

Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.


Определите длину кратчайшего пути между пунктами A и Е. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.
1) 4
2) 5
3) 6
4) 7

Решение: 

1. Построим граф – схему, соответствующую этой весовой матрице; из вершины А можно проехать в вершины B, C и D (длины путей соответственно 2, 5 и 1)

2. Для остальных вершин можно рассматривать только часть таблицы над главной диагональю, которая выделена серым цветом; все остальные рёбра уже были рассмотрены ранее. Например, ВА=АВ=2. Если нижняя часть таблицы отличается от верхней, то строим отдельный маршрут. В задачах, как правило, таблица симметрична.

3. Из вершины В можно проехать в вершину C (длина пути 1):

4. Из вершины C можно проехать в вершины D, E (длины путей 3 и 2):

5. Нужно проехать из А в Е, по схеме видим, что в любой из таких маршрутов входит ребро СE длиной 2; таким образом, остается найти оптимальный маршрут из A в С

Попробуем составить все возможные варианты маршрутов из точки А в точку С:

А-С = 5
А-В-С = 3
А-D-С = 4

Видно, что самый короткий маршрут от А до С это маршрут А-В-С. Добавляем последнее ребро С-Е, получим длину маршрута А-В-С-Е = 3 + 2 = 5. Это второй вариант ответа.

Ответ: 2

ОГЭ по информатике

blog comments powered by Disqus

Яндекс.Метрика Мой канал на youtube Усть-Куломская школа Усть-Куломский район Коноплев О.О.

© 2016 Рассыхаев А.А.