Сначала давайте разберёмся с некоторыми определениями, которые нам понадобятся для решения 4-го задания.
Иногда очень трудно структурировать информацию описанными структурами из-за сложных «взаимоотношений» между объектами. Тогда можно использовать графы:
Граф – это набор вершин и связей между ними, называющихся рёбрами:
Связный граф – это граф, между любыми вершинами которого существует путь.
Дерево – это связный граф без циклов (замкнутых участков).
Взвешенные графы и весовая матрица
У взвешенных графов указан «вес ребра»:
Из взвешенных графов получается весовая матрица, обратное преобразование тоже возможно.
Поиск кратчайшего пути (перебор)
Рассмотрим, как решать 4-е задание ОГЭ по информатике. Есть несколько способов решений этого задания.
Пример:
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
Определите длину кратчайшего пути между пунктами A и Е, проходящего через пункт С. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Способ 1 — Решение графом
Проведем визуализацию данной таблицы. Для этого сначала расставим все населенные пункты, которые даны в таблице, они будут вершинами. Далее соединяем вершины ребрами (ребра это дороги, идущие из пункта А) и указываем вес каждого ребра (числовое значение в таблице).
Из табличной структуры получили структуру в виде графов. Из полученного рисунка видно, что анализ будет проходить гораздо лучше. Мы должны найти кратчайший путь между пунктом А и Е проходящий через пункт С. Для этого просто переберем все данные маршруты.
1) A-B-C-D-E=8
2) A-C-D-E=9
3) A-C-B-D-E=13
4) A-B-D-E — не подходит, так как не идет через С
5)A-D-E — не подходит, так как не идет через С
6) A-E — не подходит, так как не идет через С
Ответ: кратчайший маршрут — A-B-C-D-E=8
Способ 2 — Решение деревом (перебор)
Берем за основу данные таблицы и строим дерево, которое начинается с вершины А, а конечной точкой является вершина Е. Оно рисуется очень просто. Есть корень A, от него вниз исходят прямые линии в соответствие с тем, в какие города есть дороги из пункта A. Это будут ветки дерева. Учтем, что каждая ветвь, должна включить узел пересечения с С и заканчиваться E.
Поясним построенное дерево:
- Вершина А связана с вершинами В, С, D и Е.
- Вершина В с вершинами С и D и т.д.
Связи и значение длин берем из таблицы.
После построения дерева, суммируем длины отрезков, которые проходят через вершину С.
Каким бы способом вы ни решали поставленную задачу — результат должен быть одним и тем же.
В нашем случае в бланк ответов заносим число 8.
Если статья была полезна, ставьте 👍 и подписывайтесь на канал ✅, а также на наш телеграм-канал, в котором вы найдёте ещё больше полезной информации по подготовке к ОГЭ по информатике и не только.