Поиск пути через четырехмерные данные

Question

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

Я использовал традиционный алгоритм поиска A * и взломал его, чтобы заставить его работать в 3-х измерениях и с векторами ветра.

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

Я чувствую, что у меня это работает "хорошо", но это кажется очень смешным.

Есть ли лучший, более эффективный способ поиска пути по таким данным (возможно, генетический алгоритм или нейронная сеть) или что-то, чего я даже не рассматривал? Может быть, динамика жидкости? Я не знаю?

Редактировать: подробности.

Данные - векторы ветра (направление, величина). Данные расположены на расстоянии 15x15 км на 25 различных уровнях высоты.

Под «не всегда работает» я подразумеваю, что он выберет тупой путь для самолета, потому что вес пути такой же, как у другого пути. Это хорошо для поиска пути, но неоптимальный для плоскости.

Я принимаю во внимание много вещей для каждого изменения узла:

• Стоимость подъема по убыванию.
• сопротивление ветра.
• Игнорирование узлов со слишком высоким сопротивлением.
• Стоимость диагонали тавель против прямой и т. Д.

Я использую евклидово расстояние в качестве эвристического или H-значения. Я использую различные факторы для моего веса или значения G (список выше).

Спасибо!

Answer 1

Вы всегда можете найти компромисс с оптимизацией по времени, используя взвешенный A *.

взвешенный A * [или A * epsilon], который, как ожидается, найдет путь быстрее.тогда A *, но путь не будет оптимальным [Тем не менее, он дает вам оценку его оптимальности в качестве показателя вашего эпсилона / веса].

Answer 2

A * не рекламируется как самый быстрый алгоритм поиска; это гарантирует, что первое найденное решение будет наилучшим (при условии, что вы предоставили допустимую эвристику). Если у вас не работает в некоторых случаях, то что-то не так с некоторыми аспектами вашей реализации (возможно, с механикой A *, может быть, специфичные для домена вещи; учитывая, что вы не предоставили никаких деталей, не могу сказать, более того).

Если это слишком медленно, вы можете пересмотреть эвристику, которую вы используете.

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

Answer 3

Планируете ли вы оффлайн или онлайн?

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