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

Рассмотрим для примера множество исходных точек, образующих четыре угла прямоугольника, размерами три метра на четыре. Решения содержат две точки Штейнера, которые можно расположить двумя различными способами. При каждом расположении мы получаем дерево Штейнера, причём в каждой точке Штейнера сходятся по три ребра под углом 120°. Если точки Штейнера расположить на линии, параллельной поперечной стороне прямоугольника, то получается локально минимальное дерево Штейнера длиной 9, 9 м. Если расположить точки Штейнера на линии, параллельной продольной стороне прямоугольника, то получится глобально минимальное дерево длиной 9, 2 м.

Действуя методом полного перебора, можно найти кратчайшую сеть путём построения всех возможных локально минимальных деревьев Штейнера, вычислением их длины и выбором кратчайшего. Но поскольку расположение точек Штейнера неоднозначно, возникает сомнение в том, что вычислить все локально минимальные деревья Штейнера можно за конечное время. З. Мелзак из Университета Британской Колумбии сумел преодолеть это затруднение и составил первый алгоритм для решения задачи Штейнера.

В алгоритме Мелзака рассматриваются многие возможные соединения между заданными точками и многие возможные расположения точек Штейнера. Алгоритм можно условно разбить на две части. В первой его части множество исходных точек просто подразделяется на всевозможные подмножества. Во второй части для каждого такого подмножества создается ряд возможных деревьев Штейнера с использованием построения, аналогичного тому, которое мы применили к задаче с тремя точками.

Так же как и для трёх точек, вместо двух исходных точек можно подставить одну заменяющую их точку, не изменяя результата (длины сети) решения. Однако в общем случае алгоритм должен угадать, какую пару следует заменить, и поэтому он перебирает все возможные пары. Более того, заменяющая точка может размещаться по любую сторону от прямой, соединяющей две заменяемые точки, поскольку равносторонний треугольник, используемый при построении, может быть ориентирован в одном из двух направлений. После того как одна из точек в подмножестве заменена одной из двух возможных заменяющих точек, на каждом последующем шаге алгоритма замещаются либо две другие исходные точки, либо одна исходная и одна замещающая, либо две замещающие другой замещающей точкой; и так до тех пор, пока всё подмножество не будет сведено к трём точкам.

Как только для этих трёх точек найдена точка Штейнера, алгоритм начинает работать в обратном направлении, пытаясь определить точку Штейнера, соответствующую каждой замещающей точке (см. рис.).

Алгоритм Мелзака разбивает задачу поиска кратчайшей сети на подзадачи. Точка A подходит для разбиения задачи на подзадачи из 3 и 5 точек. Чтобы построить возможные деревья Штейнера для 5 точек, пару точек (например, B и C) можно заменить одной (здесь X), построив равносторонний треугольник с основанием BC. Теперь задача сведена к 4 точкам: X, D, G и A. Пару точек опять можно заменить — сначала D и X на Y, а потом G и A на Z. Вокруг каждого из полученных равносторонних треугольников (XDY, AGZ и BCX) описываем окружности. Точки Q и R, в которых прямая YZ пересекает две окружности, — это точки Штейнера, а пересечение прямой XQ с третьей окружностью определяет точку Штейнера P. Поскольку невозможно заранее предугадать наилучшее разбиение на подзадачи и группировки на пары, необходимо рассмотреть все варианты, чтобы найти кратчайшее дерево.

Попытка может окончиться неудачей, поскольку на расположение точек Штейнера накладываются противоречащие друг другу ограничения. Однако успешная попытка приводит к возникновению дерева Штейнера, соединяющего каждую исходную точку подмножества с деревом одним ребром. Рассмотрев, таким образом, все замещающие последовательности, алгоритм выбирает кратчайшее из этих деревьев Штейнера для подмножества. Комбинируя между собой всевозможными способами кратчайшие деревья Штейнера для подмножеств так, чтобы охватить исходное множество точек, можно построить всевозможные локально минимальные деревья Штейнера и определить геометрию кратчайшей сети.

Алгоритм Мелзака может потребовать колоссального времени даже для небольших задач, поскольку в нём рассматривается очень много вариантов. Например, задача для 10 точек может быть распределена на 512 подмножеств исходных точек. И хотя двухточечные подмножества не требуют большого объёма работы, каждое из 45 подмножеств с восемью точками имеет два миллиона замещающих последовательностей. Кроме того, существуют ещё более 18 000 способов объединить эти подмножества в деревья.

