if (std::binary_search(std::begin(powers), std::end(powers), sum)) {
const auto it = std::lower_bound(std::begin(powers), std::end(powers), sum);
вы тут при попадании внутрь if второй раз бинарный поиск делаете (aka lower_bound), зачем?
нужно сделать 1 раз lower_bound и сравнить значение по итератору с искомым.
Согласен, номер клетки в матрице можно использовать как ключ, если размер матрицы заранее известен, что в нашем случае конечно же так и есть. Соседние ключи в этом случае вычисляются тоже элементарно.
Для ответа на первый вопрос, давайте рассмотрим ситуацию в одномерном пространстве. Две точки с координатами 0.9 и 1.1, первая получит ключ 0, вторая 1, но расстояние между ними 0.2, то есть в нашем случае меньше метра.
По второму вопросу — ключ выбран таким для того, чтобы можно было легко рассчитать ключи соседних клеток и посмотреть что там. А с точки зрения вычисления — ключ очень простой: два отбрасывания дробной части, сдвиг и побитовое ИЛИ.
На данный момент маршруты с учетом пробок не планируются (не хватает людей и времени), это большая задача.
Сложность доработки очень сильно зависит от вида, в котором можно получить данные о пробках. Если это будет просто таблица новых весов сегментов, то изменений практически не требуется. Но думаю в реальной жизни данные о пробках такими идеальными не бывают и большая часть работы будет сосредоточена в том, чтобы привести эти данные к виду «просто таблица новых весов сегментов».
Для первой задачи R-tree безусловно подошел бы. Но сложность склейки вершин полагаю была бы n log(n), а наше решение для нашего частного случая имеет линейную сложность. Вероятно в абсолютных величинах время обработки нашего набора данных отличалось бы не драматически, но наше решение довольно простое в реализации, так почему бы и нет.
По второй части возникает вопрос сложности предпросчета при меняющихся весах (например пробки).
Думаю, что мы могли бы его использовать, если бы нашли. Но вряд ли бы это сильно сэкономило нам время, так как для того, чтобы запустить это решение на наших данных, сами данные нужно было бы привести в нормальный вид, а потом преобразовать в формат OSM (это наверное совсем несложно), выполнив как трансформацию графа в соответствии с ограничениями, так и предобработку для «склеивания» вершин, а это вещи которые заняли у нас больше 90% времени.
Если мы будем в будущем развивать наше решение, то возможно переход на OSRM в качестве поискового движка будет иметь смысл. Еще раз спасибо за ссылку.
Когда искали готовое решение — этот маршрутизатор не нашли. Но сейчас бегло посмотрев, не смог сходу найти хорошо документированное API или возможность разместить на своих серверах, и как его можно использовать на своих, а не OpenStreetMaps данных. По этим критериям мы бы его исключили, даже если бы нашли.
Если времени на статью не найдете, напишите хотя бы заметку.
Мы хотели попробовать распределенную дейкстру из Parallel BGL, чтобы подсократить время поиска, но к сожалению не успели. С удовольствием послушал бы чей-то опыт про это. Стоит ли оно того.
Думали об этом, но поскольку ищем маршрут с минимальным времени сходу не придумали какую эвристику использовать для A*. Интуитивно расстояние до цели казалось неподходящим. Но может быть мы были не правы и позже попробуем.
вы тут при попадании внутрь if второй раз бинарный поиск делаете (aka lower_bound), зачем?
нужно сделать 1 раз lower_bound и сравнить значение по итератору с искомым.
По второму вопросу — ключ выбран таким для того, чтобы можно было легко рассчитать ключи соседних клеток и посмотреть что там. А с точки зрения вычисления — ключ очень простой: два отбрасывания дробной части, сдвиг и побитовое ИЛИ.
Сложность доработки очень сильно зависит от вида, в котором можно получить данные о пробках. Если это будет просто таблица новых весов сегментов, то изменений практически не требуется. Но думаю в реальной жизни данные о пробках такими идеальными не бывают и большая часть работы будет сосредоточена в том, чтобы привести эти данные к виду «просто таблица новых весов сегментов».
По второй части возникает вопрос сложности предпросчета при меняющихся весах (например пробки).
Если мы будем в будущем развивать наше решение, то возможно переход на OSRM в качестве поискового движка будет иметь смысл. Еще раз спасибо за ссылку.
Мы хотели попробовать распределенную дейкстру из Parallel BGL, чтобы подсократить время поиска, но к сожалению не успели. С удовольствием послушал бы чей-то опыт про это. Стоит ли оно того.