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

Хотя для очень маленьких задач и полиномиальные, и экспоненциальные алгоритмы достаточно практичны, для больших задач время решения у экспоненциальных алгоритмов настолько велико, что практически они оказываются безнадёжными (см. H. Lewis, C. Papadimitriou. The Efficiency of Algorithms, Scientific American, January, 1978). Для достаточно больших задач полиномиальный алгоритм, выполняющийся даже на самой медленной машине, даёт решение всё-таки значительно быстрее, чем экспоненциальный алгоритм, выполняющийся на суперкомпьютере.

Хотя для задачи Штейнера были найдены экспоненциальные алгоритмы (например, алгоритм Мелзака), ни одного полиномиального алгоритма найти для неё не удалось. И шансы на то, что эффективный алгоритм будет когда-нибудь найден, очень малы. В 1971 году С. Кук из Университета в Торонто доказал, что если будет найден полиномиальный алгоритм для любой задачи, принадлежащей классу труднорешаемых задач, называемых NP-полными, то этим же алгоритмом можно будет воспользоваться для эффективного решения широкого класса труднорешаемых задач, включая класс NP-полных. Позже один из авторов настоящей статьи (Грэм), работая совместно с М. Гэри и Д. жонсоном из AT&T Bell Laboratories, доказал, что задача Штейнера относится к классу NP-полных. Поскольку до сегодняшнего дня все NP-полные задачи оказались не по силам тысячам исследователей, то маловероятно, чтобы какая-нибудь NP-полная задача, в том числе и задачи Штейнера, была решена алгоритмом с полиномиальным временем. Однако доказательство того, что NP-полные задачи невозможно решить эффективным способом, остаётся одной из основных теоретических проблем вычислительной математики.

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

Е. Гилберт и X. Поллак высказали предположение о том, что отношение длины кратчайшего дерева Штейнера к длине минимального остовного дерева равно, самое меньшее, √3/2, т.е. дерево Штейнера не более чем на 13, 4% короче минимального остовного дерева. Это отношение √3/2 возникает в простом примере, когда три исходные точки являются вершинами равностороннего треугольника. Хотя это предположение остаётся недоказанным, Чанг и один из авторов данной статьи (Грэм) показали, что дерево Штейнера короче минимального остовного дерева не более чем на 17, 6%.

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

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

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

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

Такая задача, получившая название прямоугольной задачи Штейнера, была впервые изучена в 1965 году Морисом Хэнаном из Исследовательского центра им. Томаса Уотсона корпорации IBM в Йорктаун-Хейтсе (шт. Нью-Йорк). Как и в классической задаче Штейнера, решение для прямоугольной её версии также содержит точки Штейнера и исходные точки, но рёбра встречаются в них под углом либо 90°, либо 180°. Хотя точки Штейнера могут, казалось бы, лежать повсеместно в прямоугольной задаче, так же как и в классической задаче Штейнера, Хэнан показал, что в кратчайшей прямоугольной сети на расположение точек Штейнера можно наложить определённые ограничения. Через каждую исходную точку проводятся горизонтальная и вертикальная прямые, и каждое пересечение двух линий даёт возможное положение точки Штейнера. Чтобы найти кратчайшую сеть, алгоритм может рассмотреть все подмножества возможных точек Штейнера. Однако по мере того, как число исходных точек возрастает, время решения для каждого алгоритма, осуществляющего полный перебор вариантов, растёт экспоненциально. Более тонкие, но всё же экспоненциальные алгоритмы способны решать прямоугольные задачи Штейнера размером порядка 40 точек.

Прямоугольная версия задачи поиска минимального остовного дерева может быть эффективно решена алгоритмом, выбирающим на каждом шаге кратчайшее соединение, если это соединение не образует замкнутого пути. Ф. Хванг из фирмы Bell Laboratories показал, что прямоугольное дерево Штейнера не бывает короче прямоугольного остовного дерева более чем на одну треть.

Наиболее удивительное применение задача Штейнера нашла в биологии, в одной из областей, изучающей происхождение видов. Д. Сэнкофф из Монреальского университета и ряд других исследователей сформулировали одну из версий задачи Штейнера для того, чтобы вычислять наиболее вероятные филогенетические деревья. Учёные сначала изолируют какой-то определённый белок, общий для организмов, которые они намереваются классифицировать. Затем для каждого организма они определяют последовательность аминокислот, составляющих этот белок, и устанавливают точку в позиции, определяемой числом различий между белком соответствующего организма и белком других организмов. Организмы с похожими последовательностями аминокислот определяются, таким образом, как близкие, а организмы с непохожими последовательностями — как далёкие. В кратчайшей сети для этого абстрактного множества исходных точек точки Штейнера соответствуют наиболее вероятным предкам, а рёбра представляют связь между данным организмом и предком, обладающую наименьшим числом мутаций. Однако, поскольку филогенетическая задача Штейнера не легче других задач подобного рода, эта задача — за исключением случаев с небольшим числом организмов — послужила скорее в качестве мысленного эксперимента, нежели практического инструмента исследований.

Хотя за последние годы наши познания в области алгоритмов значительно расширились, задача поиска кратчайшей сети остаётся всё такой же неприступной. Несмотря на то что формулировка этой задачи очень проста, её решения трудно поддаются анализу. Крошечное изменение геометрии задачи, кажущееся несущественным, может коренным образом изменить кратчайшую сеть, являющуюся её решением. Такая чувствительность к исходным данным делает даже периферийные вопросы, касающиеся кратчайших сетей, весьма не простыми. Задача поиска кратчайшей сети будет ещё долгие годы привлекать наше воображение.

Список литературы

1. E. N. Gilbert and H. О. Pollak. Steiner Minimal Trees. In: SIAM Journal on Applied Mathematics, 1968, v. 16, No 1, pp. 1–29.

2. Z. A. Melzak. Companion to Concrete Mathematics. John Wiley & Sons, Inc., 1973.

3. Pawel Winter. An Algorithm for the Steiner Problem in the Euclidean Plane. In: Networks, 1985, v. 15, No 3, pp. 323–345.

4. Pawel Winter. Steiner Problem in Networks: A Survey. In: Networks, 1987, v. 17, No 2, pp. 129–167.

5. М. Гэри, Д. Джонсон. Вычислительные машины и труднорешаемые задачи. — Перев. с англ. М.: Мир, 1982.