4551
правка
Прямолинейное остовное дерево: различия между версиями
Перейти к навигации
Перейти к поиску
Прямолинейное остовное дерево (посмотреть исходный код)
Версия от 12:58, 27 апреля 2016
, 27 апреля 2016нет описания правки
Irina (обсуждение | вклад) м (→Применение) |
Irina (обсуждение | вклад) Нет описания правки |
||
| Строка 103: | Строка 103: | ||
Алгоритм построения прямолинейного минимального остовного дерева широко применяется в САПР для проектирования СБИС. Он часто используется в качестве метрики для оценки длины кабелей в процессе размещения. Прямолинейные МОД нередко вычисляются для аппроксимации дерева Штейнера и являются ключевым компонентом многих эвристик дерева Штейнера. Также они использовались для аппроксимации задачи коммивояжера, которая может применяться для генерации цепей сканирования в процессе тестирования. Важно подчеркнуть, что в реальных приложениях размеры входных объектов обычно очень велики. Поскольку эта задача будет вычисляться сотни тысяч раз и во многих случаях на очень больших входных значениях, для вычисления прямолинейного МОД нужен очень эффективный алгоритм. | Алгоритм построения прямолинейного минимального остовного дерева широко применяется в САПР для проектирования СБИС. Он часто используется в качестве метрики для оценки длины кабелей в процессе размещения. Прямолинейные МОД нередко вычисляются для аппроксимации дерева Штейнера и являются ключевым компонентом многих эвристик дерева Штейнера. Также они использовались для аппроксимации задачи коммивояжера, которая может применяться для генерации цепей сканирования в процессе тестирования. Важно подчеркнуть, что в реальных приложениях размеры входных объектов обычно очень велики. Поскольку эта задача будет вычисляться сотни тысяч раз и во многих случаях на очень больших входных значениях, для вычисления прямолинейного МОД нужен очень эффективный алгоритм. | ||
== Экспериментальные результаты == | |||
Экспериментальные результаты построения прямолинейного остовного графа на основе алгоритма Крускала для вычисления прямолинейного МОД были представлены Чжоу и др. [5]. В сравнении участвовали два других подхода. Первый подход использовал полный граф на множестве точек в качестве входного для алгоритма Крускала. Второй подход представлял собой реализацию концепции, предложенной в [ ]: для каждой точки просканировать все остальные точки, но установить связь только с ближайшей точкой в каждом квадранте. В эксперименте использовались множества от 1000 до 20000 точек, сгенерированные случайным образом. Результаты эксперимента представлены в таблице 1. В первом столбце указано количество сгенерированных точек; во втором – количество различающихся точек. Для каждого подхода приведены количество ребер в заданном графе и общее время исполнения. Если количество точек на входе больше 10000, подходу на основе полного графа попросту не хватало памяти. | |||
{| class = "wikitable" | {| class = "wikitable" | ||
! style="background:#efefef;" colspan="2" width="200" | Вход | ! style="background:#efefef;" colspan="2" width="200" | Вход | ||
! style="background:#efefef;" colspan="2" | Полный | ! style="background:#efefef;" colspan="2" | Полный | ||
! style="background:#efefef;" colspan="2" | | ! style="background:#efefef;" colspan="2" | С огр. степени | ||
! style="background:#efefef;" colspan="2" | | ! style="background:#efefef;" colspan="2" | ПОГ | ||
|- | |- | ||
! style="background:#efefef;" | исх. | ! style="background:#efefef;" | исх. | ||
| Строка 143: | Строка 146: | ||
Таблица 1. Экспериментальные результаты | Таблица 1. Экспериментальные результаты | ||