4431
правка
Разработка алгоритмов для применения в больших сетях: различия между версиями
Перейти к навигации
Перейти к поиску
Разработка алгоритмов для применения в больших сетях (посмотреть исходный код)
Версия от 13:28, 15 января 2019
, 15 января 2019→Применение
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 51: | Строка 51: | ||
== Применение == | == Применение == | ||
Ответы на запросы о кратчайших путях в большим графам требуются в множестве различных приложений, в частности, в системах управления информацией о дорожном движении, работающих по вышеупомянутому сценарию: центральный сервер должен максимально быстро отвечать на большое число запросов от клиентов в реальном времени, которым необходим лучший путь или оптимальный маршрут. Среди других вариантов применения этого сценария можно упомянуть системы планирования маршрутов для автомобилей, велосипедистов и туристов-пешеходов; системы общественного транспорта с информацией о графике транспортных средств на маршруте (например, поездов или автобусов); ответы на запросы в пространственных базах данных и Интернет-поиск. Все эти примеры относятся к системам реального времени, в которых пользователи постоянно задают вопросы для поиска лучшего подключения или маршрута. Поэтому основной целью является сокращение (среднего) времени выполнения запроса. | |||
== Открытые вопросы == | |||
Размеры реальных сетей постоянно растут – как в результате накопления в них все больших и больших объемов информации, так и в результате цифровой конвергенции медиасервисов, сетей коммуникаций и устройств. Рост размера сетей ставит под вопрос масштабируемость алгоритмов, определяющих их работу. По мере этого роста будет сохраняться потребность в разработке более быстрых алгоритмов для решения базовых алгоритмических задач. | |||
== Экспериментальные результаты == | |||
Все работы, упомянутые в разделе «Основные результаты», содержат изложение важных экспериментальных исследований рассматриваемых ими техник. | |||
== Наборы данных == | |||
Наборы данных, использовавшиеся в [6, 11], доступны по адресу http://lso-compendium.cti.gr/ (номера задач 20 и 26, соответственно). | |||
Наборы данных, использовавшиеся в [1, 2], доступны по адресу http://www.dis.uniroma1.it/~challenge9/. | |||
== Ссылка на код == | |||
Код, используемый в [6, 11], доступен на сайте http://doi.acm.org/ 10.1145/351827.384254. | |||
Код, используемый в [6, 11], доступен по адресу http://lso-compendium.cti.gr/ (номера задач 20 и 26, соответственно). | |||
Код, используемый в [3], доступен на сайте http://www. avglab.com/andrew/soft.html. | |||
== См. также == | |||
* [[Конкурс по реализации алгоритмов поиска кратчайших путей]] | |||
* [[Подход к составлению расписания при помощи кратчайших путей]] | |||
== Литература == | |||
1. Delling, D., Holzer, M., Miiller, K., Schulz, F., Wagner, D.: High-Performance Multi-Level Graphs. In: 9th DIMACS Challenge on Shortest Paths, Nov 2006. Rutgers University, USA (2006) | |||
2. Delling, D., Sanders, P., Schultes, D., Wagner, D.: Highway Hierarchies Star. In: 9th DIMACS Challenge on Shortest Paths, Nov 2006 Rutgers University, USA (2006) | |||
3. Goldberg, A.V., Harrelson, C.: Computing the Shortest Path: A* Search Meets Graph Theory. In: Proc. 16th ACM-SIAM Symposium on Discrete Algorithms - SODA, pp. 156-165. ACM, New York and SIAM, Philadelphia (2005) | |||
4. Gutman, R.: Reach-based Routing: A New Approach to Shortest Path Algorithms Optimized for Road Networks. In: Algorithm Engineering and Experiments - ALENEX (SIAM, 2004), pp. 100-111. SIAM, Philadelphia (2004) | |||
5. Holzer, M., Schulz, F., Wagner, D.: Engineering Multi-Level Overlay Graphs for Shortest-Path Queries. In: Algorithm Engineering and Experiments - ALENEX (SIAM, 2006), pp. 156-170. SIAM, Philadelphia (2006) | |||
6. Pyrga, E., Schulz, F., Wagner, D., Zaroliagis, C.: Efficient Models for Timetable Information in Public Transportation Systems. ACM J. Exp. Algorithmic 12(2.4), 1-39 (2007) | |||
7. Sanders, P., Schultes, D.: Highway Hierarchies Hasten Exact Shortest Path Queries. In: Algorithms - ESA 2005. Lect. Note Comp. Sci. 3669,568-579 (2005) | |||
8. Sanders, P., Schultes, D.: Engineering Highway Hierarchies. In: Algorithms - ESA 2006. Lect. Note Comp. Sci. 4168, 804-816 (2006) | |||
9. Schulz, F., Wagner, D., Weihe, K.: Dijkstra's Algorithm On-Line: An Empirical Case Study from Public Railroad Transport. ACM J. Exp. Algorithmics 5(12), 1 -23 (2000) | |||
10. Schulz, F., Wagner, D., Zaroliagis, C.: Using Multi-Level Graphs for Timetable Information in Railway Systems. In: Algorithm Engineering and Experiments - ALENEX 2002. Lect. Note Comp. Sci. 2409,43-59 (2002) | |||
11. Wagner, D., Willhalm, T., Zaroliagis, C.: Geometric Containers for Efficient Shortest Path Computation. ACM J. Exp. Algorithmics 10(1.3), 1-30 (2005) | |||