4551
правка
Прямолинейное остовное дерево: различия между версиями
Перейти к навигации
Перейти к поиску
Прямолинейное остовное дерево (посмотреть исходный код)
Версия от 12:36, 27 апреля 2016
, 27 апреля 2016→Применение
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 103: | Строка 103: | ||
Алгоритм построения прямолинейного минимального остовного дерева широко применяется в САПР для проектирования СБИС. Он часто используется в качестве метрики для оценки длины кабелей в процессе размещения. Прямолинейные МОД нередко вычисляются для аппроксимации дерева Штейнера и являются ключевым компонентом многих эвристик дерева Штейнера. Также они использовались для аппроксимации задачи коммивояжера, которая может применяться для генерации цепей сканирования в процессе тестирования. Важно подчеркнуть, что в реальных приложениях размеры входных объектов обычно очень велики. Поскольку эта задача будет вычисляться сотни тысяч раз и во многих случаях на очень больших входных значениях, для вычисления прямолинейного МОД нужен очень эффективный алгоритм. | Алгоритм построения прямолинейного минимального остовного дерева широко применяется в САПР для проектирования СБИС. Он часто используется в качестве метрики для оценки длины кабелей в процессе размещения. Прямолинейные МОД нередко вычисляются для аппроксимации дерева Штейнера и являются ключевым компонентом многих эвристик дерева Штейнера. Также они использовались для аппроксимации задачи коммивояжера, которая может применяться для генерации цепей сканирования в процессе тестирования. Важно подчеркнуть, что в реальных приложениях размеры входных объектов обычно очень велики. Поскольку эта задача будет вычисляться сотни тысяч раз и во многих случаях на очень больших входных значениях, для вычисления прямолинейного МОД нужен очень эффективный алгоритм. | ||
{| | |||
! style="background:#efefef;" colspan="2" width="200" | Вход | |||
! style="background:#efefef;" colspan="2" | Полный | |||
! style="background:#efefef;" colspan="2" | Огр. степени | |||
! style="background:#efefef;" colspan="2" | RSG | |||
|- | |||
! style="background:#efefef;" | исх. | |||
! style="background:#efefef;" | разл. | |||
! style="background:#efefef;" | число ребер | |||
! style="background:#efefef;" | время | |||
! style="background:#efefef;" | число ребер | |||
! style="background:#efefef;" | время | |||
! style="background:#efefef;" | число ребер | |||
! style="background:#efefef;" | время | |||
|} | |||
Таблица 1. Экспериментальные результаты | Таблица 1. Экспериментальные результаты | ||
| Строка 119: | Строка 135: | ||
18000 17837 - - 70876 1m 19.812s 47511 1.701s | 18000 17837 - - 70876 1m 19.812s 47511 1.701s | ||
20000 19805 - - 78723 1m 45.792 s 52732 1.907 s | 20000 19805 - - 78723 1m 45.792 s 52732 1.907 s | ||
== Экспериментальные результаты == | == Экспериментальные результаты == | ||