4430
правок
Прямолинейное остовное дерево: различия между версиями
Материал из WEGA
Прямолинейное остовное дерево (посмотреть исходный код)
Версия от 14:33, 1 октября 2023
, 1 октября 2023нет описания правки
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) мНет описания правки |
||
| (не показано 13 промежуточных версий этого же участника) | |||
| Строка 48: | Строка 48: | ||
Пусть даны две точки p, q в одном и том же сегменте (октанте) восьмиугольного разбиения плоскости относительно точки s. Согласно свойству единственности, ||pq|| < max(||sp||; ||sq||). Рассмотрим цикл с точками s, p и q. Согласно свойству циклов, только одну точку с минимальным расстоянием до s необходимо соединить с s. Интересное свойство восьмиугольного разбиения заключается в том, что контур равноудаленных от s точек формирует отрезок прямой в каждой области. В областях <math>R_1, R_2, R_5, R_6 \;</math> эти сегменты описываются уравнением вида x + y = c; в областях <math>R_3, R_4, R_7, R_8 \;</math> – уравнением вида x - y = c. | Пусть даны две точки p, q в одном и том же сегменте (октанте) восьмиугольного разбиения плоскости относительно точки s. Согласно свойству единственности, ||pq|| < max(||sp||; ||sq||). Рассмотрим цикл с точками s, p и q. Согласно свойству циклов, только одну точку с минимальным расстоянием до s необходимо соединить с s. Интересное свойство восьмиугольного разбиения заключается в том, что контур равноудаленных от s точек формирует отрезок прямой в каждой области. В областях <math>R_1, R_2, R_5, R_6 \;</math> эти сегменты описываются уравнением вида x + y = c; в областях <math>R_3, R_4, R_7, R_8 \;</math> – уравнением вида x - y = c. | ||
Для каждой точки s необходимо найти ближайшего к ней соседа в каждом октанте. Опишем, как эффективно вычислить соседей в октанте <math>R_1 \;</math> для всех точек. Случаи остальных октантов симметричны. Для октанта <math>R_1 \;</math> алгоритм с заметающей прямой | Для каждой точки s необходимо найти ближайшего к ней соседа в каждом октанте. Опишем, как эффективно вычислить соседей в октанте <math>R_1 \;</math> для всех точек. Случаи остальных октантов симметричны. Для октанта <math>R_1 \;</math> алгоритм с заметающей прямой выполняется для всех точек в порядке неубывания x + y. В процессе заметания поддерживается [[активное множество]], состоящее из точек, для которых ближайшие соседи в <math>R_1 \;</math> еще не найдены. После обработки точки p будут найдены все точки активного множества, содержащие p в их областях <math>R_1 \;</math>. Если такая точка содержится в активном множестве, то, поскольку точки проверяются в порядке неубывания x + y, p должна быть ближайшей точкой для s в <math>R_1 \;</math>. Таким образом, будет добавлено ребро sp и точка s будет удалена из активного множества. После обработки этих активных точек точка p будет добавлена в активное множество. Каждая точка будет добавлена в активное множество и удалена из него только один раз. | ||
Фундаментальной операцией алгоритма с заметающей прямой является нахождение подмножества активных точек, такого, что заданная точка p принадлежит к их областям <math>R_1 \;</math>. Основываясь на наблюдении, что точка p принадлежит к области <math>R_1 \;</math> точки s в том и только том случае, если s принадлежит к области <math>R_5 \;</math> точки p, необходимо найти подмножество активных точек в области <math>R_5 \;</math> точки p. Поскольку область <math>R_5 \;</math> может быть представлена как двумерный диапазон <math>( - \infty ,x_p ] \times (x_p - y_p, + \infty) \;</math> на <math>(x, x - y) \;</math>, для поддержки множества активных точек можно использовать дерево поиска с приоритетами [1]. В силу того, что каждая операция вставки и удаления требует O(log n) времени, а операция запроса – O(log n+ k) времени, где k – количество объектов в диапазоне, общее время работы алгоритма с заметающей прямой составит O(n log n). Другие области могут быть обработаны аналогично <math>R_1 \;</math>, так что полное время работы алгоритма составит O(n log n). Дерево поиска с приоритетами – это структура данных, поддерживающая сбалансированность ради быстрого осуществления поиска. Она отлично работает для статических входных множеств. Если входное множество оказывается динамическим, перебалансировка дерева может представлять серьезную проблему. К счастью, активное множество имеет структуру, которая допускает альтернативное представление. Поскольку точка удаляется из активного множества, если найдена точка в ее области <math>R_1 \;</math>, никакая точка активного множества не может принадлежать к области <math>R_1 \;</math> другой точки множества. | |||
'''Лемма 2. Для любых двух точек p, q, входящих в активное множество, должно выполняться <math>x_p \ne x_q \;</math>, и если <math>x_p < x_q \;</math>, то <math>x_p - y_p \le x_q - y_q \;</math>.''' | |||
'''Лемма 2. Для любых двух точек p, q в | |||
| Строка 62: | Строка 60: | ||
Чтобы найти подмножество активных точек, для которых s находится в их областях <math>R_1 \;</math>, вначале необходимо найти наибольшее x, такое, что <math>x \le x_s \;</math>, а затем выполнять обработку в порядке убывания x, до тех пор, пока не будет достигнуто <math>x - y \ge | Чтобы найти подмножество активных точек, для которых s находится в их областях <math>R_1 \;</math>, вначале необходимо найти наибольшее x, такое, что <math>x \le x_s \;</math>, а затем выполнять обработку в порядке убывания x, до тех пор, пока не будет достигнуто <math>x - y \ge x_s - y_s \;</math>. Поскольку упорядочение производится только по одному измерению, используя любое бинарное дерево поиска со стоимостью операций вставки, деления и запроса, равной O(log n), получаем алгоритм с временем выполнения O(n log n). Бинарные деревья поиска также требуют балансировки. Кроме того, можно использовать списки с пропусками [2], использующие рандомизацию во избежание проблемы явной балансировки, но демонстрирующие ожидаемое поведение на уровне O(log n). | ||
Внимательное рассмотрение также позволяет прийти к выводу, что после заметания области <math>R_1 \;</math> нет необходимости в заметании <math>R_5 \;</math>, поскольку все ребра, необходимые на данном этапе, уже | Внимательное рассмотрение также позволяет прийти к выводу, что после заметания области <math>R_1 \;</math> нет необходимости в заметании <math>R_5 \;</math>, поскольку все ребра, необходимые на данном этапе, уже включены или предполагаются. Более того, основываясь на информации из <math>R_5 \;</math>, количество реберных соединений можно еще больше сократить. Во время обработки заметающим процессом точки s он находит подмножество активных точек, содержащих s в их областях <math>R_1 \;</math>. Без потери общности будем считать, что к ним относятся точки p и q. Тогда p и q принадлежат к области <math>R_5 \;</math> точки s, что означает ||pq|| < max(||sp||; ||sq||). Следовательно, необходимо только соединить s с ближайшей активной точкой. | ||
| Строка 72: | Строка 70: | ||
'''for''' (i = 0; i < 2; i + +) { | '''for''' (i = 0; i < 2; i + +) { | ||
'''if''' (i == 0) отсортировать точки согласно x + y; | '''if''' (i == 0) отсортировать точки согласно порядку x + y; | ||
'''else''' отсортировать точки согласно x - y; | '''else''' отсортировать точки согласно порядку x - y; | ||
A[l] = A[2] = <math>\empty</math> | A[l] = A[2] = <math>\empty</math> | ||
'''for''' каждой точки | '''for''' каждой точки p по порядку { | ||
найти точки в А[1], А[2], такие, что p находится в их областях <math>R_{2i+1}</math> и <math>R_{2i+2}</math>, соответственно; | найти точки в А[1], А[2], такие, что p находится в их областях <math>R_{2i+1}</math> и <math>R_{2i+2}</math>, соответственно; | ||
соединить p с ближайшей точкой каждого подмножества; | соединить p с ближайшей точкой каждого подмножества; | ||
| Строка 90: | Строка 88: | ||
'''Теорема 3. Пусть имеется n точек на плоскости. Алгоритм вычисления прямолинейного остовного графа строит остовный граф за время O(n log n), при этом количество ребер графа составляет O(n).''' | '''Теорема 3. Пусть имеется n точек на плоскости. Алгоритм вычисления прямолинейного остовного графа строит остовный граф за время O(n log n), при этом количество ребер графа составляет O(n).''' | ||
Доказательство. Алгоритм может рассматриваться как механизм удаления ребер из полного графа. Как было отмечено выше, все удаленные ребра являются избыточными согласно правилу циклов. Таким образом, граф на выходе алгоритма будет содержать по меньшей мере одно прямолинейное минимальное остовное дерево. | Доказательство. Алгоритм может рассматриваться как механизм удаления ребер из полного графа. Как было отмечено выше, все удаленные ребра являются избыточными согласно правилу циклов. Таким образом, граф на выходе алгоритма будет содержать по меньшей мере одно прямолинейное минимальное остовное дерево. | ||
За время работы алгоритма каждая точка будет добавлена в активное множество и удалена из него только один раз для каждой из областей <math>R_1 - R_4 \;</math>. Каждая операция вставки и удаления требует O(log n) времени. Таким образом, верхняя граница временной сложности алгоритма оказывается равной O(n log n). Хранить необходимо только активные множества, так что объем памяти для хранения не превышает O(n). □ | |||
== Применение == | == Применение == | ||
Алгоритм построения прямолинейного минимального остовного дерева широко применяется в САПР для проектирования СБИС. Он часто используется в качестве метрики для оценки длины кабелей в процессе размещения. Прямолинейные МОД нередко вычисляются для аппроксимации дерева Штейнера и являются ключевым компонентом многих эвристик дерева Штейнера. Также они | Алгоритм построения прямолинейного минимального остовного дерева широко применяется в САПР для проектирования СБИС. Он часто используется в качестве метрики для оценки длины кабелей в процессе размещения. Прямолинейные МОД нередко вычисляются для аппроксимации дерева Штейнера и являются ключевым компонентом многих эвристик дерева Штейнера. Также они используются для аппроксимации задачи коммивояжера, которая может применяться для генерации цепей сканирования при тестировании. Важно подчеркнуть, что в реальных приложениях размеры входных объектов обычно очень велики. Поскольку эта задача будет вычисляться сотни тысяч раз и во многих случаях на очень больших входных значениях, для вычисления прямолинейного МОД нужен очень эффективный алгоритм. | ||
== Экспериментальные результаты == | == Экспериментальные результаты == | ||
Экспериментальные результаты построения прямолинейного остовного графа на основе алгоритма Крускала для вычисления прямолинейного МОД были представлены Чжоу и др. [5]. В сравнении участвовали два других подхода. Первый подход использовал полный граф на множестве точек в качестве входного для алгоритма Крускала. Второй подход представлял собой реализацию концепции, предложенной в [3]: для каждой точки просканировать все остальные точки, но | Экспериментальные результаты построения прямолинейного остовного графа (ПОГ) на основе алгоритма Крускала для вычисления прямолинейного МОД были представлены Чжоу и др. [5]. В сравнении участвовали два других подхода. Первый подход использовал полный граф на множестве точек в качестве входного для алгоритма Крускала. Второй подход представлял собой реализацию концепции, предложенной в [3]: для каждой точки просканировать все остальные точки, но соединить ее только с ближайшей точкой в каждом квадранте. В эксперименте использовались множества от 1000 до 20000 точек, сгенерированные случайным образом. Результаты эксперимента представлены в таблице 1. В первом столбце указано количество сгенерированных точек; во втором – количество различающихся точек. Для каждого подхода приведены количество ребер в заданном графе и общее время выполнения. Если количество точек на входе было больше 10000, подходу на основе полного графа попросту не хватало памяти. | ||
{| class = "wikitable" | {| class = "wikitable" | ||
