Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Эвклидово дерево MST
|
|
Предположим, что даны N точек на плоскости, и мы хотим найти кратчайший набор линий, соединяющих все эти точки. Эта геометрическая задача называется задачей поиска эвклидова дерева MST (Euclidian MST) (см. рис. 20.18). Один из подходов к ее решению предусматривает построение полного графа с N вершинами и N(N- l)/2 ребрами - одно ребро соединяет каждую пару вершин, а вес этого ребра равен расстоянию между соответствующими точками. Затем мы можем при помощи алгоритма Прима найти дерево MST за время, пропорциональное N2.
В общем случае для этого решения характерно низкое быстродействие. Эвклидова задача несколько отличается от задач на графах, которые мы рассматривали выше, поскольку все ребра определены неявно. Объем входных данных пропорционален N, так что решение, которое мы наметили для этой задачи в первом приближении, есть квадратичный алгоритм. Исследования показывают, что можно несколько улучшить этот показатель. Из рассматриваемой геометрической структуры следует, что большая часть ребер в полном графе не будет использоваться при решении задачи, и нет необходимости включать в граф большую часть этих ребер, прежде чем мы построим минимальное остовное дерево (дерево MST).
Свойство 20.13. Мы можем отыскать эвклидово дерево MST для N точек за время, пропорциональное N logN.
Этот факт представляет собой прямое следствие двух важных фактов, касающихся точек на плоскости, которые мы будем рассматривать в части 7. Во-первых, граф, известный как триангуляция Делони (Delauney triangulation), содержит дерево MST по определению. Во-вторых, триангуляция Делони есть планарный граф, число ребер которого пропорционально N. ■
РИСУНОК 20.18. ЭВКЛИДОВО ДЕРЕВО MST
Пусть задано множество N точек на плоскости (вверху), тогда эвклидово дерево MST есть кратчайшее множество линий, которые их соединяют (внизу). Эта задача выходит далеко за рамки задач обработки графов, поскольку нам придется использовать глобальную информацию геометрического характера о точках на плоскости, дабы избежать необходимости обработки всех N2 неявных ребер, соединяющих эти точки.
Глава 20» Минимальные остовные деревья
| сматриваемом случае существует простая нижняя граница наших возможностей. Свойство 20.14. Вычислить эвклидово дерево MST для N точек не проще, чем сортировка N чисел. Доказательство: Пусть задан список чисел, подлежащих сортировке, преобразуем этот список в список точек, в котором в качестве координаты х берется соответствующее число из списка чисел, а координата у принимается равной 0. Требуется найти дерево MST для построенного списка точек. Далее (как и в случае алгоритма Крускала) поместите точки в АТД графа и выполните поиск в глубину с целью построения остовного дерева, начиная с точки с минимальной координатой х. Это основное дерево представлено в виде связного списка упорядоченных чисел; таким образом, мы решили задачу сортировки чисел. ■ |
В принципе, мы можем вычислить триангуляцию Делони за время, пропорциональное N logN, затем либо прогнать алгоритм Крускала, либо метод поиска по приоритету с целью вычисления эвклидового дерева MST за время, пропорциональное TV logN. Однако написание программы, вычисляющей триангуляцию Делони — задача не из легких даже для опытного программиста, так что в силу сказанного выше подобный подход может оказаться слишком убийственным для решения таких задач на практике.
Другие подходы вытекают из геометрических алгоритмов, которые будут рассматриваться в части 7. Для случайно распределенных точек мы можем поделить плоскость на квадраты таким образом, чтобы каждый квадрат содержал примерно lgN/2 точек, что мы и делали в программе 3.20, осуществляющей поиск ближайшей точки. Далее, даже если мы включаем в граф только ребра, соединяющие каждую точку с точками из соседних квадратов, то, по-видимому (но отнюдь не обязательно), все эти ребра окажутся в минимальном остовном дереве; в этом случае мы можем воспользоваться алгоритмом Крускала или реализацией алгоритма Прима с поиском по приоритету, чтобы не снижать производительность на завершающей стадии вычислений. Примеры, который мы использовали на рис. 20.10, рис. 20.13 и рис. 20.16 и других подобных рисунках, были построены с использованием именно этого способа (рис. 20.19). Мы можем разработать новую версию алгоритма Прима на базе алгоритмов поиска ближайшего соседа, чтобы не обрабатывать отдаленные вершины.
Имея в своем распоряжении богатый выбор подходов к решению этой задачи и возможности линейных алгоритмов для решения в общем виде задачи отыскания дерева MST, важно отметить, что в рас-
РИСУНОК 20.19. ЭВКЛИДОВЫ ГРАФЫ БЛИЖАЙШИХ СОСЕДЕЙ
Один из способов вычисления эвклидового дерева MST состоит в построении графа, в котором каждое ребро соединяет каждую пару точек, расположенных друг от друга на расстоянии, не превышающем d, подобно графу, изображенному на рис. 20.8 и на ряде других. Тем не менее, этот метод дает слишком много ребер, если расстояние d достаточно велико (диаграмма вверху), при этом нет гарантии того, что существуют все ребра, соединяющие все точки, если d меньше длины самого длинного ребра в дереве MST(диаграмма внизу).