Мне нужно найти оптимальный путь, соединяющий две плоские точки.Мне дана функция, которая определяет максимальную скорость продвижения, которая зависит как от местоположения, так и от времени.
Мое решение основано на алгоритме Дейкстры.Сначала я покрываю плоскость двумерной решеткой, рассматривая только дискретные точки.Точки соединяются с соседями до указанного порядка, чтобы получить достаточное разрешение по направлению.Затем я нахожу лучший путь с помощью (вроде) алгоритма Дейкстры.Далее я улучшаю разрешение / качество найденного пути.Я увеличиваю плотность решетки и соседний порядок связности, а также ограничиваю поиск только точками, достаточно близкими к уже найденному пути.Это может повторяться до тех пор, пока не будет достигнуто необходимое разрешение.
В целом это работает хорошо, но, тем не менее, я хотел бы улучшить общую производительность алгоритма.Я реализовал несколько трюков, таких как переменная плотность решетки и соседний порядок подключения, основанный на «плавности» функции цены.Однако я полагаю, что существует потенциал для улучшения самого алгоритма Дейкстры (применимого к моему конкретному графику), который я еще не смог полностью реализовать.
Сначала давайте договоримся о терминологии.Я разбил все точки решетки на 3 категории:
- холодная - точки, которые не были достигнуты алгоритмом.
- теплая - точки, которые достигнуты, но еще не полностью обработаны (т.е. имеют потенциал для улучшения)
- стабильный - точки, которые полностью обработаны.
На каждом шагеАлгоритм Дейкстры выбирает «самую дешевую» теплую точку решетки, а затем пытается повысить цену своих соседей.Из-за характера моего графика я получаю нечто вроде стабильных точек, окруженных тонким слоем теплых точек.На каждом шаге обрабатывается теплая точка по периметру облака, затем она добавляется к стабильному облаку и теплый периметр (потенциально) расширяется.
Проблема в том, что теплых точек, которые, следовательно, обрабатываются алгоритмом, обычно пространственно (следовательно, топологически) не связаны .Типичный теплый периметр состоит из сотен тысяч точек.На каждом шаге следующая теплая точка обработки является псевдрандомальной (пространственно), поэтому практически нет шансов, что две связанные точки обрабатываются одна за другой.
Это действительно создает проблему сИспользование кэша процессора.На каждом шаге процессор имеет дело с псевдослучайным расположением памяти.Поскольку существует большое количество теплых точек - все соответствующие данные могут не соответствовать кэш-памяти ЦП (это порядка десятков или сотен МБ).
Что ж, это действительно означаеталгоритм Дейкстры.Вся идея состоит в том, чтобы явно выбрать самую дешевую теплую точку, независимо от других свойств.
Однако интуитивно очевидно, что точки на одной стороне периметра большого облака не имеют никакого смысла дляточки на другой стороне (в нашем конкретном случае), и нет проблем с swap их порядком обработки.
Поэтому я думаю о способах "регулировки" warm порядок обработки баллов, но без ущерба для алгоритма в целом.Я подумал о нескольких идеях, таких как погружение самолета в блоки и частичное решение их независимо, пока не будут выполнены некоторые критерии, означающие, что их решение может быть нарушено.Или, в качестве альтернативы, игнорируйте помехи и, возможно, разрешите «повторное решение» (то есть переход от стабильный обратно к теплый ).
Однако пока я не смог найтистрогий метод.
Есть ли идеи, как это сделать?Возможно, это известная проблема с существующими исследованиями и (надеюсь) решениями?
Заранее спасибо.И извините за длинный вопрос.