4551
правка
Прямолинейное дерево Штейнера: различия между версиями
Перейти к навигации
Перейти к поиску
→Экспериментальные результаты
Irina (обсуждение | вклад) (Новая страница: «== Ключевые слова и синонимы == Метрическое минимальное дерево Штейнера; кратчайшее дерев…») |
Irina (обсуждение | вклад) |
||
| Строка 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 | |||
|- | |||
! | улучш. | |||
! | время | |||
! | улучш. | |||
! | время | |||
! | улучш. | |||
! | время | |||
! | улучш. | |||
! | время | |||
|- | |||
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: | ||
== См. также | == См. также | ||
* ''[Прямолинейное остовное дерево] | * ''[Прямолинейное остовное дерево] | ||
== Литература == | == Литература == | ||