Аноним

Прямолинейное дерево Штейнера: различия между версиями

Материал из WEGA
(Новая страница: «== Ключевые слова и синонимы == Метрическое минимальное дерево Штейнера; кратчайшее дерев…»)
 
Строка 70: Строка 70:
Во второй серии экспериментов сравнивались алгоритмы RST, версия Боры его собственного алгоритма (Borah), алгоритм Роэ на базе подхода Прима (Rohe) [ ] и жадный пакетный алгоритм Канга и др. (Batched Greedy Algorithm, BGA) [ ]. Они исполнялись на различных Linux-системах с процессором Intel Xeon с 2,4 ГГц тактовой частоты и 2 ГБ оперативной памяти. Помимо случайно сгенерированных тестовых сценариев, также использовались промышленные тестовые сценарии из области разработки СБИС [9]. Результаты представлены в таблице 2.
Во второй серии экспериментов сравнивались алгоритмы RST, версия Боры его собственного алгоритма (Borah), алгоритм Роэ на базе подхода Прима (Rohe) [ ] и жадный пакетный алгоритм Канга и др. (Batched Greedy Algorithm, BGA) [ ]. Они исполнялись на различных Linux-системах с процессором Intel Xeon с 2,4 ГГц тактовой частоты и 2 ГБ оперативной памяти. Помимо случайно сгенерированных тестовых сценариев, также использовались промышленные тестовые сценарии из области разработки СБИС [9]. Результаты представлены в таблице 2.


{| class = "wikitable"
! rowspan="2" width="100" | Входные данные
! colspan="2" width="200" | GeoSteiner
! colspan="2" width="200" | BI1S
! colspan="2" width="200" | BOI
! colspan="2" width="200" | RSt
|-
! | улучш.
! | время
! | улучш.
! | время
! | улучш.
! | время
! | улучш.
! | время
|-


Input GeoSte einer BI1S S В
 
BI1S S В
size Improve Time Improve Time Improve Time Improve Time
size Improve Time Improve Time Improve Time Improve Time
100 11:440 0:487 10:907 0:633 9.300 0:0267 10.218 0.004
100 11:440 0:487 10:907 0:633 9.300 0:0267 10.218 0.004
Строка 113: Строка 130:
== См. также
== См. также
* ''[Прямолинейное остовное дерево]
* ''[Прямолинейное остовное дерево]


== Литература ==
== Литература ==
4551

правка