Алгоритмические методы или приемы поиска конъюнкций в больших ансамблях векторов состояния?

Предположим, я хочу ответить на вопрос: пролетит ли Starman/Roadster особенно близко к каким-либо астероидам в ближайшие несколько лет? или попытаться предсказать соединения спутников вокруг Земли (например, SOCRATES Celestrak ), и у меня были эфемериды, TLE или интерполируемые таблицы векторов состояния.

Я мог бы распространять их небольшими временными шагами, вычислять все Н должности и все Н ( Н − 1 ) / 2 расстояния и поиск любого меньшего расстояния д с о н Дж , но это может быть не самый эффективный способ сделать это.

Вопрос: Какие существуют алгоритмические методы или приемы для более эффективного поиска такого рода? Предположим, что пропагаторы возвращают шестивектор (положение и скорость). Мне нужно объяснение или авторитетная ссылка, а не просто имя.

Этот вопрос отличается от алгоритмических методов или методов поиска соединений в ансамблях с высоким N кеплеровских элементов? потому что он специально спрашивает о методах, которые работают с векторами состояния (либо в таблице, либо распространяются по запросу), которые могут включать эффекты n тел (например, Солнце движется, Юпитер делает свое дело и т. д.)

Я решил повторно задать этот вопрос, основываясь на этом совете . Я ожидаю, что на этот раз он полетит, а не «соединится» (столкнется) со своим родственным вопросом .
Если я правильно понимаю, что вы спрашиваете о задаче о паре ближайших точек в шестимерном евклидовом пространстве, то этот вопрос достаточно общий, чтобы соответствовать Math.SE. Или вы указываете на что-нибудь, связанное с орбитальной механикой?
Почему вас интересуют соединения скоростей? Т.е. почему вы включаете 3 измерения относительно скорости в вектор состояния. Первоначальный вопрос о Starman/Roadster касается только позиций.
@EverydayAstronaut соединение - это когда два объекта достигают одинаковой точки в четырехмерном пространстве-времени. ( Икс с , у с , г с , т с ) . я про скорость не спрашивал т с . Однако , чтобы предсказать, произойдет ли это в какой-то момент в будущем, вам нужны два их вектора состояния и две эпохи. ( Икс 1 , у 1 , г 1 , в Икс 1 , в у 1 , в г 1 , т 1 ) и ( Икс 2 , у 2 , г 2 , в Икс 2 , в у 2 , в г 2 , т 2 ) . Это минимальная проблема. Мой вопрос касается ансамбля н векторы состояния и эпохи ( Икс я , у я , г я , в Икс я , в у я , в г я , т я ) и глядя на О ( н 2 ) пары и предсказание союзов для каждой из них.
я думал ты шляпа н состояния ( Икс я , у я , г я , в Икс я , в у я , в г я ) и хотите найти ближайшую пару точек среди этих н точек в 6 измерениях для каждого дискретного момента времени. Пожалуйста, помогите мне с этой настройкой 4-D. Какой тип метрики вы используете в этом пространстве для этой цели? Что-то вроде Минковского? Я имею в виду, что вам нужно взвешивать пространственное и временное расстояние.
@EverydayAstronaut, если вы посмотрите на ссылку СОКРАТ в вопросе: «Порог вычислений: 5,0 км». Итак, если есть время, когда они находятся в пределах 5,0 км друг от друга (например, один раз можно выбрать другое число), тогда произошло соединение .
Итак, вы пытаетесь найти 2 точки, одинаковые в пространстве, в одно и то же время. Для дискретных по времени наборов позиций (3D) это определенно проблема с ближайшими парами точек. Если вы не найдете здесь помощи, я рекомендую Math.SE. В Engineering.SE пока нет тегов "контактная механика" и "многочастичные системы" :-(
@EverydayAstronaut Я нигде не вижу слова «точно»; Я только что упомянул «... в пределах 5,0 км друг от друга ...» прямо над вашим комментарием. В любом случае я не прошу кого-то объяснить мне, как это сделать или решить из первых принципов, я прошу ссылки на существующие алгоритмы, характерные для ситуации ансамбля связанных орбит, распространяющихся в гравитационном поле Земли .

Ответы (1)

Допустим, вы хотите сделать что-то «разумное», например, собрать посекундные соединения за столетний период для всех объектов, для которых вы можете получить векторы состояния (сотни тысяч или около того?)

У вас есть О ( С ⋅ Н 2 ) подход, так что... о ≈ 10 20

Да, я вижу, что есть проблема.

В Солнечной системе все движется с ограниченной скоростью. Затем мы можем воспользоваться тем фактом, что объекты могут перемещаться только на определенное расстояние за каждый временной шаг.

Вот алгоритм разделения времени:

  1. Просканируйте всю кучу данных вектора состояния, чтобы найти максимальную скорость. О ( С ⋅ Н ) . Это должна быть приемлемая среда выполнения, поскольку в противном случае вы даже не смогли бы сохранить все эти векторы состояния.

Вы получите крайний случай, например скорость перигелия Икара 1566 года , порядка ~ 100 км / с. Таким образом, для наихудшего случая относительной скорости, когда объекты движутся прямо навстречу друг другу, мы можем принять верхний предел около 200 км/с.

  1. Теперь для каждого объекта по одному:

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

За эти 10 дней расстояния могут сократиться не более чем на ~1 а.е., если относительные скорости могут быть не более 200 км/с.

Теперь для 10 «менее грубых» временных шагов между 1 днем ​​учитывайте только те объекты в пределах 1 а.е. в «грубом» временном шаге. Во многих случаях это будет более короткий список.

Между ними снова вставьте 10 «еще менее грубых» временных шагов по 2,4 часа. Здесь нам нужно учитывать только те, которые находятся в пределах 0,1 а.е. на «менее грубом» временном шаге. Это должно быть небольшое меньшинство в вашей базе данных векторов состояний.

При детализации временного шага ~ 15 минут мы свелись к прогону короткого списка 0,01 AU. Через 1,5 мин 0,001 а.е.

Если вы остановите разбиение здесь, будет только пара объектов (или ни одного!) для проверки на каждом временном шаге.

Для объектов, распределенных в объеме или даже сгруппированных вдоль одной двумерной плоскости, это асимптотически О ( Н 2 ) . То есть вам не нужно беспокоиться об ограничении степени детализации ваших временных шагов.

Даже для очень неприятной линейной кластеризации (которая, кстати, не относится к объектам Солнечной системы) это все еще в худшем случае О ( л о г ( С ) ⋅ Н 2 )

Таким образом, вы сможете просмотреть кучу за пару минут на ноутбуке.

Алгоритмические методы или приемы поиска конъюнкций в больших ансамблях векторов состояния?
СпросиСетьПолитика конфиденциальности1y, 0v