Аппроксимация графов дорожных сетей

📒 Рассматриваются задачи аппроксимации графов дорожных сетей в двух постановках: 1) минимизация погрешности определения расстояний при аппроксимации исходного графа сети графом заданной размерности, 2) минимизация размерности аппроксимирующего графа при заданном ограничении на погрешность определения расстояний. Для решения задач предлагаются алгоритмы, строящие аппроксимирующий граф путем декомпозиции и разбиения исходного графа. Рассматриваются задачи эффективного (по времени) определения кратчайших путей между всеми вершинами и метрических характеристик графов дорожных сетей. Показывается эффективность разработанных алгоритмов в сравнении с известными алгоритмами с помощью вычислительных экспериментов на большом наборе графов реальных дорожных сетей России, Европы и Северной Америки.