Задание 4 ОГЭ по информатике: анализ схем и таблиц, кратчайший путь

Что проверяет задание

Задание 4 проверяет умение работать с формальными описаниями объектов — таблицами и схемами (графами). Проверяемые навыки:

• находить и извлекать данные из таблицы, где строки и столбцы обозначают одни и те же объекты (населённые пункты, объекты, элементы схемы);
• переводить табличное представление связей в схему (граф) и обратно;
• выполнять простые вычисления над числовыми характеристиками связей — обычно суммирование расстояний;
• находить кратчайший (или иной оптимальный) путь между двумя объектами, перебирая все возможные варианты соединений.

В практике ОГЭ чаще всего встречается вариант с таблицей дорог между населёнными пунктами: нужно найти минимальную суммарную длину пути между двумя пунктами, если двигаться можно только по указанным дорогам.

Как выглядит формулировка и сколько баллов

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

Особенности:

• таблица квадратная, строки и столбцы соответствуют одним и тем же пунктам;
• таблица симметрична: расстояние из A в B равно расстоянию из B в A;
• если между двумя пунктами прямой дороги нет, соответствующая клетка пустая;
• диагональ (расстояние пункта до самого себя) всегда пустая.

Задание оценивается в 1 балл, ответ — целое число (длина пути в километрах). На решение стоит отводить не более 3–4 минут: задание не требует сложных вычислений, только аккуратности.

Что нужно знать

• Граф — набор вершин (пунктов) и рёбер (дорог), соединяющих некоторые пары вершин.
• Вес ребра — числовая характеристика связи, в данных задачах — расстояние в километрах.
• Путь — последовательность рёбер, соединяющая начальную и конечную вершину, где каждое следующее ребро начинается в вершине, где закончилось предыдущее.
• Длина пути — сумма весов всех рёбер, входящих в путь: $S = w_1 + w_2 + \dots + w_n$.
• Симметричность таблицы расстояний: если в ячейке на пересечении строки $X$ и столбца $Y$ стоит число $d$, то и в ячейке на пересечении строки $Y$ и столбца $X$ стоит то же число $d$.
• Отсутствие ребра: пустая клетка означает, что прямой дороги между этими пунктами нет, а не что расстояние равно нулю.
• Кратчайший путь — путь с минимальной суммой весов среди всех возможных путей между двумя вершинами; он может состоять не из одного, а из нескольких промежуточных участков.
• Кратчайший путь по весу и путь с минимальным количеством переходов — разные понятия: путь через две дороги может быть короче одной длинной прямой дороги.

Методы решения

1. Построение графа по таблице. Каждому пункту соответствует вершина, каждой непустой ячейке — ребро с весом, равным числу в этой ячейке. Мини-пример: в таблице для A, B, C дано A–B = 2, B–C = 3, ячейка A–C пуста. Граф: две вершины соединены ребром 2 (A–B), две другие — ребром 3 (B–C), прямой связи A–C нет.

2. Полный перебор маршрутов. Для графов с 4–5 вершинами количество разумных маршрутов невелико, поэтому проще перебрать все варианты пути от старта до финиша, посчитать сумму весов каждого и выбрать минимальную. Мини-пример (граф выше): путь из A в C только один — A–B–C, длина $2+3=5$, значит ответ 5.

3. Метод последовательных меток (упрощённая версия алгоритма Дейкстры). Начальной вершине присваивается метка 0, всем остальным — «бесконечность». На каждом шаге выбирается непосещённая вершина с наименьшей меткой, и через неё пересчитываются метки соседей: новая метка соседа = метка текущей вершины + вес ребра, если это значение меньше уже имеющейся метки. Мини-пример: вершины A(0), B, C; ребро A–B=4, A–C=6, B–C=1. Метка B через A: 4. Метка C через A: 6, но через B: $4+1=5$ — меньше, значит метка C обновляется до 5.

4. Анализ схемы через степень вершины. Для подтемы «анализ схемы» полезно уметь считать, сколько рёбер выходит из вершины (это соответствует количеству дорог, ведущих из пункта). Мини-пример: если из пункта D в таблице заполнены три ячейки (кроме диагонали), значит из D выходит три дороги.

5. Проверка через симметричность таблицы. Если результат подсчёта не совпадает при чтении «по строке» и «по столбцу», значит допущена ошибка при переносе данных из таблицы в граф — это удобный способ самоконтроля.

Алгоритм решения по шагам

1. Выписать все пункты (вершины) и обозначить начальный и конечный пункт из условия.
2. Построить схему (граф) по таблице: для каждой непустой ячейки нарисовать ребро между соответствующими вершинами и подписать его вес.
3. Проверить построенный граф на симметричность — сверить, что каждое ребро отражено согласованно в обеих клетках таблицы.
4. Найти все вершины, напрямую соединённые с начальным пунктом, и вершины, напрямую соединённые с конечным пунктом.
5. Перебрать все возможные маршруты от начала до конца (через одну, две и более промежуточных вершин), не повторяя вершины в одном маршруте.
6. Для каждого маршрута посчитать сумму весов рёбер.
7. Сравнить все полученные суммы и выбрать наименьшую — это и есть ответ.
8. Сверить ответ: убедиться, что при движении по выбранному маршруту действительно используются только существующие дороги.

