Задание под номером 4 из ОГЭ по информатике это формальное описание реальных объектов и процессов. Подразумевает работу с таблицей расстояний между населёнными пунктами, при помощи которой, нужно найти кратчайшее расстояние между какими-то двумя пунктами.
Задание нацелено на внимательность и построено таким образом, что в нём легко ошибиться. При чём, ошибиться всего на единицу. Используя правильный подход, эта задача легко решаема.
Пример задания
Между населенными пунктами A, B, C, D, E построены дороги, протяженность которых (в километрах) приведена в таблице.
Определите длину кратчайшего пути между пунктами A и C (при условии, что передвигаться можно только по построенным дорогам).
Анализ
Необходимо найти кратчайшую длину из пункта A в пункт C.
Перемещаться можно по любым дорогам. Главное - найти самый короткий способ добраться из одного пункта в другой.
Решение
Шаг 1 - строим граф
Построим граф на основе имеющейся таблицы. Просто отобразим все населённые пункты и соединим их отрезками. Над каждым отрезком укажем расстояние.
Шаг 2 - поиск кратчайшего пути по графу
По графу найти кратчайший путь проще, чем по таблице, так как когда информация визуализирована нам проще замечать детали.
Так как нужно найти путь из пункта A, то с него и начнём. Из пункта A ведут всего две дороги: в пункт B или в пункт D. По рисунку видно, что пункт B и пункт пункт D тоже соединены. Как будет добраться до пункта D быстрее? Напрямую A-D или выбрать A-B-D? Если напрямую, то расстояние равно 8, а если через пункт B, то 6. Через пункт B будет короче, поэтому путь A-D можно больше не учитывать. Вычеркнем A-D из графа:
Видно, что пункт D соединён с пунктом C дорогой, расстояние которой равно 1. Таким образом получим, что маршрут A-B-D-C = 2 +4 + 1 = 7.
Но нам пока что рано заканчивать, ведь мы не рассмотрели другие маршруты. Маршрут A-B-D-E-C рассматривать нет смысла, так как D и C соединены дорогой с расстоянием равным единицы, а расстояния меньшего чем 1 мы точно не найдём.
Тогда остаются не рассмотрены маршруты A-B-E-D-C и A-B-E-C.
A-B-E-D-C явно длиннее чем A-B-E-C, потому что E-D-C = 6, а E-C = 3. Поэтому рассчитаем только A-B-E-C.
A-B-E-C = 2 + 1 + 3 = 6
Получается, что самый короткий маршрут это A-B-E-C, а не A-B-D-C.
Ответ: 6