Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Объединяя этот результат с уже известным нам фактом о том, что триангуляция Делоне может быть построена за время е (TV log TV), получаем
Следствие 6.1. ЕМОД множества S из N точек на плоскости может быть построено за оптимальное время Q{N\ogN).
6.1. Евклидовы минимальные остовные деревья
281
На рис. 6.2 показаны множество точек, его диаграмма Вороного и ЕМОД этого множества.
Рис. 6.2. Множество точек и соответствующие ему диаграмма Вороного и ЕМОД.
Далее будет рассмотрено одно интересное приложение ЕМОД конечного множества точек.
6.1.1. Евклидова задача о коммивояжере
Задача Б.9 (ЕВКЛИДОВА ЗАДАЧА О КОММИВОЯЖЕРЕ). Найти кратчайший замкнутый путь, проходящий через N заданных точек на плоскости.
Пример такого кратчайшего маршрута показан на рис. 6.3. (Читатель, представляющий сложность этой задачи, может удивиться тому, как удалось получить решение для приведенного примера, содержащего 16 точек. Это было сделано с помощью
эвристического приема, предло- Рис. 6.3. Маршрут коммивояжера.
женного Кристофидесом, который будет описан далее.)
Отличие этой задачи от задачи о коммивояжере в общей постановке имеет ту же природу, что и отличие задачи о евклидовом остовном дереве от задачи о минимальном остовном дереве в произвольном графе. А именно расстояния между точками не являются произвольными, а определяются евклидовой
Гл. 6. Близость: варианты и обобщения
метрикой. Как известно, задача о коммивояжере в общей постановке (ЗК) является JVP-трудной').
Можно было бы предположить, что свойства евклидовой метрики могут быть использованы для разработки полиномиального алгоритма решения этой задачи в случае множества точек, заданного на плоскости. Однако Гэри, Грэхем и Джонсон [Garey, Graham, Johnson (1976)], Пападимитриу и Стайг-лиц [Papadimitriou, Steiglitz (1976)] и Пападимитриу [Рара-dimitriou (1976)] наряду с другими результатами о ЛГР-полноте некоторых геометрических задач доказали, что евклидова задача о коммивояжере (ЕЗК) является ЛФ-трудной. Учитывая это, мы не будем обсуждать вопрос разработки эффективного
Рис. 6.4. Продублировав все ребра ЕМОД, получаем граф с эйлеровым циклом.
в худшем случае алгоритма для ЕЗК, а рассмотрим взаимосвязь ЕЗК с другими задачами о близости точек с точки зрения разработки хороших приближенных методов.
Начнем с рассмотрения более простого (и менее эффективного) из двух известных методов, основанного на следующей теореме:
Теорема 6.2 [Rosenkrantz, Stearns, Lewis (1974)]. Используя минимальное остовное дерево, можно получить приближенное решение ЗК, дающее путь, длина которого меньше удвоенной длины кратчайшего пути.
Доказательство. Пусть Т* обозначает евклидово минимальное остовное дерево заданного множества точек S, а Ф—• оптимальный маршрут коммивояжера. Начнем с того, что заменим каждое ребро дерева Т* парой ребер. В результате получим граф W, каждая вершина которого имеет четную степень (рис. 6.4). Граф W является связным эйлеровым графом. Это значит, что его ребра можно занумеровать таким образом, что получившаяся последовательность образует эйлеров цикл,
') Сведения, касающиеся Л^Р-полных задач, а также доказательство того, что ЗК является JVP-трудной, можно найти в ГКагр (1972), Garey, Johnson (1979)].
6.1. Евклидовы минимальные остовные деревья
283
или, иначе говоря, маршрут, проходящий через все вершины (при этом через некоторые вершины он проходит не один раз). Следовательно, длина(№)=2 длина(7*). Заметим, что если удалить из Ф некоторое ребро е, то получим путь Фпуть, который также является остовным деревом множества 5. Очевидно, что длина (Г*) ^ длина (Фпуть) (по определению 7"*) и длина (Фпуть) < длина (Ф). Отсюда получаем длина(W)< 2 длина (Ф).
Заметим, что приближенный маршрут, показанный на рис. 6.4, можно улучшить, сделав его более коротким, удалив все ненужные остановки, т. е. при обходе точек ни одна из уже пройденных точек не проходится вновь. Более конкретно это
Рис. 6.5. Введение «хорд» в эйлеровом цикле обеспечивает однократное посещение каждой вершины.
делается так. На эйлеровом цикле W выбираются произвольным образом направление его обхода и начальная вершина (которую мы оставим непомеченной). Каждая пройденная вершина помечается, а следующей вершиной окончательного маршрута является первая после нее непомеченная вершина, встретившаяся при обходе W в установленном направлении. Применение такой процедуры удаления повторений вершин к примеру на рис. 6.4 дает маршрут, показанный на рис. 6.5. (Заметим, что эта процедура удаления не может увеличить длину получаемого маршрута, так как расстояния между точками удовлетворяют неравенству треугольника.)
Следующий результат, касающийся приближенных методов, использует понятие минимального взвешенного паросочетания.
Задача Б.10 (МИНИМАЛЬНОЕ ЕВКЛИДОВО ПАРОСО-ЧЕТАНИЕ). На плоскости заданы 2N точек. Объединить их в пары, соединив отрезками так, чтобы сумма длин отрезков была минимальной.
Пример такого паросочетания показан на рис. 6.6. Едмондс [Edmonds (1965)] показал, что минимальное взвешенное паросочетание в произвольном графе может быть най-
