Близкая точка обнаружения приближения

Question

У меня есть большой набор многочленов 3-го порядка в 3D.

в матричной форме

Pn = [1, т, т ² , т ⁴ ] * [An]

[Pn] и [An] являются матрицами 1xN и 4xN соответственно

каждая функция имеет вес Wn. Я хочу, чтобы для некоторых n, m, T и t0 был найден первый t, где t>t0 такой, что

(Wn * Wm) * | Pn-Pm | ^-2 > T

кроме подхода "попробуй все" (n ² ), я даже не уверен, с чего начать, в этом отношении, я не уверен, как ответить на это даже для известного n & m.

Любые идеи

Edit:

• установленный размер порядка 10-1000
• вес распределен ~ логарифмически (очень мало больших, много маленьких)
• этот тест будет во внутреннем цикле симулятора n-тела, поэтому он будет выполняться много
• Версии, которые хорошо (амортизируются) при поиске нового ответа после изменения одного пути - это хорошо.

Answer 1

Не зная, разрешимо ли это с помощью аналитических средств, существует много подходов к поиску пространства и поиску любого t, соответствующего этим критериям.

Генетические алгоритмы, моделируемый отжиг и другие алгоритмы для оптимизации приходят на ум.

Answer 2

Насколько велика N? Возможен ли исчерпывающий поиск?

Я бы задал вопрос на форумах numpy или scipy и освежил свои навыки работы с питоном. Могу поспорить, что вы могли бы превратить это в проблему минимизации и использовать fmin или BFGS или какой-либо другой ограниченный квазиньютоновский алгоритм, чтобы найти разумный минимум. Возможно, минимизируйте разницу между t и T. Если в ваших матрицах нет чего-то странного, похоже, что ваше пространство поиска, по крайней мере, непрерывно.

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

Answer 3

ОК, чтобы посеять горшок:

• Использование некоторой формы алгоритма "поиска близких пар" создает кучу с этими парами в t0 и другие моменты времени.
• Вытащите ближайшую найденную пару
• если достаточно близко и раньше, чем лучший, держите
• найдите, находятся ли они ближе или дальше друг от друга
• разделите разницу между текущей парой и следующей в "более близкой" стороне и добавьте эту кучу.

Мысли