В задании № 4 дают таблицу дорог между населёнными пунктами. Нужно найти длину самого короткого пути. Научимся рисовать схему, последовательно проверять маршруты и вовремя отбрасывать неподходящие варианты.
1. Что означает таблица
Буквы обозначают пункты. Число на пересечении строки и столбца — длина прямой дороги между ними. Пустая клетка означает, что прямой дороги нет.
В нашем примере дороги двусторонние: A–B и B–A — одна дорога. Поэтому таблица симметрична.
Длина пути — сумма длин его дорог. Сравниваем километры, а не количество остановок и не длину линий на рисунке.
2. Как нарисовать схему
Будем искать кратчайший путь из A в F. Каждый пункт можно посетить не более одного раза. Все расстояния указаны в километрах.
Исходная таблица
| |
A |
B |
C |
D |
E |
F |
| A |
— |
2 |
3 |
7 |
|
15 |
| B |
2 |
— |
|
3 |
|
|
| C |
3 |
|
— |
1 |
|
|
| D |
7 |
3 |
1 |
— |
2 |
11 |
| E |
|
|
|
2 |
— |
3 |
| F |
15 |
|
|
11 |
3 |
— |
Получится такая схема
2 3 3 1 7 2 3 11 15 A B C D E F
Рисуем по шагам:
- Нарисуй кружки A, B, C, D, E, F. Их расположение можно выбрать самостоятельно.
- Прочитай строку A: соедини A с B, C, D, F. Подпиши длины 2, 3, 7, 15.
- Из строки B добавь B–D длиной 3. Из строки C — C–D длиной 1. Дороги к A уже нарисованы, повторять их не нужно.
- Добавь D–E длиной 2, D–F длиной 11 и E–F длиной 3.
Эта схема называется графом. Кружки — вершины, дороги — рёбра.
3. Когда можно остановить ветку
Отсечь ветку — перестать проверять её продолжения. Для этого нужна причина.
① Повторяется пункт.
По условию повторные посещения запрещены. Например, после A → B → D нельзя возвращаться ни в A, ни в B.
② Получился тупик.
Финиш ещё не достигнут, а все дороги ведут в уже посещённые пункты.
③ Уже слишком длинно.
Назовём рекордом длину самого короткого полного пути, который мы уже нашли. Если текущая сумма не меньше рекорда, улучшения не получится: дальнейшие дороги добавят километры.
Например, уже найден полный путь длиной 12 км. В другой ветке набрано 12 км, но финиша ещё нет. Эту ветку можно остановить. Равенства тоже достаточно.
4. Дерево поиска: проверяем и отсекаем
Из начального пункта рисуем ветки во все разрешённые пункты. Из каждого нового пункта снова рисуем возможные продолжения. Так получается дерево маршрутов.
Внутри кружка — пункт и вся пройденная длина от A.
На стрелке — длина добавляемой дороги.
Один пункт может встречаться в разных ветках: это разные маршруты. Повторять пункт внутри одного маршрута нельзя, поэтому стрелки назад в уже посещённые пункты не рисуем.
Сначала проверяем прямой путь A → F: получаем первый рекорд 15 км. Затем полностью проверяем ветку через B, после неё — через C, затем — через D.
Внутри каждой ветки идём слева направо, каждый раз продолжая выбранный маршрут до финиша или остановки. Рекорд постепенно меняется: 15 → 10 → 9.
На узком экране рисунок можно прокрутить по горизонтали.
Серый крестик — тупик.
Например, после A → B → D → C можно выйти только в уже посещённые A или D.
Красный крестик — рекорд не улучшить.
Уже набранная длина не меньше лучшего подходящего пути, найденного к этому моменту.
Зелёная цепочка — лучший путь.
A → C → D → E → F.
3 + 1 + 2 + 3 = 9 км.
Почему сравнения на рисунке разные? Рекорд менялся во время поиска. Когда получили путь длиной 16 км, рекорд был 10 км. Позже нашли путь длиной 9 км и оставшиеся варианты сравнивали уже с ним.
Все ветви проверены или обоснованно остановлены. Ответ: 9.
5. Дополнительные условия
Нужно пройти через B.
В конце каждого маршрута проверяй, был ли в нём B. Путь без B нельзя принимать за рекорд, даже если он короткий.
Нельзя проходить через E.
Убери E и все дороги к нему. В таблице можно зачеркнуть строку E и столбец E. Затем строй дерево по оставшимся дорогам.
Рекордом становится только полный маршрут, который выполняет все условия задания.
6. Что важно запомнить
Не выбирай только ближайший пункт.
Короткая первая дорога может привести к длинному маршруту.
Не отбрасывай ветку без причины.
Причины: нарушение условия, тупик или невозможность улучшить рекорд.
Возле пункта записывай накопленную сумму.
Каждый следующий участок прибавляй к ней.
В ответе — длина.
Запиши только число, без букв маршрута и «км».
7. Проверь себя
Используй ту же таблицу. Каждый пункт можно посетить не более одного раза.
Задание А. Найди длину кратчайшего пути из A в F через B.
Ответ и решение
У B только два соседа: A и D. Поэтому подходящий маршрут начинается A → B → D. Уже пройдено 2 + 3 = 5 км.
Из D в C идти бесполезно: получится тупик. Остаются два продолжения:
Через E: 5 + 2 + 3 = 10.
Сразу в F: 5 + 11 = 16.
Ответ: 10.
Задание Б. Найди длину кратчайшего пути из A в F без посещения E.
Ответ и решение
Убираем E и дороги D–E, E–F. Прямой путь A → F даёт первый рекорд 15.
Проверяем остальные маршруты до F:
A → B → D → F: 2 + 3 + 11 = 16.
A → C → D → F: 3 + 1 + 11 = 15.
A → D → F: 7 + 11 = 18.
Рекорд не улучшился. Здесь два кратчайших маршрута, но длина у них одинаковая.
Ответ: 15.