4446
правок
Прямолинейное дерево Штейнера: различия между версиями
Материал из WEGA
м
нет описания правки
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) мНет описания правки |
||
| Строка 34: | Строка 34: | ||
Большую часть времени исполнения алгоритма занимают генерация остовного графа и сортировка ребер, требующие O(n log n) времени. Поскольку количество ребер в остовном графе составляет O(n), и алгоритм Крускала, и алгоритм Тарьяна для поиска наименьших общих предков занимают <math>O(n \alpha (n)) \;</math> времени, где <math>\alpha (n) \;</math> – обратная функция Аккермана, растущая исключительно медленно. | Большую часть времени исполнения алгоритма занимают генерация остовного графа и сортировка ребер, требующие O(n log n) времени. Поскольку количество ребер в остовном графе составляет O(n), и алгоритм Крускала, и алгоритм Тарьяна для поиска наименьших общих предков занимают <math>O(n \alpha (n)) \;</math> времени, где <math>\alpha (n) \;</math> – обратная функция Аккермана, растущая исключительно медленно. | ||
<math>T = \empty</math>; | <math>T = \empty</math>; | ||
| Строка 58: | Строка 59: | ||
Рисунок 3. Алгоритм построения прямолинейного дерева Штейнера. | Рисунок 3. Алгоритм построения прямолинейного дерева Штейнера. | ||
== Применение == | == Применение == | ||
| Строка 64: | Строка 66: | ||
== Экспериментальные результаты == | == Экспериментальные результаты == | ||
Как отмечалось в работе [ ], первая серия экспериментов была проведена на Linux-системе с процессором Intel Pentium III с тактовой частотой 938 МГц и 512 Мбайт оперативной памяти. Алгоритм RST сравнивался с другими публично доступными программами: точным алгоритмом GeoSteiner (версия 3.1) Уорма, Уинтера и Захарисена [ ], пакетным итеративным алгоритмом 1-Steiner (BI1S) Робинса и алгоритмом Боры и коллег, реализованным Мэдденом (BOI). | Как отмечалось в работе [16], первая серия экспериментов была проведена на Linux-системе с процессором Intel Pentium III с тактовой частотой 938 МГц и 512 Мбайт оперативной памяти. Алгоритм RST сравнивался с другими публично доступными программами: точным алгоритмом GeoSteiner (версия 3.1) Уорма, Уинтера и Захарисена [14], пакетным итеративным алгоритмом 1-Steiner (BI1S) Робинса и алгоритмом Боры и коллег, реализованным Мэдденом (BOI). | ||
| Строка 70: | Строка 72: | ||
Во второй серии экспериментов сравнивались алгоритмы RST, версия Боры его собственного алгоритма (Borah), алгоритм Роэ на базе подхода Прима (Rohe) [ ] и жадный пакетный алгоритм Канга и др. (Batched Greedy Algorithm, BGA) [ ]. Они исполнялись на различных Linux-системах с процессором Intel Xeon с 2,4 ГГц тактовой частоты и 2 ГБ оперативной памяти. Помимо случайно сгенерированных тестовых сценариев, также использовались промышленные тестовые сценарии из области разработки СБИС [9]. Результаты представлены в таблице 2. | Во второй серии экспериментов сравнивались алгоритмы RST, версия Боры его собственного алгоритма (Borah), алгоритм Роэ на базе подхода Прима (Rohe) [13] и жадный пакетный алгоритм Канга и др. (Batched Greedy Algorithm, BGA) [9]. Они исполнялись на различных Linux-системах с процессором Intel Xeon с 2,4 ГГц тактовой частоты и 2 ГБ оперативной памяти. Помимо случайно сгенерированных тестовых сценариев, также использовались промышленные тестовые сценарии из области разработки СБИС [9]. Результаты представлены в таблице 2. | ||
{| class = "wikitable" | {| class = "wikitable" | ||