Разумеется, исследователи нашли более эффективные пути организации вычислений и сумели повысить быстродействие алгоритма. Вместо того чтобы рассматривать геометрию задачи, они фокусируют внимание на возможных конфигурациях соединений в сети, т.е. на её топологии. Топология указывает, какие точки соединены друг с другом, а не действительные расположения точек Штейнера. Приняв определённую топологию, можно найти соответствующую замещающую цепочку относительно быстро. При такой организации процесса скорость вычисления кратчайших деревьев Штейнера для подмножеств немного возрастает. Например, для подмножества из 8 точек алгоритм должен рассмотреть лишь около 10 000 различных топологий вместо двух миллионов различных последовательностей замещения.

Так как количество возможных топологий быстро возрастает с размером подмножества, задачи Штейнера могут стать менее трудоёмкими лишь в том случае, если требуется рассматривать только очень небольшие подмножества исходного множества точек. Эксперименты, проведённые с алгоритмом Мелзака, показали, что кратчайшая сеть для числа случайных точек больше 6 обычно может быть разбита на кратчайшие сети для меньших наборов точек. Однако, рассмотрев специальные конфигурации точек, называемые лестницами, Ф. Чанг из фирмы Bell Communications Research совместно с одним из авторов настоящей статьи (Грэмом) показал, что существуют бесконечно большие множества точек, для которых кратчайшее дерево Штейнера невозможно расчленить. Лестница — это конфигурация, в которой исходные точки расположены равномерно вдоль двух параллельных линий. Для этой весьма частной задачи Штейнера было найдено общее решение. Оно показало, что число точек Штейнера в кратчайшем дереве Штейнера для лестницы с нечётным количеством «ступенек» максимально: оно равно числу исходных точек минус 2. Такое дерево Штейнера невозможно расчленить, потому что для каждой точки Штейнера нужно одновременно учитывать все исходные точки. Следовательно, не всегда можно сократить размер подмножеств, рассматриваемых алгоритмом Мелзака.

Некоторым исследователям удалось улучшить эффективность алгоритмов по сравнению с алгоритмом Мелзака за счёт применения более тонких способов, позволяющих уменьшить объём вычислений (см. рис.).

Методы усечения повышают эффективность алгоритмов поиска кратчайших сетей. Один из приёмов усечения, или исключения, возможных сетей (изобретённый Кокейном) заключается в том, чтобы рассмотреть порядок, в котором резиновое кольцо (красный цвет), натянутое вокруг заданного множества точек, касается их. Резинка касается всех точек, за исключением C и H, но C можно включить в последовательность, поскольку угол, образуемый точкой C с двумя соседними точками, находящимися в контакте с резинкой, не меньше 120°. Тогда порядок точек будет ABCDEFG. Непрерывный путь (чёрный цвет), проходящий вдоль возможной сети (синий цвет), касается точек в порядке ACBDEFHG. Поскольку B и C здесь переставлены местами по отношению к последовательности, образованной резинкой, эту сеть можно исключить из рассмотрения.

В их алгоритмах производится усечение вычислительной процедуры, т.е. прекращаются те ветви вычисления, которые заведомо должны привести к сравнительно длинным сетям. Новые методы усечения действительно значительно сокращают объём вычислений. Программы, основанные на алгоритме Мелзака, как, скажем, программа Э. Кокейна из Университета Виктории, написанная в 1969 году, могли решить любую задачу для 9 точек и некоторые задачи для 12 точек приблизительно за полчаса. Программа же, недавно написанная Кокейном и его коллегой из Университета Виктории Д. Хьюджиллом, использует мощный метод усечения, изобретённый Р. Винтером из Копенгагенского университета. Эта программа смогла решить все задачи для 17 точек и большинство случайно сгенерированных задач для 30 точек всего за несколько минут. Метод усечения Винтера оказался настолько удачным, что благодаря устранению большинства возможных топологий, основной объём вычислительной работы связан с комбинированием решений, полученных для отдельных подмножеств.

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

Прогресс, достигнутый в теории вычислительной математики, убедил большинство исследователей, что существующие алгоритмы решения задачи Штейнера практически невозможно улучшить. В этой теории каждой задаче сопоставляется определённый размер. Для каждого конкретного случая задачи Штейнера таким естественным размером является число заданных исходных точек. Затем рассматривается количество элементарных компьютерных операций — таких как сложение, вычитание и умножение, — которое может потребоваться алгоритму для решения какого-то частного случая задачи определённого размера. Поскольку различные частные случаи одного и того же размера могут потребовать различного количества операций, следует рассматривать максимальное количество операций как функцию размера задачи. Если число операций растет с размером задачи (n) пропорционально некоторой степени размера, например, как в выражениях n2, 5n или 6n + n10, то процедура решения называется алгоритмом с полиномиальным временем, или просто полиномиальным алгоритмом. Такие алгоритмы считаются эффективными, по крайней мере в теоретическом смысле. Если же количество операций возрастает экспоненциально с размером задачи, как, например, в случаях 2n, 5n или 3n2·4n, процедура решения называется алгоритмом с экспоненциальным временем или просто экспоненциальным алгоритмом.