Опишите компромисс между временем выполнения и потреблением памяти, если нужно хранить большие графы в памяти для поиска кратчайшего пути; какие структуры и алгоритмы вы бы рекомендовали для sparse vs dense графов
Компромисс: больше предварительной памяти — быстрее запросы; меньше памяти — медленнее или нужны повторные вычисления/приближения. Характерные варианты: Общие замечания - Хранение: матрица смежности занимает \(O(V^2)\) памяти, списки смежности / CSR — \(O(V+E)\). - Постпроцессинг/индексация (contraction hierarchies, hub labeling) требует дополнительной памяти и времени на предвычисление, но даёт очень быстрые запросы (часто миллисекунды/микросекунды). - Если граф не влезает в ОЗУ — использовать внешнюю память (memory-mapped files, external-memory algorithms), стриминг или приближённые методы. Рекомендации для sparse (разрежённые) графы (\(E \ll V^2\)) - Структуры: - Списки смежности (вектор списков пар (v, w)) — простые, память \(O(V+E)\). - CSR (Compressed Sparse Row) — плотная компактная репрезентация, лучшая кэш-локальность, память \(O(V+E)\). - Edge list — для экономии при одном проходе/сортировке. - Алгоритмы: - Однопарный поиск кратчайшего пути: Dijkstra + бинарная куча: \(O(E\log V)\) (точнее \(O((E+V)\log V)\)); с Fibonacci-кучей: \(O(E + V\log V)\). - Для небольших целочисленных весов: Dial / Radix heap — часто быстрее, амортизированно близко к \(O(E + V)\). - Для графов дорог: Contraction Hierarchies, ALT (landmarks) — дополнительные индексы, но ответы очень быстрые. - Для отрицательных весов: Bellman–Ford \(O(VE)\) или Johnson (перевзвешивание + Dijkstra) для всех пар. - Почему: списки/CSR минимизируют память и обход соседей; кучи уменьшают стоимость выбора минимального узла при редких ребрах. Рекомендации для dense (плотные) графы (\(E \approx V^2\)) - Структуры: - Матрица смежности (двумерный массив или битсеты) — память \(O(V^2)\), быстрый доступ к наличию ребра и веса. - Для булевых/плотных операций — битсеты (SIMD/GPU-ускорение). - Алгоритмы: - Если нужен один источник: Dijkstra с простым массивом расстояний (без кучи) даёт \(O(V^2)\) и часто лучше в плотном графе. - Для всех пар: Floyd–Warshall \(O(V^3)\) на матрице; иногда лучше алгоритмы на основе многократного Dijkstra (если веса неотрицательные). - Для матричных операций — использовать блокирование, BLAS/GPU для ускорения. - Почему: при \(E \sim V^2\) затраты на хранение матрицы приемлемы, и массивные операции по матрице дают лучшую производительность из‑за кэша и векторизации. Практические советы и компромиссы - Если память критична и граф разрежён — CSR + Dijkstra/ALT; если граф статичен и запросов много — потратить память на CH или hub-labeling. - Если задачи — много однотипных запросов (all-pairs/много источников) и граф плотный — матрица + Floyd/матричные методы. - Если веса целые в ограничённом диапазоне — использовать radix/Dial для скорости и простоты. - Для очень больших графов — приблизительные методы (landmarks, sketching), внешняя память или распределённая обработка. Коротко: для sparse — \(O(V+E)\) структуры (списки/CSR) + Dijkstra/специализированные кучи/CH; для dense — \(O(V^2)\) матрица + алгоритмы на матрице (Dijkstra\(O(V^2)\) или Floyd–Warshall\(O(V^3)\)), либо битсеты/GPU для ускорения.
Общие замечания
- Хранение: матрица смежности занимает \(O(V^2)\) памяти, списки смежности / CSR — \(O(V+E)\).
- Постпроцессинг/индексация (contraction hierarchies, hub labeling) требует дополнительной памяти и времени на предвычисление, но даёт очень быстрые запросы (часто миллисекунды/микросекунды).
- Если граф не влезает в ОЗУ — использовать внешнюю память (memory-mapped files, external-memory algorithms), стриминг или приближённые методы.
Рекомендации для sparse (разрежённые) графы (\(E \ll V^2\))
- Структуры:
- Списки смежности (вектор списков пар (v, w)) — простые, память \(O(V+E)\).
- CSR (Compressed Sparse Row) — плотная компактная репрезентация, лучшая кэш-локальность, память \(O(V+E)\).
- Edge list — для экономии при одном проходе/сортировке.
- Алгоритмы:
- Однопарный поиск кратчайшего пути: Dijkstra + бинарная куча: \(O(E\log V)\) (точнее \(O((E+V)\log V)\)); с Fibonacci-кучей: \(O(E + V\log V)\).
- Для небольших целочисленных весов: Dial / Radix heap — часто быстрее, амортизированно близко к \(O(E + V)\).
- Для графов дорог: Contraction Hierarchies, ALT (landmarks) — дополнительные индексы, но ответы очень быстрые.
- Для отрицательных весов: Bellman–Ford \(O(VE)\) или Johnson (перевзвешивание + Dijkstra) для всех пар.
- Почему: списки/CSR минимизируют память и обход соседей; кучи уменьшают стоимость выбора минимального узла при редких ребрах.
Рекомендации для dense (плотные) графы (\(E \approx V^2\))
- Структуры:
- Матрица смежности (двумерный массив или битсеты) — память \(O(V^2)\), быстрый доступ к наличию ребра и веса.
- Для булевых/плотных операций — битсеты (SIMD/GPU-ускорение).
- Алгоритмы:
- Если нужен один источник: Dijkstra с простым массивом расстояний (без кучи) даёт \(O(V^2)\) и часто лучше в плотном графе.
- Для всех пар: Floyd–Warshall \(O(V^3)\) на матрице; иногда лучше алгоритмы на основе многократного Dijkstra (если веса неотрицательные).
- Для матричных операций — использовать блокирование, BLAS/GPU для ускорения.
- Почему: при \(E \sim V^2\) затраты на хранение матрицы приемлемы, и массивные операции по матрице дают лучшую производительность из‑за кэша и векторизации.
Практические советы и компромиссы
- Если память критична и граф разрежён — CSR + Dijkstra/ALT; если граф статичен и запросов много — потратить память на CH или hub-labeling.
- Если задачи — много однотипных запросов (all-pairs/много источников) и граф плотный — матрица + Floyd/матричные методы.
- Если веса целые в ограничённом диапазоне — использовать radix/Dial для скорости и простоты.
- Для очень больших графов — приблизительные методы (landmarks, sketching), внешняя память или распределённая обработка.
Коротко: для sparse — \(O(V+E)\) структуры (списки/CSR) + Dijkstra/специализированные кучи/CH; для dense — \(O(V^2)\) матрица + алгоритмы на матрице (Dijkstra\(O(V^2)\) или Floyd–Warshall\(O(V^3)\)), либо битсеты/GPU для ускорения.