4430
правок
Прямолинейное остовное дерево: различия между версиями
Материал из WEGA
Прямолинейное остовное дерево (посмотреть исходный код)
Версия от 14:33, 1 октября 2023
, 1 октября 2023нет описания правки
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) мНет описания правки |
||
| (не показано 5 промежуточных версий этого же участника) | |||
| Строка 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 будет добавлена в активное множество. Каждая точка будет добавлена в активное множество и удалена из него только один раз. | ||
| Строка 60: | Строка 60: | ||
Чтобы найти подмножество активных точек, для которых 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), получаем алгоритм с временем | Чтобы найти подмножество активных точек, для которых 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). | ||
| Строка 70: | Строка 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 с ближайшей точкой каждого подмножества; | ||
| Строка 88: | Строка 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" | ||
