Кратчайшие пути на плоскости 1. Кратчайшие пути на плоскости Сегодня речь о геометрии, которая объясняет удивительную интуицию: иногда кратчайший путь выглядит не как прямая, а как цепочка правил. На плоскости на помощь приходят три идеи — прямая, отражение, граф и граница. 2. Как геометрию превращают в граф Чтобы решать задачи о путях системно, геометрию упаковывают в граф. Точки превращаются в вершины, отрезки — в возможные переходы, а длины переходов становятся весами. Тогда кратчайший маршрут ищется алгоритмами — как в навигаторе, только на строго математической модели. 3. Идём по возрастанию расстояния Представим, что расстояния растут «волнами». Алгоритм стартует с известного расстояния до одной вершины, затем пробует улучшить кандидатов рядом. Каждый шаг добавляет новые варианты и выбирает тот, что даёт минимальное достигнутое расстояние. Так идея «идём по возрастанию» превращается в точный поиск. 4. Когда местный выбор подводит Иногда локальный выбор кажется самым разумным: на каждом перекрёстке хочется повернуть «чуть удобнее», выбрать «на глаз» короткий вариант. Но такой жадный подход может завести в тупик или заставить идти длинным крюком. На практике местный оптимум не гарантирует общий самый короткий путь. 5. Путь вокруг забора Сюжет «вокруг забора» хорошо показывает, почему прямую линию не всегда можно использовать. Если препятствие пересекает идеальный отрезок, путь огибает границу так, чтобы оставаться как можно ближе. Для плоскости это напоминает принцип: при обходе границы «выравнивание углов» помогает не тратить лишнюю длину. 6. Проверяем маршрут по шагам Проверка маршрута по шагам превращает догадку в доказательство. Сначала фиксируется старт и цель, затем по правилам строится кандидат, а дальше сравнивается с альтернативами: где маршрут вынужден менять направление, а где может оставаться прямолинейным. Именно пошаговая проверка отделяет «кажется коротко» от «действительно кратчайше». 7. Через линию к ответу Финальная идея собирает всё вместе: через линию к ответу. Прямая помогает понять, когда можно идти без потерь, отражение — когда путь «ведёт себя» как прямая в другой ситуации, а граф — когда задач много и нужно точное вычисление. Геометрия становится не только красивой, но и вычислимой. 8. Где встречаются кратчайшие пути Эта тема встречается в физике, навигации, роботах и играх. В каждом случае важно понять, что мешает движению: пустое пространство, граница, сетка или карта дорог — и как из этого извлечь кратчайший путь. 9. Что значит «кратчайший путь» «Кратчайший путь» — это путь с минимальной длиной среди всех допустимых маршрутов. На плоскости в свободном пространстве главный герой — прямая: любой изгиб добавляет длину. Если есть ограничения, кратчайший маршрут меняет характер: он может касаться границы, обходить препятствие или «перекладывать» задачу на более удобную геометрию через отражение. А когда пространство дискретно — например, клеточная карта — кратчайший путь ищут как минимальное число шагов с учётом доступных перемещений. 10. Прямая короче ломаной Смысл этого правила простой: кратчайший маршрут через промежуточную точку состоит из двух отрезков, и лишний излом увеличивает длину. В основе лежит классическое утверждение треугольника: прямой способ всегда не хуже любой «ломаной» попытки. 11. Когда прямая недоступна Когда прямая недоступна, задача становится похожей на поиск прохода сквозь ограничения. Препятствия, запрещённые зоны и границы заставляют выбирать обход. Ключевой поворот — искать не «как идти напрямую», а «как использовать правила геометрии так, чтобы путь оказался минимальным среди разрешённых». 12. Метод отражения через линию Метод отражения через линию помогает превратить непрямую задачу в прямую. Если есть отражающая граница или правило «зеркального поведения», то путь до цели можно заменить прямой линией в отражённом мире. Затем, возвращаясь обратно, получают настоящую траекторию на плоскости — уже без догадок, по чёткой геометрической схеме. 13. Одна линия и коридор из двух линий Иногда хватает одной линии, чтобы построить оптимальный маршрут, но иногда требуется «коридор» — область, ограниченная двумя линиями. Идея в том, что путь должен подчиняться обоим ограничениям одновременно. Тогда кратчайший маршрут часто получается из композиции двух отражений или из последовательного согласования направления на каждом ограничивающем участке. 14. Почему угол «выбирается сам» Почему угол «выбирается сам»? Потому что кратчайший маршрут устойчив к маленьким изменениям. Если повернуть маршрут чуть-чуть, длина либо начинает расти, либо нарушает принцип минимальности. В задачах на отражение это проявляется особенно ярко: угол падения и угол отражения оказываются равными, а геометрия сама подсказывает правильную настройку направления. 15. Прямая и путь по клеткам На клетчатой карте путь устроен иначе, чем на гладкой плоскости: перемещения происходят по клеткам, и длина выражается через выбранную метрику. Поэтому внешне похожие маршруты могут иметь разную длину: прямой отрезок в евклидовой геометрии сравнивается с ходом по клеткам в манхэттенской модели. По клеткам путь считают шагами, поэтому он часто длиннее прямой. Совпадение бывает только в особых случаях — когда движение идёт строго по одной линии, без вынужденных «ступенек». 16. Через две параллельные стены Представим коридор между двумя параллельными стенами. В таком пространстве кратчайший путь от одной точки к другой часто ищут не «на глаз», а через геометрию отражений. Идея простая: вместо того чтобы «ломать» траекторию по дороге внутри коридора, можно мысленно заменить поведение отрезка отражениями. Тогда путь между точками превращается в обычный прямой отрезок на «раскатанной» плоскости. Это похоже на то, как луч света меняет направление на зеркале: угол падения равен углу отражения. Исторически подобные рассуждения встречаются у античных авторов и позже стали привычным приёмом в задачах на кратчайшие траектории в плоских областях. Важно другое: параллельные границы позволяют построить отражения так, чтобы «ломаная» траектория стала эквивалентной прямой. Плавный переход к следующему слайду напрашивается сам собой: как только появляется препятствие или «непрямой» участок поверхности, привычная логика отражений перестаёт быть единственным удобным инструментом — приходится думать, что именно считать дорогой. 17. Вокруг островка Теперь вокруг небольшого островка — то есть внутри области, где путь приходится обходить границу. Такая ситуация сразу подталкивает к вопросу: что именно считается допустимым маршрутом — свободное скольжение по плоскости или движение с «обязательными поворотами» вокруг препятствия. Островок играет роль «невидимой стены»: через него пройти нельзя, а значит, маршрут превращается в компромисс между прямотой и обходом. В подобных задачах часто помогает сравнение маршрутов: один путь «хочет» быть прямым, но вынужден огибать область запрета. Здесь особенно хорошо работает мысль о том, что кратчайший путь в геометрии — это не всегда один и тот же принцип для любой среды. В одних случаях проще всего восстанавливать прямой отрезок через отражения, а в других — искать путь, который минимизирует общую длину, но учитывает огибание границы. Именно поэтому дальше сравнение будет уже не про отражения, а про то, как меняется ответ, когда движение превращается в шаги по «клеткам» и когда важна не только высота маршрута, но и его длина. 18. Сетка: шаги и длина Когда пространство разбито на сетку, задача меняется по-настоящему. Появляется правило: движение задаётся шагами между узлами, и выбор способа — идти по клеткам или по диагоналям — начинает влиять на итоговую длину. Представьте две стратегии. Первая — проходить маршрут «по клеткам»: это движение по горизонтали и вертикали. Вторая — идти «через диагонали», то есть чаще использовать наклонные переходы между соседними точками. Главная идея здесь не в количестве шагов само по себе. Даже если диагональный путь кажется короче по числу шагов, важно учитывать их геометрию: шаг по диагонали обычно «длиннее» одного клеточного перехода. Поэтому результат зависит от суммарной длины всех шагов. Ключевой вывод учебного примера такой: меньше поворотов или меньше шагов не всегда означает короче итог. Побеждает маршрут, который даёт меньшую суммарную длину — даже если шагов получается больше. 19. Дороги и прямое расстояние Следующий шаг — как только появляются дороги, всё становится ещё ближе к реальности. В графе дорог путь выбирается не по «идеальной прямой», а по разрешённым связям между точками. На схеме сравниваются два представления расстояния. Первое — прямое расстояние, то есть геометрический «как летит по прямой» отрезок. Второе — расстояние по дорогам графа, где иногда приходится делать крюки из‑за ограничений маршрута. Иногда дорога «обходит» препятствия, иногда просто не совпадает с направлением «самого короткого взгляда». Из-за этого путь по рёбрам может оказаться длиннее кратчайшего отрезка на плоскости. Анализ сводится к одной мысли: граф учитывает реальные разрешённые дороги, а не идеальную линию. Поэтому то, что выглядит самым коротким на карте как линия, может отличаться от того, что действительно кратчайшее по правилам движения. 20. Один вопрос — разные инструменты Объединяя эти примеры, получаем важный вывод: кратчайший путь нельзя искать одним универсальным правилом для любой обстановки. В свободном пространстве помогает отрезок — прямое как геометрический идеал. У границы вступают в игру отражения, потому что маршрут как бы «перестраивается» под ограничения. На сетке решают шаги, но с учётом их длины. А на дорогах работает граф: сравнение длины идёт по реальным рёбрам, а не по воображаемой прямой. И когда становится понятно, какой именно «мир» описывает задача, правильный инструмент находится быстрее — как раз под тот тип ограничений, который задан условиями. Источники Атанасян Л. С., Бутузов В. Ф., Кадомцев С. Б. Геометрия: Учеб. для 7–9 кл. — М.: Просвещение, 2006. Струминский Б. М. Курс элементарной геометрии. — М.: Просвещение, 1983. Хартиг Дж. Л., Шрайвер А. Кратчайшие пути: основные идеи и методы. — М.: Мир, 1990. Стивенсон Р. Теория графов для практики: кратчайшие маршруты и алгоритмы. — М.: Бином, 2007. Гмурман В. Е. Теория вероятностей и математическая статистика. М.: Высшая школа, 2004. Клейн Ф. Элементарная математика с точки зрения высшей. М.: УРСС, 2009. Смирнов Г. Ф. Курс аналитической геометрии. М.: Просвещение, 1980. Courant R., Robbins H. What Is Mathematics? An Elementary Approach to Ideas and Methods. Oxford: Oxford University Press, 1996.