Весьма нетривиальная оптимизация

[Dmitriy40]

_genius_
Я собственно на что хотел обратить внимание: если допустимы неограниченные сближения точек, то решение быстро сваливается в ближайший локальный максимум и из него уже не выйдет. А максимумов этих рассыпано по ландшафту немеряно (стоит лишь сблизиться любым двум точкам разных фигур - и вуаля, слипаются и максимум). Как в таких условиях искать глобальный максимум - вопрос отдельный.
В общем на мой взгляд думать надо не о полумиллиарде взаимных расстояний и не о 300 тысячах умножений при преобразовании координат и не о проверке пересечений, а как выбрать сетку расчётов чтобы не пропустить все максимумы и в то же время не состариться в ожидании.
Судя по первым картинкам я бы предложил для начала удалить все внутренние точки в обеих фигурах если таковые есть. Потом аппроксимировать каждую фигуру набором пересекающихся сфер (два-три десятка) чуть большего диаметра (чтобы точки заведомо не соприкоснулись) и искать сближение уже таких фигур, для наборов сфер это намного проще. И лишь найдя более-менее устойчивое взаимное положение (т.е. возвращающееся в себя при небольших возмущениях) возвращаться к точным фигурам и досчитывать уже по ним. Не ограничиваясь первым найденным перебрать все устойчивые расположения если нужен именно глобальный максимум, а не лишь бы любой локальный. Извините что так абстрактно.

[vpb]

_genius_ в сообщении #1357242 писал(а):

Я к сожалению не совсем математик, но в целом похоже на правду

Так от Вас и не ожидают, что Вы сформулируете вопрос так же четко, как это сделал бы математик. Однако же то, что Вы написали, вообще как-то очень расплывчато и туманно.

Что я понял ? Есть два трехмерных тела. Они заданы тем, что заданы ограничивающие их поверхности. Поверхности заданы приблизительно, а именно, для обоих поверхностей заданы несколько десятков тысяч точек на этих поверхностях. Потом, для каждой точки на одной или другой поверхности, задано некоторое число, называемое "энергия". Затем, положение одного тела в пространстве фиксируется, а для второго рассматриваются всевозможные положения (т.е. результат перемещения тела в пространстве, при этом тело считается твердым, т.е. полностью сохраняет свою форму), при которых оно не пересекает первое тело. Для каждого такого положения вычисляется некоторое число. Главный вопрос: по какой формуле оно вычисляется ?

Может быть по такой:

$$ f(\Phi)=\sum_{i=1,\ldots,N;\ j=1,\ldots,M} h(d(x_i, \Phi y_j)) (f(x_i)-g(y_j)) ? $$

где $x_i$ --- это точки первой поверхности, $M$ штук, $y_j$ --- точки второй, $N$ штук, $d(x,y)$ --- обычное расстояние между точками в трехмерном пространстве, $\Phi$ означает то самое движение (а $\Phi y$ соответственно --- результат применения движения к точке $y$) ?

В случае чего, не обязательно писать много формул, просто опишите это число, которое зависит от положения поверхностей в пространстве, своими словами, главное, чтоб не очень туманно.

[_genius_]

vpb в сообщении #1357281 писал(а):

_genius_ в сообщении #1357242 писал(а):

Я к сожалению не совсем математик, но в целом похоже на правду

Так от Вас и не ожидают, что Вы сформулируете вопрос так же четко, как это сделал бы математик. Однако же то, что Вы написали, вообще как-то очень расплывчато и туманно.

Что я понял ? Есть два трехмерных тела. Они заданы тем, что заданы ограничивающие их поверхности. Поверхности заданы приблизительно, а именно, для обоих поверхностей заданы несколько десятков тысяч точек на этих поверхностях. Потом, для каждой точки на одной или другой поверхности, задано некоторое число, называемое "энергия". Затем, положение одного тела в пространстве фиксируется, а для второго рассматриваются всевозможные положения (т.е. результат перемещения тела в пространстве, при этом тело считается твердым, т.е. полностью сохраняет свою форму), при которых оно не пересекает первое тело. Для каждого такого положения вычисляется некоторое число. Главный вопрос: по какой формуле оно вычисляется ?

Может быть по такой:

$$ f(\Phi)=\sum_{i=1,\ldots,N;\ j=1,\ldots,M} h(d(x_i, \Phi y_j)) (f(x_i)-g(y_j)) ? $$

где $x_i$ --- это точки первой поверхности, $M$ штук, $y_j$ --- точки второй, $N$ штук, $d(x,y)$ --- обычное расстояние между точками в трехмерном пространстве, $\Phi$ означает то самое движение (а $\Phi y$ соответственно --- результат применения движения к точке $y$) ?