Разбор примеров

Пример 1. По таблице дорог восстанавливается схема с рёбрами: $A\text{-}B=1$, $B\text{-}C=2$, $B\text{-}D=2$, $B\text{-}E=7$, $C\text{-}E=3$, $D\text{-}E=4$. Нужно найти кратчайший путь от A до E.

Шаг 1. Из A выходит только одна дорога — к B (вес 1). Значит любой путь из A обязательно начинается с A–B.

Шаг 2. Из B можно попасть к C (вес 2), к D (вес 2) или прямо к E (вес 7).

Шаг 3. Перебираем варианты окончания пути:

• A–B–E: $1+7=8$;
• A–B–C–E: $1+2+3=6$;
• A–B–D–E: $1+2+4=7$.

Шаг 4. Сравниваем суммы: 8, 6, 7. Минимальная — 6, достигается на маршруте A–B–C–E.

Ответ: 6.

Пример 2. Схема по таблице: $A\text{-}B=5$, $A\text{-}C=3$, $B\text{-}C=1$, $B\text{-}D=4$, $C\text{-}D=6$, $D\text{-}E=1$.

Шаг 1. Из A есть две дороги: к B (5) и к C (3).

Шаг 2. Единственная дорога к E идёт через D (вес 1), а к D можно попасть через B (4) или через C (6).

Шаг 3. Перебираем маршруты до E:

• A–B–D–E: $5+4+1=10$;
• A–C–D–E: $3+6+1=10$;
• A–C–B–D–E: $3+1+4+1=9$;
• A–B–C–D–E: $5+1+6+1=13$.

Шаг 4. Минимальная сумма — 9, маршрут A–C–B–D–E.

Ответ: 9.

Пример 3. Схема по таблице: $A\text{-}B=3$, $A\text{-}C=7$, $B\text{-}C=2$, $B\text{-}E=8$, $C\text{-}D=4$, $D\text{-}E=1$.

Шаг 1. Из A есть две дороги: к B (3) и к C (7).

Шаг 2. К E ведут дороги от B (8) и от D (1), а к D можно попасть только через C (4).

Шаг 3. Перебираем маршруты:

• A–B–E: $3+8=11$;
• A–C–D–E: $7+4+1=12$;
• A–B–C–D–E: $3+2+4+1=10$;
• A–C–B–E: $7+2+8=17$.

Шаг 4. Минимальная сумма — 10, маршрут A–B–C–D–E.

Ответ: 10.

Во всех трёх примерах ключевой приём один: сначала определить, какие дороги выходят из начального пункта, затем — какие ведут к конечному, а затем перебрать все связующие цепочки, не пропуская варианты с бо́льшим числом промежуточных пунктов — именно они часто оказываются короче на суммарный вес.

Типичные ошибки и ловушки

• Путают строку и столбец при чтении таблицы. Нужно чётко фиксировать, какая метка относится к строке, а какая — к столбцу, особенно если таблица напечатана компактно.
• Принимают пустую клетку за нулевое расстояние. Пустая клетка означает отсутствие прямой дороги, а не расстояние 0 — по такой «дороге» двигаться нельзя.
• Обрывают перебор маршрутов слишком рано, ограничиваясь только прямой дорогой или путём с одним промежуточным пунктом, и не проверяют более длинные по числу участков, но короче по сумме веса маршруты.
• Путают кратчайший путь (по сумме весов) с путём с наименьшим числом дорог. Маршрут через три пункта может быть короче маршрута через один пункт, если веса рёбер малы.
• Ошибаются при сложении весов, особенно когда в маршруте несколько промежуточных вершин — стоит явно выписывать каждое слагаемое.
• Не используют симметричность таблицы для проверки — при чтении данных «вкось» легко перепутать значение соседней ячейки.
• Забывают, что вершина в одном маршруте не должна повторяться — путь не может проходить через один и тот же пункт два раза.

Как готовиться

• Разбирать таблицы разного размера — от 4 до 6 пунктов, чтобы натренировать быстрое построение графа по табличным данным.
• После построения графа обязательно проверять его на симметричность: сравнивать значение из строки и из столбца для одной и той же пары пунктов.
• Тренироваться выписывать все возможные маршруты в явном виде (например, в столбик), а не держать их в голове — это снижает число ошибок при переборе.
• Отдельно решать задачи, где ответ достигается не на прямом ребре, а на пути через два-три промежуточных пункта — такие задачи чаще всего приводят к ошибкам из-за поспешных выводов.
• Засекать время на решение: на задание 4 в норме должно уходить не больше 3–4 минут, при регулярной практике время сокращается за счёт автоматизации построения графа.
• После решения всегда делать быструю проверку: пройти выбранный маршрут «по шагам» и убедиться, что каждый участок действительно есть в таблице, а сумма посчитана верно.