XV Международный конкурс научно-исследовательских и творческих работ учащихся
Старт в науке
Сети Штейнера
Автор работы награжден дипломом победителя III степени
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF
Введение
Задача Штейнера заключается в поиске наименьшего дерева Штейнера — кратчайшей сети, объединяющей заданный конечный набор точек плоскости. Свое название получила в честь Якоба Штейнера (1796—1863).
История данной задачи восходит ко временам Пьера Ферма (1601—1665), который, после изложения своего метода исследования минимумов и максимумов, написал.
Тот же, кто этот метод не оценил, пусть он решит [следующую задачу]: для заданных трех точек найти такую четвертую, что если из нее провести три отрезка в данные точки, то сумма этих трех отрезков даст наименьшую величину.
Эта задача была частично решена Э. Торричелли (1608—1647) и Б. Кавальери (1598—1647), учениками Б. Кастелли (1577—1644), затем найденная ими конструкция была модифицирована Т.
Симпсоном (1710—1761) и окончательно уточнена Ф. Хейненом и Ж. Бертраном (1822-1900). В результате, был получено геометрическое построение точки S, ныне называемой точкой Ферма (иногда точкой Торричелли), которая для трёх заданных точек A, B и C даёт минимально возможную сумму длин отрезков AS, BS, CS.
В 1934 году В. Ярник и O. Кесслер сформулировали обобщение задачи Ферма, заменив три точки на произвольное конечное число. А именно, их задача состоит в описании связных плоских графов наименьшей длины, проходящих через данное конечное множество точек плоскости.
Актуальность и значимость исследования:
Изученный и представленный материал может быть использован на уроках геометрии в школе, а также будет полезен для учеников.
Такие задачи могут встречаться на олимпиадах в школах, они развивают логическое мышление и кругозор школьников, что является актуальным.
Глава 1. Алгоритм Штейнера (Поиск кратчайших сетей)
В общей форме задача Штейнера была в первый раз сформулирована в статье Милоша Кёсслера и Войцеха Ярника, опубликованной в 1934 году, однако сама эта проблема не приобрела широкой известности вплоть до 1941 года, когда Рихард Курант и Герберт Е. Роббинс включили её в свою книгу «Что такое математика?». Курант и Роббинс связали эту задачу с исследованиями Якоба Штейнера, немецкого математика XIX столетия, работавшего в Берлинском университете. Работа Штейнера была посвящена поиску одной точки, сумма расстояний от которой до всех точек заданного множества была бы минимальной. Однако ещё в 1640 году впервые была поставлена задача, являющаяся частным случаем обеих описанных задач — той, над которой работал Штейнер, и той, которая носит его имя: найти точку P, сумма расстояний от которой до каждой из трёх заданных точек минимальна. Эванджелиста Торричелли и Бонавентура Кавальери независимо друг от друга решили эту задачу. Торричелли и Кавальери обосновали, чту суммарное расстояние минимально, когда все сопряжённые углы в точке P больше или равны 120°.
Необходимо провести отрезки прямых, соединяющие исходные точки (назовем их A, B и C), с точкой в вершине наибольшего угла (скажем, B). Если угол B больше или равен 120°, то искомая точка P совпадает с точкой B. Другими словами, кратчайшая сеть в данном случае представляет собой просто два отрезка прямых между точками A и B и точками B и C. Если угол в точке B меньше 120°, то точка P должна находиться где-то внутри треугольника. Чтобы найти её, следует построить равносторонний треугольник с основанием на самой большой стороне треугольника ABC, а именно на отрезке AC. Третья вершина равностороннего треугольника (обозначим её X) находится на противоположной стороне от точки B относительно AC. Вокруг построенного равностороннего треугольника описываем окружность и проводим прямую, соединяющую точки B и X. Точка P будет на пересечении этой прямой и окружности. Соединив точки A, B и C с точкой P, мы получаем три угла, в точности равные 120° каждый, и искомую кратчайшую сеть. Более того, длина отрезка BX оказывается равной длине кратчайшей сети. В дальнейшем в нашей статье мы будем называть точку X замещающей точкой, поскольку замена точек A и C одной точкой X не изменяет длину сети.
Задача с тремя точками и задача Штейнера для многих точек обладают много общих свойств. Их решения, имеющие вид дерева, типичны тем, что при удалении любого отрезка из кратчайшей сети мы должны будем исключить одну из заданных точек. Другими словами, мы не можем пройти по сети из какой-либо заданной точки и вернуться в неё, без того чтобы не пройти те или иные отрезки повторно. По этой причине графические решения задачи с тремя точками и задачи со многими точками называются деревьями Штейнера. Отрезки прямых называются рёбрами, а точки, роль которых аналогична точке P и которые нужно добавить для построения дерева, называются точками Штейнера.
Задача Штейнера для трёх точек даёт также некоторую информацию о геометрии кратчайших деревьев Штейнера. Во-первых, каждый угол равен 120° или больше, а это означает, что каждая точка соединяется с остальным деревом не более чем тремя рёбрами. Во-вторых, в каждой точке Штейнера сходятся ровно три ребра, образуя друг с другом углы, в точности равные 120°. В-третьих, число рёбер дерева всегда на единицу меньше суммарного числа заданных исходных точек и точек Штейнера. И наконец, последнее свойство: поскольку в каждой точке Штейнера сходятся ровно три ребра и по крайней мере одно ребро должно касаться каждой из заданного множества точек, максимальное число точек Штейнера для любой задачи на две меньше, чем число заданных исходных точек.
При одном и том же количестве и расположении исходных точек можно построить много различных деревьев Штейнера, удовлетворяющих перечисленным выше условиям. Некоторые из этих деревьев, называемые локально минимальными решениями, нельзя сократить за счёт мелкомасштабных изменений, таких как небольшое перемещение ребра или расщепление точки Штейнера. Всё же не всякое локально минимальное дерево Штейнера даёт кратчайшее из возможных решений задачи. Для того чтобы преобразовать сеть в кратчайшее дерево, называемое глобально минимальным деревом Штейнера, могут потребоваться крупномасштабные перемещения точек Штейнера.
Глава 2. Планирование сети дорог
Рассмотренная прежде постановка задачи о прокладке коммуникаций может не включать требования о том, что коммуникации могут разветвляться лишь на территории связываемых объектов. Зачастую реальность не накладывает этих ограничений, например, при строительстве дорог, которые могут менять направление, иметь повороты, развилки и перекрестки любого вида. Данная задача известна как ''задача Штейнера на графах''.
Вообще говоря, известно два типа такого рода задач.
Евклидова задача Штейнера состоит в соединении множества точек на плоскости так, чтобы сумма длин отрезков была минимальна.
Линейная задача Штейнера вместо евклидова расстояния между точками оперирует линейным расстоянием: d(X, Y) = |x1-x2| + |y1 - y2|. При этих условиях если через каждую точку из множества Р провести вертикальные и горизонтальные линии, то решение задачи Штейнера можно получить, рассматривая в качестве возможных точек Штейнера точки пересечения полученной сетки линий.
Линейные задачи Штейнера имеют применение при монтаже печатных схем электронных устройств и в логистике практически не используются, в отличие от евклидовых задач.
Сразу же зададимся вопросом: а может ли расположение развилок вне связываемых объектов уменьшить длину кратчайшей системы дорог? Для случая, когда четыре города расположены в углах квадрата, допустим со стороной равной 1 км, кратчайшая система дорог с разветвлением только в городах имеет длину 3, тогда как интуитивное расположение перекрестка в центре квадрата дает результирующую длину примерно 2,8.
Итак, улучшение результата возможно. Однако можно ли утверждать что 2 корня из 2 – это уже минимум? Вряд ли, по крайней мере никаких оснований для этого нет. Но зато уже видно, что в такой постановке проблема поиска кратчайшей системы дорог, связывающей все имеющиеся объекты, существенно усложняется.
Данный алгоритм в общем случае не существует. Евклидова задача Штейнера является нерешенной с вычислительной точки зрения, поскольку существующие точные алгоритмы находят решение за разумное время только при очень небольшом количестве вершин (порядка 10).
Анализ сложности: Возрастание сложности связано с потерей дискретности, поскольку расположение перекрестков уже не совпадает с самими объектами, и строго говоря, на площади в 1 кв. м. существует бесконечное количество возможных мест расположения развилок. Очевидно, что в общем случае теория графов уже не может давать достоверного результата при решении этой задачи. В настоящее время неизвестно точных и эффективных алгоритмов, решающих эту задачу в том случае, если города заданы произвольной сетью.
Постановка Задачи Штейнера
На плоскости задано N точек. Требуется соединить эти точки ломаными линиями таким образом, чтобы каждая точка была соединена с каждой и чтобы суммарная длина всех проведенных линий была минимальной
Довольно быстро было установлено, что задача достаточно сложная. В 1977 г. Р.Грехем и Д.Джонсон доказали NP – полноту этой задачи, поэтому метода нахождения точного минимума не существует даже на данный момент.
Это обстоятельство послужило стимулом для разработки многочисленных эвристических алгоритмов. Наибольший практический интерес представляет алгоритм последовательного введения дополнительных вершин в дерево Прима-Краскала.
Использование предложенного алгоритма позволяет строить деревья Штейнера, длина которых в среднем не превышает длину оптимального дерева Штейнера более чем на 0.5 процента. Временные характеристики модификаций алгоритма позволяют успешно использовать его на данном этапе построения маршрута.
Глава 3. Задача Штейнера и методы её решения
Задача Штейнера состоит в поиске минимального дерева Штейнера —кратчайшей сети, соединяющей заданный конечный набор точек плоскости.
Свое название получила в честь Якоба Штейнера (1796—1863). Для трех точек на плоскости она формулируется следующим образом: в заданном треугольнике нужно найти точку на плоскости, сумма расстояний от которой до вершин этого треугольника наименьшая.
В задаче Штейнера допускается при необходимости введение новых вершин дерева, отличных от заданных. Эти вершины называют точками Штейнера.
Хорошо известны достаточные условия: в решение могут входить промежуточные точки, и все соединения должны быть отрезками, соединяющими точки (исходные и промежуточные). В каждой промежуточной точке должны сходиться три отрезка, а в исходных точках – более трех. Угол между отрезками, сходящимися в данной точке, не должен быть меньше 120°. Основное внимание следует уделять поиску абсолютно минимальной сети среди всех имеющихся сетей, использующих фиксированное конечное множество N точек плоскости. Существует несколько подходов к указанной проблеме Штейнера.
Один из них предполагает поиск абсолютно минимальной сети в классе сетей, все вершины которых принадлежат N. В этом случае минимальная сеть является деревом (не имеет циклов), которое называется минимальным деревом. Э. Гилберт и Г. Поллак показали, что дерево Штейнера не более чем на 13,4% короче минимального остовного дерева.
Однако, как было доказано группой ученых, эта проблема является NP трудной. Это означает, что нахождение ее решения за полиномиальное время затруднительно. По мнению М. Херринга, текущим наиболее оптимальным и интересным алгоритмом, решающим задачу Штейнера, является алгоритм GeoSteiner до 2 000 точек, реализованный Д. Вармом, П. Винтером и М. Захариасеном.
Наиболее простой задачей является задача нахождения точки Штейнера для трех точек (трехточечная задача Штейнера). Существуют следующие варианты решения данной задачи.
1. Если каждый из углов между отрезками, соединяющий точку Штейнера с каждой из заданныхточек (вершин треугольника), составляет 120°, тогда точка Штейнера либо лежит внутри данного треугольника, либо совпадает с одной из этих вершин.
2. Угол, образованный отрезками, соединяющими эту точку с другими заданными, равен или больше 120°. Если же один из углов треугольника с вершинами в этих точках больше или равен 120°, то сеть состоит из 2 ребер (сторон этого угла). Если все углы меньше 120°, т.е. точка Штейнера состоит из 3 ребер, соединяющих дополнительную точку Штейнера с тремя вершинами.
Указанный алгоритм решения трехточечной задачи Штейнера рассмотрен на примере строительства нового дорожного участка автомобильной дороги «Автомобильная дорога Р-16 Тюхиничи — Высокое — граница Республики Польша (Песчатка), км20,000 —км 41,000»
Глава 4. Задачи
Задача 1
Для трех коллинеарных терминалов решением задачи будет отрезок, соединяющий два крайних терминала.
Как изменится решение, если терминалы слегка «подвигать», чтобы они стали неколлинеарными? — Интуитивно ожидаемый ответ: решение должно слегка измениться, т.е. из отрезка превратиться в ломаную, соединяющую крайние терминалы с «внутренним». Пусть этим внутренним терминалом является P2
Увеличим величину его отклонения от прямой P3 т.е.уменьшим величину угла P1P2P3. Можно ли ожидать, что минимальное дерево Штейнера останется совпадающим с ломаной P1P2P3 — Оказывается, что это заключение справедливо только до определенного значения угла P1P2P3, а именно до тех пор, пока он остается
Что происходит с решением при переходе этого значения? — Оказывается минимум длины обеспечивается теперь принципиально иной конфигурацией: не ломаной P1P2P3, а трехзвенной конструкцией, в которой терминалы связываются посредством некоторой вспомогательной, «узловой», точки S, расположенной внутри терминального треугольника.
Эта точка называется точкой Ферма-Торричелли треугольника P1P2P3 и она формально определяется именно как точка треугольника, обеспечивающая минимальное значение величин.
|P1P| + |P2P| + |P3P|
Где P — произвольная точка треугольника.
Выяснение свойств точки Ферма-Торричелли и способы ее нахождения излагаются в следующих пунктах. А пока, забегая вперед, ответим на ожидаемый вопрос: если добавление одной дополнительной точки оптимизирует решение построения кратчайшей сети, соединяющей три терминала, то, возможно, добавление двух (или более) дополнительных даст еще бóльшую выгоду? — Ответ оказывается отрицательным.
Задача 2
Для решения задачи строительства автомобильной дороги «Автомобильная дорога Р-16 Тюхиничи — Высокое — граница Республики Польша (Песчатка), км20,000 —км41,000» использовалась трехточечная задача Штейнера. Часть автомобильной дороги Р-16 «Граница Республики Польша (Песчатка) – Волковичи» уже реконструирована. Поэтому необходимо было соединить сетью дорог только три точки: д. Волковичи, г. Высокое, автомобильная дорога Р-16 Тюхиничи. Строение местного рельефа определяется расположением ее в пределах Восточно-Европейской равнины. Рельеф территории представляет собой слабо приподнятую, слегка волнистую, наклоненную на север и запад равнину. Такие свойства территории позволяют рассматривать ее как однородную.
В настоящий момент населенные пункты соединены между собой дорогой, суммарная длина которой составляет 8,8 км, по данным карт Яндекс. Карты. Предлагается рассмотреть возможность соединения указанных населенных пунктов другой, более короткой дорогой.
Так как все углы треугольника АВС, вершины которого находятся в данных населенных пунктах, меньше 120, то точка Штейнера лежит внутри треугольника ABC. Для ее нахождения воспользуемся следующим алгоритмом.
Шаг 1. На одной из сторон треугольника ABC построим равносторонний треугольник. Например, возьмем сторону BC и строим равносторонний треугольник BCD, причем точка A не принадлежит этому треугольнику.
Шаг 2. Опишем вокруг треугольника BCD окружность.
Шаг 3. Найдем точку Штейнера (Т) как точку пересечения описанной окружности с отрезком AD.
Для соединения автомобильной дорогой д. Волковичи, г. Высокое и автомобильная дорога Р-16 Тюхиничи взяли следующие точки: д. Волковичи(точка K), д. Оберовщина (точка M), поворот на д. Мыкшицы со стороны г.
Высокое (В), г. Высокое (точка А) и автомобильная дорога Р-16 Тюхиничи (С).
При нахождении точки Штейнера треугольника АВС были выполнены следующие построения:
Шаг 1. На стороне ВС треугольника ABC построили равносторонний треугольник, причем точка A не принадлежит этому треугольнику. Для этого провели дуги радиуса ВС из каждой точки В и С. Точку пересечения дуг обозначили точкой D. Получился треугольник BCD.
Шаг 2. Для нахождения центра окружности, проходящейчерез точки B, С и D построили серединные перпендикуляры сторон треугольника ВСD. Точкапересечения данных серединных перпендикуляров О – центр искомой окружности.
Шаг 3. Вокруг треугольника BCD описали окружность с центром в точке О и радиусом ОD (Рис. 1)
Шаг 4. Для нахождения точки Штейнера нашли точку пересечения
описанной окружности с отрезком AD. Искомая точка Т является точкой Штейнера (Рис. 2).
Шаг 5. Соединив точки В, Т и С получим минимальный путь между населенными пунктами д. Оберовщина, г. Высокое и автомобильная дорога Р-16 Тюхиничи.
Так как часть дороги ТС проходит на местности по пойме реки Пульва и является заболоченной местностью, то строительство такой дороги является нецелесообразным. Изменим направление оптимальногопути без изменения его протяженности.
Шаг 6. Проведем через точки В и С прямую – ось симметрии.
Шаг 7. Относительно оси симметрии ВС построим точку Т` симметричную точке Т. Длина ломанной ВТ`С равна длине ломанной ВТС (Рис. 3).
На местности отрезок ВТ` является частью существующей дороги, соединяющей д. Оберовщина и д. Мыкшицы.
В треугольнике KMB градусная мера угла KMB оказалась равна больше 120, поэтому точка Штейнера при совпадет с точкой M, и кратчайший путь будет представлять собой ломанную KMB. Изменим направление пути, не изменяя длину пути. Для этого построим точку Т`` симметричную точке Mотносительно прямой BK.
Соединив последовательно точки K, Т``, B, Т` и С получим необходимый минимальный путь между точками: д. Волковичи, г. Высокое, автомобильная дорога Р-16 Тюхиничи (Рис. 4)
Заключение
Данная работа помогла понять мне, что такое сети Штейнера. Дала понимание, как можно решать задачи с использованием сетей, дерева, а также с алгоритмом Штейнера. Научная работа помогла разобраться в задачах и различных методах решения их. Работа очень познавательна, интересна и полезна ученикам средней школы.
Данную работу можно использовать для проведения кружков и дополнительных занятий. Такие задания развивают логическое мышление, могут встречаться в олимпиадах.
Источники
https://ru.wikipedia.org/
http://vmath.ru/
https://dic.academic.ru/
https://testmf.grsu.by/
https://habr.com
http://lmatrix.ru