В случае чего, не обязательно писать много формул, просто опишите это число, которое зависит от положения поверхностей в пространстве, своими словами, главное, чтоб не очень туманно.

Вы все правильно поняли, если надо конкретизировать "h", то пусть $h = \frac{1}{d^3}$ при условии что $f(\Phi)$ надо будет максимизировать. Желательно иметь возможность заменить эту тройку на любое положительное число, чтобы уже на деле узнать какая степень там лучше подходит.

[vpb]

Так тогда, вообще говоря, $f(\Phi)$ не ограничено сверху, и как ставить вопрос о максимуме ? Конкретно, если есть две точки $x_i$ и $y_j$ такие, что (а) можно $x_i$ непосредственно прислонить к $y_j$, для подходящего $\Phi$, и (б) $f(x_i)-g(y_j)>0$ , то $f(\Phi)$ не ограничено (если их прислонить друг к другу, то вообще обращается в плюс бесконечность).

[Dmitriy40]

Ну от бесконечности уйти несложно, например априорно запретив сближение ближе фемтометра, только задача всё равно сводится к нахождению положения с максимальным количеством касающихся точек - что вовсе не обязательно будет максимальным сближением фигур. Контрпример: пусть фигуры имеют по три одинаковых выступающих "уса", 3 пары точек на которых могут сблизиться на тот самый фемтометр, а все остальные точки при этом не сближаются ближе нанометра - положение максимума функции будет явно не максимально близким. Потому я выше и говорил что столь узкие пики (максимумов) и такое огромное их количество в пространстве положений губит на корню перебор.

[vpb]

Dmitriy40 в сообщении #1357359 писал(а):

Ну от бесконечности уйти несложно, например априорно запретив сближение ближе фемтометра, только задача всё равно сводится к нахождению положения с максимальным количеством касающихся точек -

Что-то это противоречит предполагаемому физическому смыслу задачи. Не следует ли узнать более точный ответ у ТС ?

[Dmitriy40]

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

[vpb]

Dmitriy40 в сообщении #1357362 писал(а):

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

Так я же не против отнюдь.

[_genius_]

Хорошо, а если $h = a\cdot e^{-b\cdot d^c}$ где a, b, c будут подобраны позже? Бесконечность исчезает без применения костылей.

[Dmitriy40]

(Оффтоп)

Забавный диалог тут происходит:
- Есть некая функция $f(x,y,z,a,b,c)$ от трёх координат и трёх углов поворота, в обозримом будущем найди при каких параметрах её значение максимально.
- А вид функции узнать можно?
- Придумаем потом, ты ищи, ищи!

[upgrade]

_genius_ в сообщении #1356789 писал(а):

Нужно сблизить эти поверхности так чтобы разность энергий близлежащих

Непонятно, зачем сближать и что такое близлежащие. Еслиб не это, может надо находить максимальный объем между поверхностями (при константе расстояния между ними, если оно единственным образом определимо)?

[_genius_]

upgrade в сообщении #1357384 писал(а):

_genius_ в сообщении #1356789 писал(а):

Нужно сблизить эти поверхности так чтобы разность энергий близлежащих

Непонятно, зачем сближать и что такое близлежащие. Еслиб не это, может надо находить максимальный объем между поверхностями (при константе расстояния между ними, если оно единственным образом определимо)?

"Зачем" это не так важно. Каюсь что не смог сразу сформулировать математически, но может оно и к лучшему, т.к. vpb с этим отлично справился.

[vpb]

Dmitriy40 в сообщении #1357380 писал(а):

Забавный диалог тут происходит:

Гм. Что ученый-прикладник не смог сразу внятно объяснить постановку задачи, дело то это обычное. На него тут как раз пенять незачем, имхо.

[Dmitriy40]

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

[vpb]

Есть такая возможность ускорить вычисление $f(\Phi)$. Рассмотрим функции от $x$ и $y$:

$$ p(x)=\sum_{j=1}^M h(d(x,y_j))g(y_j)\,, \qquad q(y)=\sum_{i=1}^N h(d(x_i,y)) f(x_i)\,.$$

Тогда легко видеть, что

$$f(\Phi)=\sum_{j=1}^Mq(\Phi y_j)-\sum_{i=1}^Np(\Phi^{-1}x_i)$$

(следует учесть, что $d(x,\Phi y)=d(\Phi^{-1}x,y)$. Это подсказывает такой путь: затабулировать $p(x)$, $q(y)$ достаточно
плотно по ${\mathbb R}^3$, а потом пользоваться указанными соотношениями (интерполируя $p$ и $q$ из близлежащих затабулированных точек). Тогда вычисление $f(\Phi)$ будет требовать не миллиарда операций, а порядка ста тысяч.