#algorithm #optimization #coordinates #shortest-path
#алгоритм #оптимизация #координаты #кратчайший путь
Вопрос:
Я пилот-парапланерист. Гонка на параплане определяется как набор виртуальных буев. Побеждает пилот, который первым пролетит через все буи.
Буй определяется двумя параметрами:
- координаты точки
- радиус
Это определяет цилиндр в трехмерном пространстве, но для простоты давайте оставим проблему в 2D. Гонка может выглядеть примерно так (приблизительный рисунок): 
A = 1000 м; B = 3000 м; C = 2000 м; D = 500 м
Пилот должен стартовать внутри круга A, затем пролететь внутри кругов B и C (или, по крайней мере, просто «коснуться» его) и должен закончиться внутри круга D.
Как вы вычисляете оптимальный (кратчайший) путь?
Результатом должны быть координаты всех сегментов, которые составляют часть кратчайшего пути.
Комментарии:
1. Вы можете использовать ограниченный градиентный спуск или некоторые из квази-ньютоновских альтернатив второго порядка.
2. Также не решение, а наблюдение. Кратчайший путь, если его расширить, будет начинаться в точке A и заканчиваться в точке E и будет путем, по которому мог бы пройти свет, если бы каждый круг был либо идеально отражающим (поворачивается в этой точке), либо прозрачным (проходит через круг к следующему).
3. Вам действительно нужен кратчайший путь? Это не будет физически осуществимо, поскольку его касательные прерывисты.
4. Кратчайший путь не обязательно самый быстрый. Направление ветра очень важно.
5. @btilly Да, я понял, пытаясь выяснить, могу ли я упростить эту проблему, расширив решение всего на 3 круга.
Ответ №1:
Если путь известен априори как ABCD и неизвестны только точные точки, то общее расстояние (в квадрате) можно записать как функцию от 4 переменных.
Одна параметризация точки i, конечно
x(t_i) = x0_i r_i * cos(t_i)
y(t_i) = y0_i r_i * sin(t_i)
Квадрат длины пути равен
D^2 = sum_{i = 1, n-1} (x(t_{i i}) - x(t_i))^2 (y(t_{i i}) - y(t_i))^2
Четыре переменные, для которых вы решаете, — это t_1, … t_4. После подстановки конечное выражение для D ^ 2 представляет собой довольно сложную квадратичную по синусу и косинусу. Вы должны минимизировать это количество.
Это вряд ли допускает аналитическое решение.
Вы также можете попробовать рациональную квадратичную параметризацию круга, но в итоге вы получите рациональную квартику. Не намного (любой?) Проще.
К счастью, даже такие сложные функции могут быть сведены к минимуму с помощью стандартных числовых алгоритмов нелинейной оптимизации, таких как (как кто-то предложил в комментариях) градиентный спуск.
В общем случае вы не можете гарантировать, что минимумы, найденные такими алгоритмами, являются глобальными. Но здесь кажется, что пространство решений может быть выпуклым, по крайней мере, для большинства проблемных случаев, что делает локальный минимум также глобальным.
Также, вероятно, существуют хорошие эвристические способы выбора начальных точек для численной итерации. Например, возьмите путь вдоль центров окружностей. Для каждого круга выберите среднюю точку между двумя его пересечениями с траекторией.
С аналогичной логикой вы можете ограничить значения каждого t_i диапазоном, всегда меньшим pi .