Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
284
Гл. 6. Близость: варианты и обобщения
дено за полиномиальное время, а Габоу [Gabow (1972)] разработал алгоритм со сложностью 0(N3). Следующий результат, полученный Кристофидесом [Christofides (1976)], связывает минимальные остовные деревья, паросочетания и задачу о коммивояжере.
Теорема 6.3. Если расстояния между точками удовлетворяют неравенству треугольника, то за время 0(N3) можно найти приближенное решение задачи о коммивояжере, представляющее
Рис. 6.6. Минимальное евклидово паросочетание.
маршрут, длина которого не превосходит 3/2 длины минимального маршрута.
Доказательство. Пусть задано множество точек 5. Следующий алгоритм соответствует условиям теоремы и дает необходимый результат.
1. Найти минимальное остовное дерево Т* множества 5.
2. Найти минимальное евклидово паросочетание М* для множества X ^ S вершин, имеющих нечетную степень в Т*. (Множество X всегда содержит четное число элементов для любого графа.)
3. Граф Т* U М* является эйлеровым, так как все его вершины имеют четную степень. Обозначим через Фе эйлеров цикл этого графа.
4. Продвигаясь по Фе от ребра к ребру таким образом, чтобы не проходить вновь уже пройденные вершины, построить приближенный маршрут Фприбл.
Пусть, как обычно, Ф — минимальный маршрут. Заметим, что: (1) длина (Г*) < длина (Ф); (2) длина(Л1*Ху длина (Ф). Действительно, выбрав из Ф каждое второе ребро, получаем два паросочетания на множестве S (к первому относятся отобранные ребра, а ко второму оставшиеся). Длина кратчайшего из двух паросочетаний не превосходит 1/2 длина (Ф) и со всей очевидностью не меньше длина (М*), так как М* — минимальное паросочетание. Ранее было показано, что длина (Т*)< < длина (Ф). И так как расстояния между точками удовлетворяют неравенству треугольника, длина (Фприбл) ^ длина (Фе).
6.2. Планарные триангуляции
285
Объединяя эти результаты, получаем длина (Фприбл.Х длина (Фе)
= длина (7") + длина (М*) < длина (Ф) + у длина (Ф) = -| длина (Ф).
Справедливость временной оценки следует из результата, полученного Габоу.
Замечание. Воспользовавшись минимальным евклидовым паросочетанием, можно получить лучшее приближенное решение, отличающееся от минимального не в 2, а в 3/2 раза. При этом сложность вычислений возрастает с О (N log N) до 0(N3). За несколько лет, прошедших с момента, когда Кристофидес получил свой результат, никому не удалось ни найти способ поиска приближенного решения, отличающегося от минимального менее чем в 3/2 раза, ни уменьшить время поиска приближенного решения. Само по себе примечательно, что метод, используемый для получения минимального евклидова паросочетания, не использует геометрические свойства. Действительно, единственный известный метод заключается в сведении (преобразовании) данной задачи к задаче поиска максимального взвешенного паросочетания (сведение осуществляется путем замены длины / каждого ребра величиной М — /, где М = = max /) и применении к полученной в результате сведе-
по всем ребрам
ния задаче метода, разработанного для произвольных графов.
6.2. Планарные триангуляции
В разд. 5.1 уже отмечалась важность триангуляции для многочисленных приложений, связанных с интерполяцией поверхностей, как в задачах графического отображения данных, так и в задачах численного анализа. В дополнение к этим очень важным приложениям возможность выполнять планарные триангуляции сама по себе является полезным средством, используемым для решения других задач вычислительной геометрии. Достаточно упомянуть два примера: (1) в методе геометрического поиска Киркпатрика (см. разд. 2.2.2.3) предполагается, что планарное разбиение является триангуляцией; (2) алгоритм построения пересечения многогранников (см. разд. 7.3.1) требует выполнить предварительную триангуляцию поверхности многогранников.
В предыдущей главе уже было показано, что триангуляция— а именно триангуляция Делоне — множества точек мо-
Гл. 6. Близость: варианты и обобщения
жет быть найдена за оптимальное время. Однако это не решает проблемы, так как, хотя триангуляция Делоне является замечательным объектом, обладающим очень привлекательными свойствами, могут встретиться приложения, для которых триангуляция Делоне не подходит. Например, может потребоваться минимизировать суммарную длину ребер триангуляции (минимальная взвешенная триангуляция). Было сделано предположение, что триангуляция Делоне также является минимальной взвешенной триангуляцией. Еще в одном предположении утверждалось, что метод триангуляции, который будет описан в разд. 6.2.1 (метод «жадной триангуляции»), также дает минимальную взвешенную триангуляцию. Оба этих утверждения были опровергнуты Ллойдом [Lloyd (1977)], и на сегодня вопрос о сложности задачи построения минимальной взвешенной триангуляции (т. е. является ли она Л^Р-трудной или существует полиномиальный алгоритм для ее решения) остается открытым ]).
Другие критерии не связаны с длиной ребер, а касаются величины внутренних углов треугольников. Во многих приложениях требуется, чтобы треугольники были по возможности «однородными», т. е. были «более или менее равносторонними». С этой точки зрения триангуляция Делоне является очень привлекательной, так как для нее минимальное значение угла по всем треугольникам является максимальным среди всех триангуляции. (Действительно, это эквивалентно тому, что окружность, описанная вокруг треугольника в триангуляции Делоне, не содержит внутри других точек заданного множества [Lawson (1977); Lee (1978)].)
