Поиск кратчайших сетей (стр. 1 из 3)

Маршалл У. Берн, Рональд Л. Грэм

Как найти кратчайшую сеть отрезков прямых линий, соединяющих произвольное множество, скажем из 100, точек? Эта задача не поддаётся ни самым быстродействующим компьютерам, ни самым изобретательным математическим умам

Представим себе такую ситуацию: некая телефонная компании Steiner Telephone Company подсчитала, что можно сэкономить несколько миллионов долларов, если удастся найти кратчайшую из возможных сетей телефонных линий, соединяющих 100 населённых пунктов. Чтобы решить эту задачу, компания заключила контракт с компьютерной компанией Cavalieri Computer Company, располагающей самыми быстродействующими в мире компьютерами и самыми квалифицированными программистами. Через неделю Cavalieri продемонстрировала в действии программу для решения поставленной задачи. Программа действительно нашла кратчайшую сеть для 15 абонентов всего за один час. Steiner заплатила 1000 долл. за программу и пообещала платить по одному центу за каждую секунду машинного времени, которое потребуется компьютеру для полного решения задачи. К тому времени, когда компьютер завершил вычисления для всех 100 абонентов, телефонная компания задолжала компьютерной многие триллионы долларов, а сами абоненты переместились на много километров со своих мест — либо по своему желанию, либо по причине континентального дрейфа!

Может быть, Cavalieri продала Steiner неправильную программу? Попробуем разобраться. Здесь мы столкнулись с одним из примеров так называемой задачи Штейнера, в которой требуется найти кратчайшую сеть прямолинейных отрезков, связывающих между собой заданное множество точек.

Компьютер из мыльной плёнки (вверху) соревнуется с электронным компьютером (внизу), отыскивая кратчайшую сеть, связывающую между собой 29 городов. Компьютер из мыльной плёнки, в котором расположение штырьков моделирует географию городов, минимизирует длину плёночных соединений в локальной области. Он даёт короткую сеть, но необязательно кратчайшую. Электронный компьютер реализует алгоритм Э. Кокейна и Д. Хьюджилла из Университета Виктории. Алгоритм гарантирует кратчайшую сеть. Задача с 29 точками на сегодня близка к пределу вычислительных возможностей.

Задачу Штейнера невозможно решить, просто рисуя линии между заданными точками. Для решения необходимо добавить новые точки, называемые точками Штейнера и служащие в качестве узлов искомой кратчайшей сети. Чтобы определить количество и расположение точек Штейнера, математики и программисты разработали специальные алгоритмы. Однако даже лучшие из этих алгоритмов, выполняющиеся на самых быстродействующих компьютерах, не в состоянии дать решение для большого множества заданных точек за реально приемлемое время. Более того, задача Штейнера принадлежит к классу задач, для которых, по мнению многих современных исследователей, эффективные алгоритмы, по-видимому, так никогда и не будут найдены. Поэтому компьютерная компания Cavalieri должна быть реабилитирована.

В то же время фирма Cavalieri могла бы разработать практически полезную программу, которая находила бы сеть, несколько более длинную по сравнению с кратчайшей. Приближённые методы решения довольно часто применяются в различных приложениях задачи поиска кратчайших сетей. Среди них — конструирование интегральных электронных схем, построение эволюционного дерева для группы биологических видов и минимизация расхода материалов на создание сетей телефонных линий, трубопроводов и шоссейных дорог.

В общей форме задача Штейнера была впервые сформулирована в статье Милоша Кёсслера и Войцеха Ярника, опубликованной в 1934 году, однако сама эта проблема не приобрела широкой известности вплоть до 1941 года, когда Рихард Курант и Герберт Е. Роббинс включили её в свою книгу «Что такое математика?». Курант и Роббинс связали эту задачу с исследованиями Якоба Штейнера, немецкого математика XIX столетия, работавшего в Берлинском университете. Работа Штейнера была посвящена поиску одной точки, сумма расстояний от которой до всех точек заданного множества была бы минимальной. Однако ещё в 1640 году впервые была поставлена задача, являющаяся частным случаем обеих описанных задач — той, над которой работал Штейнер, и той, которая носит его имя: найти точку P, сумма расстояний от которой до каждой из трёх заданных точек минимальна. Эванджелиста Торричелли и Бонавентура Кавальери независимо друг от друга решили эту задачу. Торричелли и Кавальери доказали, чту суммарное расстояние минимально, когда все сопряжённые углы в точке P больше или равны 120°.

Зная, что углы с вершинами в точке P должны быть не меньше 120°, Торричелли и Кавальери придумали процедуру геометрического построения для нахождения точки P (см. рис.).

Кратчайшая сеть для трёх точек A, B и C. На самой длинной стороне треугольника ABC строится равносторонний треугольник ACX (зелёный цвет), и вокруг него описывается окружность (жёлтый цвет). На пересечении её с отрезком BX находится точка P, называемая точкой Штейнера. Отрезки AP, BP и CP образуют три сопряжённых угла по 120° и кратчайшую сеть, причём их суммарная длина равна BX.

Нужно провести отрезки прямых, соединяющие исходные точки (назовем их 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°. В-третьих, число рёбер дерева всегда на единицу меньше суммарного числа заданных исходных точек и точек Штейнера. И наконец, последнее свойство: поскольку в каждой точке Штейнера сходятся ровно три ребра и по крайней мере одно ребро должно касаться каждой из заданного множества точек, максимальное число точек Штейнера для любой задачи на две меньше, чем число заданных исходных точек.

b

c

8

7, 464...

6, 928...

d

e

f

10

9, 928...

9, 196...

g

h

i

10

9, 327...

9, 250...

Задача поиска сети для точек, расположенных в вершинах равностороннего треугольника, прямоугольника и «лестницы» имеет различные решения. В случаях a, d и g точки соединяются без дополнительных промежуточных точек и такое решение называется минимальным остовным деревом. Деревья Штейнера, полученные путём добавления узловых точек, показаны для случаев b, c, e, f, h и i. Только c, f и i являются кратчайшими деревьями Штейнера, или кратчайшими сетями. Числа под каждым решением указывают примерную суммарную длину отрезков сети.