4430
правок
Конкурс по реализации алгоритмов поиска кратчайших путей: различия между версиями
Материал из WEGA
Конкурс по реализации алгоритмов поиска кратчайших путей (посмотреть исходный код)
Версия от 11:06, 29 мая 2018
, 29 мая 2018→Наборы данных
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 60: | Строка 60: | ||
== Наборы данных == | == Наборы данных == | ||
Набор эталонных входных данных 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 | Набор эталонных входных данных 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" | |||
|- | |||
! НАЗВАНИЕ | |||
! ОПИСАНИЕ | |||
! ЧИСЛО ВЕРШИН | |||
! ЧИСЛО ДУГ | |||
! ШИРОТА ОГР. ПРЯМ. (С) | |||
! ДОЛГОТА ОГР. ПРЯМ. (В) | |||
|- | |||
| USA | |||
| США (вся страна) | |||
| 23 947 347 | |||
| 58 333 344 | |||
| - | |||
| - | |||
|- | |||
| CTR | |||
| Центр США | |||
| 14081816 | |||
| 34 292496 | |||
| [25,0; 50,0] | |||
| [79,0; 100,0] | |||
|- | |||
| W | |||
| Запад США | |||
| 6 262104 | |||
| 15 248146 | |||
| [27.0; 50.0] | |||
| [100.0; 130.0] | |||
|- | |||
| E | |||
| Восток США | |||
| 3 598623 | |||
| 8778114 | |||
| [24,0; 50,0] | |||
| [-1; 79,0] | |||
|- | |||
| LKS | |||
| Великие озера | |||
| 2758119 | |||
| 6885 658 | |||
| [41,0; 50,0] | |||
| [74,0; 93,0] | |||
|- | |||
| CAL | |||
| Калифорния и Невада | |||
| 1890815 | |||
| 4657 742 | |||
| [32,5; 42,0] | |||
| [114.0; 125.0] | |||
|- | |||
| NE | |||
| Северо-восток США | |||
| 1 524453 | |||
| 3 897 636 | |||
| [39,5; 43,0] | |||
| [-1; 76,0] | |||
|- | |||
| NW | |||
| Северо-запад США | |||
| 1 207 945 | |||
| 2 840 208 | |||
| [42,0; 50,0] | |||
| [116,0; 126,0] | |||
|- | |||
| FLA | |||
| Флорида | |||
| 1070 376 | |||
| 2 712 798 | |||
| [24,0; 31,0] | |||
| [79; 87,5] | |||
|- | |||
| COL | |||
| Колорадо | |||
| 435 666. | |||
| 1057 066 | |||
| [37,0; 41,0] | |||
| [102,0; 109,0] | |||
|- | |||
| BAY | |||
| Область Залива | |||
| 321 270 | |||
| 800172 | |||
| [37,0; 39,0] | |||
| [121; 123] | |||
|- | |||
| NY | |||
| Нью-Йорк | |||
| 264 346 | |||
| 733 846 | |||
| [40,3; 41,3] | |||
| [73,5; 74,5] | |||
|} | |||
Таблица 1. Дорожные сети США, созданные на основе набора TIGER/Line | Таблица 1. Дорожные сети США, созданные на основе набора TIGER/Line | ||
