Аноним

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

Материал из WEGA

Прямолинейное дерево Штейнера (посмотреть исходный код)

Версия от 22:53, 1 мая 2016

671 байт добавлено ,  1 мая 2016
→‎Экспериментальные результаты
Строка 108: Строка 108:




Input BG A T
{| class = "wikitable"
size Improve Time Time Improve Time
! rowspan="2" width="100" | Входные данные
Randomly generated testcases
! colspan="2" width="200" | GeoSteiner
100 10:272 0:006 10:341 0:004 9:617 0:000 10:218 0:002
! colspan="2" width="200" | BI1S
500 10:976 0:068 10:778 0:178 10:028 01010 10:381 0:041
! colspan="2" width="200" | BOI
1000 10:979 0:162 10:829 0:689 9:768 0:020 10:433 0:121
! colspan="2" width="200" | RSt
5000 11:012 1:695 11:015 25:518 10:139 0:130 10:499 0:980
|-
10000 11:108 4:135 11:101 249:924 10:111 0:310 10:559 2:098
! | улучш.
50000 11:120 59:147 - - 10:109 1:890 10:561 13:029
! | время
100000 11:098 161:896 - - 10:079 4:410 10:514 28:527
! | улучш.
500000 - - - - 10:059 27:210 10:527 175:725
! | время
 
! | улучш.
VLSI testcases
! | время
337 6:434 0:035 6:503 0:037 5:958 0:010 5:870 0:016
! | улучш.
830 3:202 0:070 3:185 0:213 3:102 0:020 2:966 0:033
! | время
1944 7:850 0:342 7:772 2:424 6:857 0:040 7:533 0:238
|-
2437 7:965 0:549 7:956 4:502 7:094 0:050 7:595 0:408
! colspan="9" | Случайно сгенерированные тестовые сценарии
2676 8:928 0:623 8:994 3:686 8:067 0:060 8:507 0:463
|-
12052 8:450 4:289 8:465 232:779 7:649 0:300 8:076 2:281
| 100||10,272||0,006||10,341||0,004||9,617||0,000||10,218||0,002
22373 9:848 11:330 9:832 1128:365 8:987 0:570 9:462 4:605
|-
34728 9:046 18:416 9:010 2367:629 8:158 0:900 8:645 5:334
| 500||10,976||0,068||10,778||0,178||10,028||0,010||10,381||0,041
|-
| 1000||10,979||0,162||10,829||0,689||9,768||0,020||10,433||0,121
|-
| 5000||11,012||1,695||11,015||25,518||10,139||0,130||10,499||0,980
|-
| 10000||11,108||4,135||11,101||249,924||10,111||0,310||10,559||2,098
|-
| 50000||11,120||59,147||-||-||10,109||1,890||10,561||13,029
|-
| 100000||11,098||161,896||-||-||10,079||4,410||10,514||28,527
|-
| 500000||-||-||-||-||10,059||27,210||10,527||175,725
|-
! colspan="9" | Тестовые сценарии из области разработки СБИС
|-
| 337 6,434 0,035 6,503 0,037 5,958 0,010 5,870 0,016
|-
| 830 3,202 0,070 3,185 0,213 3,102 0,020 2,966 0,033
|-
|-
|  | 1944 7,850 0,342 7,772 2,424 6,857 0,040 7,533 0,238
|-
| 2437 7,965 0,549 7,956 4,502 7,094 0,050 7,595 0,408
|-
| 2676 8,928 0,623 8,994 3,686 8,067 0,060 8,507 0,463
|-
| 12052 8,450 4,289 8,465 232,779 7,649 0,300 8,076 2,281
|-
| 22373 9,848 11,330 9,832 1128,365 8,987 0,570 9,462 4,605
|-
| 34728 9,046 18,416 9,010 2367,629 8,158 0,900 8,645 5,334
|}


Таблица 2. Сравнение с другими алгоритмами (вторая серия).
Таблица 2. Сравнение с другими алгоритмами (вторая серия).
Irina
4430

правок

Источник — http://pco.iis.nsk.su/wega/index.php/Служебная:Сравнение_версий/11416