Оптимизация алгоритма Дейкстры для кэширования

Мне нужно найти оптимальный путь, соединяющий две плоские точки. Мне дана функция, определяющая максимальную скорость продвижения, которая зависит как от местоположения, так и от времени.

Мое решение основано на алгоритме Дейкстры. Сначала я покрываю плоскость двумерной решеткой, рассматривая только дискретные точки. Точки соединяются со своими соседями в указанном порядке, чтобы получить достаточное разрешение направления. Затем я нахожу лучший путь с помощью (вроде) алгоритма Дейкстры. Далее я улучшаю разрешение/качество найденного пути. Я увеличиваю плотность решетки и порядок связности соседей, а также ограничиваю поиск только точками, достаточно близкими к уже найденному пути. Это может повторяться до тех пор, пока не будет достигнуто необходимое разрешение.

В целом это работает хорошо, но, тем не менее, я хотел бы улучшить общую производительность алгоритма. Я реализовал несколько трюков, таких как переменная плотность решетки и порядок связности соседей, основанные на «гладкости» функции цены. Однако я считаю, что есть потенциал для улучшения самого алгоритма Дейкстры (применительно к моему конкретному графику), который я еще не мог полностью реализовать.

Сначала давайте договоримся о терминологии. Я разделил все точки решетки на 3 категории:

• холодные— точки, которые не были достигнуты алгоритмом.
• теплый- точки, которые достигнуты, но еще не полностью обработаны (т.е. имеют потенциал для улучшения)
• стабильные- точки, которые полностью обработаны.

На каждом шаге алгоритм Дейкстры выбирает «самую дешевую» теплуюточку решетки, а затем пытается улучшить цену своих соседей. Из-за особенностей моего графика я получаю нечто вроде облака стабильныхточек, окруженных тонким слоем теплыхточек. На каждом шаге обрабатывается теплаяточка на периметре облака, затем она добавляется к стабильномуоблаку, а теплыйпериметр (потенциально) расширяется.

Проблема в том, что теплыеточки, которые последовательно обрабатываются алгоритмом, обычно пространственно (следовательно – топологически) не связаны. Типичный теплыйпериметр состоит из сотен тысяч точек. На каждом шаге следующая теплаяточка для обработки является псевдослучайной (пространственной), поэтому вероятность того, что две связанные точки будут обработаны одна за другой, практически исключена.

Это действительно создает проблему с использованием кэша ЦП. На каждом шаге ЦП имеет дело с псевдослучайным расположением памяти. Из-за большого количества теплыхточек - все релевантные данные могут не поместиться в кэш процессора (порядка десятков-сотней МБ).

Что ж, это действительно следствие алгоритма Дейкстры. Вся идея заключается в том, чтобы явно выбрать самую дешевую теплуюточку, независимо от других свойств.

Однако интуитивно очевидно, что точки на одной стороне периметра большого облака не имеют никакого смысла для точек на другой стороне (в нашем конкретном случае), и нет проблем поменять местамиих обработку приказ.

Поэтому я задумался о способах "настройки" порядка обработки теплыхточек, но без ущерба для алгоритма в целом. Я думал о нескольких идеях, таких как погружение самолета в блоки и их частичное самостоятельное решение до тех пор, пока не будут выполнены некоторые критерии, то есть их решению могут помешать. Или, в качестве альтернативы, проигнорируйте вмешательство и потенциально разрешите «повторное разрешение» (т.е. переход от стабильногообратно к теплому).

Однако до сих пор я не мог найти строгого метода.

Есть идеи как это сделать? Возможно, это известная проблема с существующими исследованиями и (надеюсь) решениями?

Заранее спасибо. И извините за длинный вопрос.