Тапсырмалар на маршруты
Задачи на маршруты описывают перемещения между пунктами, соединёнными дорогами, линиями связи или переходами. Нужно определить, существует ли путь, посчитать число маршрутов или выбрать маршрут с минимальной длиной, стоимостью либо временем.
1. Как читать условие и строить граф
Сначала выделите объекты задачи: города, станции, перекрёстки, страницы сайта или состояния устройства. Они становятся вершинами графа. Возможные переходы между объектами становятся рёбрами. Если переход разрешён только в одну сторону, ребро ориентированное; если движение возможно в обоих направлениях, ребро неориентированное.
Маршрут — последовательность вершин и рёбер, по которым можно пройти из начальной вершины в конечную. Важно отличать маршрут от пути: в школьных задачах словом «маршрут» часто называют любой допустимый проход, а повторение вершин может быть либо разрешено, либо запрещено условием. Поэтому всегда проверяйте фразы «не посещая пункт повторно», «каждый участок ровно один раз» и «можно возвращаться».
Длина маршрута — сумма длин или стоимостей его рёбер. Число маршрутов — количество различных последовательностей переходов между указанными вершинами. Кратчайший путь — маршрут минимальной длины или стоимости; подробнее см. страницу о кратчайшем пути.
2. Тапсырмалар на существование маршрута
В задаче на существование достаточно установить, есть ли хотя бы один путь из начальной вершины в конечную. Для небольшого графа можно проследить все переходы вручную. Удобный приём — помечать достижимые вершины: сначала отмечают стартовую, затем все вершины, соединённые с уже отмеченными. Если конечная вершина получила отметку, маршрут существует.
В неориентированном графе маршрут между двумя вершинами существует тогда и только тогда, когда они лежат в одной компоненте связности. В ориентированном графе направление рёбер учитывать обязательно: наличие обратной дороги не следует из наличия прямой.
Если требуется пройти по каждому ребру ровно один раз, это уже задача об эйлеровом маршруте. Для неё полезна бет об условиях существования эйлерова цикла. Если требуется посетить вершины по особым правилам, одной проверки связности недостаточно.
В ориентированном графе мысленно замените стрелки нельзя: переход разрешён только в направлении стрелки. В таблице или схеме отмечайте не только посещённые вершины, но и способ, которым в них попали.
3. Подсчёт количества маршрутов
Если граф имеет слоистую структуру, количество маршрутов удобно считать динамически. Пусть \(f(v)\) — число способов попасть из старта в вершину \(v\). Для начальной вершины устанавливают \(f(S)=1\). Для каждой другой вершины складывают значения всех вершин, из которых в неё можно прийти.
Такой переход применим напрямую, если в графе нет циклов или условие запрещает повторное посещение вершин. Обрабатывайте вершины в порядке движения от старта к финишу. Если маршруты проходят через несколько обязательных этапов, удобно сделать таблицу: строки — вершины, столбцы — этапы или номера шагов.
Если все маршруты из \(S\) в \(T\) разбиваются на непересекающиеся группы по последнему переходу, то общее число маршрутов равно сумме количеств маршрутов в этих группах. Один маршрут нельзя учитывать дважды.
В вершину X ведут рёбра из A и B. Из S в A существует 3 маршрута, а из S в B — 5. Сколько маршрутов из S в X, если другие входы в X отсутствуют?
В задачах с выбором нескольких независимых этапов действует правило умножения: если первый этап можно выполнить \(a\) способами, а второй — \(b\) способами для каждого выбора первого, то всего \(a\cdot b\) нұсқа. На практике сначала определите, идут варианты вместо друг друга немесе последовательно.
4. Оптимизация: кратчайший маршрут
Для поиска маршрута минимальной длины сравнивают суммы весов рёбер, а не количество рёбер. Путь из двух длинных участков может быть хуже пути из четырёх коротких. В невзвешенном графе, где каждый переход считается одинаковым, кратчайший путь ищут по числу рёбер; полезна бет о кратчайшем пути в невзвешенном графе.
Если веса неотрицательны, для больших графов применяют алгоритм Дейкстры. В таблице расстояний для каждой вершины хранят лучшее известное расстояние от старта. На каждом шаге выбирают ещё не обработанную вершину с минимальной меткой и пытаются улучшить расстояния до её соседей.
Чтобы восстановить сам маршрут, а не только его длину, при улучшении расстояния до \(v\) запоминают предшественника \(u\). Затем идут от финиша по предшественникам назад до старта и разворачивают полученную последовательность.
5. Разобранный пример
Из пункта A нужно попасть в D. Разрешены переходы A→B, A→C, B→D, C→D и B→C. Требуется найти число маршрутов из A в D, если вершины нельзя посещать повторно, а затем определить кратчайший маршрут при длинах AB=2, AC=5, BD=6, CD=1, BC=2.
Сначала считаем маршруты. В A один способ оказаться в старте: \(f(A)=1\). В B можно попасть только из A, поэтому \(f(B)=1\). В C можно попасть напрямую из A или через B: \(f(C)=f(A)+f(B)=2\). В D можно попасть из B или C: \(f(D)=f(B)+f(C)=3\). Маршруты: A→B→D, A→C→D, A→B→C→D.
Следовательно, существует 3 маршрута, а кратчайший — A→B→C→D, его длина равна 5. Обратите внимание: самый короткий по числу переходов маршрут A→C→D имеет два ребра, но не является оптимальным по длине.
1. Складывать длины только одного участка вместо всего маршрута. 2. Считать одинаковыми маршруты, проходящие через разные вершины. 3. Умножать количества вариантов там, где нужно сложение. 4. Игнорировать направление стрелок. 5. Запускать алгоритм Дейкстры при отрицательных весах без проверки условий. 6. Забывать, что условие может запрещать повторение вершин или рёбер.
Связанные типы тапсырма
Для тапсырма о полном наборе связей полезна бет о полном графе, а для подсчёта доли существующих связей — бет о долях полного графа. Если маршрутная схема разделяется на две группы вершин, обратите внимание на двудольные графы. Тапсырмалар о выборе непересекающихся соединений связаны со паросочетанием и совершенным паросочетанием.
Проверь себя
Главное
- Представляйте объекты как вершины, а переходы как рёбра; направление и веса рёбер считывайте строго по условию.
- Для существования маршрута проверяйте достижимость, а для подсчёта используйте сложение по возможным последним переходам.
- Длина маршрута равна сумме весов его рёбер; кратчайший маршрут выбирают по минимальной сумме, а не обязательно по числу рёбер.
- При решении фиксируйте промежуточные значения и проверяйте, не посчитан ли один маршрут дважды.
- Если нужно не только расстояние, но и последовательность вершин, сохраняйте предшественника каждой вершины.