Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
') Авторы благодарны Стефану Барру, сообщившему эту информацию.
230
Гл. 5. Близость: основные алгоритмы
Этот закон представляет «Соломонов компромисс» между тем, что требуется вычислять, и тем, что вычисляется на практике, так как минимальное остовное дерево не соответствует наикратчайшей из возможных сетей, соединяющих заданные точки, при условии, что к исходному множеству не запрещено добавлять новые точки. Если такое ограничение действительно отсутствует, то дерево, имеющее наикратчайшую длину, называется деревом Штейнера (рис. 5.3) ').
Как было показано Гэри, Грэхемом и Джонсоном [Garey, Graham, Johnson (1976)], задача построения дерева Штейнера является ЛФ-трудной, и, используя современные средства, мы
Рис. 5.3. Суммарная длина ребер дерева Штейнера (Ь) может быть меньше, чем у МОД (а).
не в состоянии решать задачи более чем для 20—25 точек. Поэтому неразумно требовать, чтобы тариф за использование линий связи вычислялся в соответствии с деревом Штейнера.
Минимальное остовное дерево используется при кластеризации [Cower, Ross (1969), Johnson (1967), Zahn (1971)], при вычислении характерной размерности множеств точек [Schwartz-mann, Vida] (1975)] и при распознавании образов [Osteen, Lin (1974)]. Оно также использовалось для минимизации длины проводников при компоновке электрической схемы ЭВМ [Lober-mann, Weinberger (1957)]. Минимальное остовное дерево дает начальное приближение для многих алгоритмов решения задачи о коммивояжере, которая обсуждается в разд. 6.1.
Задача о минимальном остовном дереве обычно формулируется как задача теории графов: задан взвешенный граф с N вершинами и Е ребрами, требуется найти кратчайшее поддерево графа G, включающее все его вершины. Эта задача независимо была решена Дейкстрой [Dijkstra (1959)], Краскалом [Kruskal (1956)] и Примом [Prim (1957)], а существование полиномиального алгоритма (который был представлен каждым из них) является в значительной степени неожиданным, так как граф с N вершинами может иметь N"-2 остовных деревьев [Moon (1967)] 2). В попытке найти быстрый алгоритм для этой
') Дерево Штейнера на рис. 5.3 взято из работы [Melzak (1973)]. 2) Впервые это было доказано Кэли в 1889 г.
$.1. Набор задач
общей задачи было затрачено много усилий [Nijenhuis, Will (1975), Yao (1975)] и лучший на сегодняшний день результат состоит в том, что задача может быть решена за время 0(E), если Е > [Cheriton, Tarjan (1976)]. (См. также разд. 6.1.)
В случае евклидовой задачи о минимальном остовном дереве N вершин определяются 2N координатами точек на плоскости, а соответствующий граф содержит ребра, соединяющие каждую пару вершин. Вес ребра равен расстоянию между точками, соединяемыми ребром. В этом случае использование лучшего из известных алгоритмов решения задачи о МОД потребует времени 6 (Е) = 6 (N2). И так как МОД всегда содержит самое короткое ребро графа G1), то легко доказать, что приведенное значение является нижней оценкой для произвольного графа. Действительно, так как в произвольном графе значения весов ребер ничем не ограничены, то алгоритм решения задачи о МОД, требующий времени меньше 0(N2), мог бы быть использован для поиска минимума среди N2 значений за время 0(N2), что невозможно. Из этого следует, что любой алгоритм, рассматривающий решение задачи о евклидовом минимальном остовном дереве как выделение минимального остовного дерева в полном графе с N вершинами, с необходимостью имеет квадратичную сложность по времени. Какие же соображения заставляют нас предполагать, что для решения задачи достаточно меньшего времени? Прежде всего, евклидов вариант задачи о МОД имеет лишь 2N входных величин (координат точек), в то время как в случае произвольного графа имеется N(N — 1)/2 входных величин (длин ребер). Таким образом, евклидов вариант задачи содержит сильные ограничения по сравнению с общим случаем, и при разработке быстрого алгоритма можно было бы использовать метрические свойства.
Задача Б.4 (ТРИАНГУЛЯЦИЯ). На плоскости заданы JVточек. Соединить их непересекающимися отрезками таким образом, чтобы каждая область внутри выпуклой оболочки этого множества точек являлась треугольником. (См. разд. 1.3.1.)
Граф триангуляции множества из N точек, являясь планарным, имеет не более 3N — 6 ребер. Результатом решения сформулированной выше задачи должен быть по крайней мере список этих ребер. На рис. 5.4 приведен пример триангуляции.
Задача триангуляции возникает в методе конечных элементов {Strang, Fix (1973); Cavendish (1974)] и при интерполяции функции от двух переменных, когда заданы значения функции в N произвольным образом расположенных точках (xi, г/,) и требуется аппроксимировать ее в некоторой новой точке (х, у).
') Это показали Краскал и Прим.
232 Гл. 5. Близость основные алгоритмы
Один из возможных подходов основывается на кусочно-линейной интерполяции, при которой поверхность, определяемая функцией, аппроксимируется «сетью», состоящей из плоских треугольных граней. Проекция каждой точки (х, у) принадлежит лишь одной из треугольных граней, и соответствующее значение функции f(x, у) вычисляется в результате определения интерполирующей плоскости, проходящей через три вершины грани. Процесс триангуляции заключается в выборе троек точек, которые и будут образовывать грани. Для определения «качества» получаемой триангуляции было предложено немало критериев [George (1971)], включающих, в частности, максимизацию наименьшего угла или минимизацию полной длины ребер. Выбор указанных условий объясняется их удобством для получения оценки ошибки интерполяции, а не тем, что они позволяют получить наилучшую триангуляцию. Рис. 5.4. триангуляция множества Все четыре предшествующие точек. задачи (Б.1—Б.4) относятся к
