4430
правок
Конкурс по реализации алгоритмов поиска кратчайших путей: различия между версиями
Материал из WEGA
Конкурс по реализации алгоритмов поиска кратчайших путей (посмотреть исходный код)
Версия от 10:57, 4 июня 2018
, 4 июня 2018→Наборы данных
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) м (→Наборы данных) |
||
| Строка 73: | Строка 73: | ||
== Наборы данных == | == Наборы данных == | ||
Набор эталонных входных данных 9-го конкурса DIMACS по реализации алгоритмов | Набор эталонных входных данных 9-го конкурса DIMACS по реализации алгоритмов включал как синтетические данные, так и реальные данные. Все графы являлись сильно связными. В число синтетических графов входили случайные графы, решетки, графы, уложенные на тор, и графы со свойствами «тесного мира». Реальные данные включали графы, представляющие дорожные сети Европы и США. Графы Европы были предоставлены компанией PTV из Карлсруэ (Германия) на основе бесплатного лицензионного соглашения. Они включали дорожные сети 17 европейских стран, среди которых были Австрия (AUT), Бельгия (BEL), Швейцария (CHE), Чехия (CZE), Германия (DEU), Дания (DNK), Испания (ESP), Финляндия (FIN), Франция (FRA), Великобритания (GBR), Ирландия (IRL), Италия (ITA), Люксембург (LUX), Нидерланды (NDL), Норвегия (NOR), Португалия (PRT) и Швеция (SWE), суммарно составляющие около 19 миллионов вершин и 23 миллионов ребер. Графы для США были созданы на основе файлов UA Census 2000 TIGER/Line. | ||
{| class="wikitable" | {| class="wikitable" | ||
| Строка 93: | Строка 93: | ||
| CTR | | CTR | ||
| Центр США | | Центр США | ||
| | | 14 081 816 | ||
| 34 | | 34 292 496 | ||
| [25,0; 50,0] | | [25,0; 50,0] | ||
| [79,0; 100,0] | | [79,0; 100,0] | ||
| Строка 100: | Строка 100: | ||
| W | | W | ||
| Запад США | | Запад США | ||
| 6 | | 6 262 104 | ||
| 15 | | 15 248 146 | ||
| [27.0; 50.0] | | [27.0; 50.0] | ||
| [100.0; 130.0] | | [100.0; 130.0] | ||
| Строка 107: | Строка 107: | ||
| E | | E | ||
| Восток США | | Восток США | ||
| 3 | | 3 598 623 | ||
| | | 8 778 114 | ||
| [24,0; 50,0] | | [24,0; 50,0] | ||
| [-1; 79,0] | | [-1; 79,0] | ||
| Строка 114: | Строка 114: | ||
| LKS | | LKS | ||
| Великие озера | | Великие озера | ||
| | | 2 758 119 | ||
| | | 6 885 658 | ||
| [41,0; 50,0] | | [41,0; 50,0] | ||
| [74,0; 93,0] | | [74,0; 93,0] | ||
| Строка 121: | Строка 121: | ||
| CAL | | CAL | ||
| Калифорния и Невада | | Калифорния и Невада | ||
| | | 1 890 815 | ||
| | | 4 657 742 | ||
| [32,5; 42,0] | | [32,5; 42,0] | ||
| [114.0; 125.0] | | [114.0; 125.0] | ||
| Строка 128: | Строка 128: | ||
| NE | | NE | ||
| Северо-восток США | | Северо-восток США | ||
| 1 | | 1 524 453 | ||
| 3 897 636 | | 3 897 636 | ||
| [39,5; 43,0] | | [39,5; 43,0] | ||
| Строка 142: | Строка 142: | ||
| FLA | | FLA | ||
| Флорида | | Флорида | ||
| | | 1 070 376 | ||
| 2 712 798 | | 2 712 798 | ||
| [24,0; 31,0] | | [24,0; 31,0] | ||
| Строка 149: | Строка 149: | ||
| COL | | COL | ||
| Колорадо | | Колорадо | ||
| 435 666 | | 435 666 | ||
| | | 1 057 066 | ||
| [37,0; 41,0] | | [37,0; 41,0] | ||
| [102,0; 109,0] | | [102,0; 109,0] | ||
| Строка 157: | Строка 157: | ||
| Область Залива | | Область Залива | ||
| 321 270 | | 321 270 | ||
| | | 800 172 | ||
| [37,0; 39,0] | | [37,0; 39,0] | ||
| [121; 123] | | [121; 123] | ||
