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

[_genius_]

По работе возникла следующая задача:
Есть две трехмерные поверхности состоящие из точек, каждой точке сопоставлено число, пусть это будет энергия.
Нужно сблизить эти поверхности так чтобы разность энергий близлежащих (одна от первой поверхности, другая от второй) точек была максимальной при этом не допуская наложения (общий объем равен нулю).
Со степенью зависимости от расстояния я ещё не определился, пусть это будет свободный параметр.
На входе 4$\cdot$кол-во точек переменных (разности координат и энергий).
На выходе всего 6 (3 степени свободы перемещения, 3 степени свободы вращения), т.к. двигать надо лишь одну поверхность и целиком, т.е. все её точки сразу.
Разумеется, однозначного решения здесь нет, поэтому нужна пошаговая оптимизация, но вот как именно это сделать я не представляю, уже 2 недели бью голову и пока безрезультатно.
Выглядит это примерно вот так, энергия нормализована чтобы лежать в интервале $±$0.5 https://i.ibb.co/4SGPqLx/Untitled.png


Наверняка кто-то где-то когда-то сталкивался с подобным.
Я пока вижу только один способ хоть как-то упростить задачу: тупо перебрать все возможные углы с шагом допустим в 30 градусов, тогда мне надо провести 1728 оптимизаций, зато уже только с перемещением без вращения. И главное это было бы очень легко параллелизировать. Но если можно проще - было бы здорово.

[alex55555]

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

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

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

Хотя да, это не самое оптимальное решение, но оно близко к оптимуму.

[_genius_]

Эх если б все было так просто. Допустим минимум находится в каком-нибудь маленьком углублении (а по факту так оно и есть), тогда совместить его с какой угодно точкой другой поверхности без наложения оных друг на друга невозможно.
Однозначного решения нет, но оно и не требуется. В идеале нужна какая-то функция, которая оценит текущую позицию в зависимости от разностей позиций и энергий. При этом надо учитывать только те пары точек, которые расположены сравнительно недалеко друг от друга, сразу отсекая остальные, т.к. точек на каждой поверхности по 30000. Отталкиваясь от этой функции нужно рассчитать куда и как двигаться дальше. И все бы ничего, если бы точки надо было двигать независимо друг от друга, но двигать надо всю поверхность целиком, причем не только перемещать, но ещё и вращать, причем опять-таки всю целиком. Я вот не знаю, а возможно ли это в принципе? До сих пор мне казалось, что любой процесс который можно представить можно и симулировать/запрограммировать, но теперь я в этом сомневаюсь.
Пока писал ответ, в голову пришла совсем безумная идея:
1) совмещаем центры поверхностей, чтобы одна лежала в другой
2) вращаем одну из них на 3 случайных угла вокруг осей x,y,z
3) выталкиваем её вдоль случайного вектора до тех пор пока наложение не исчезнет (знать бы как это сделать поэффективнее)
4) рассчитываем оптимальность позиции учитывая только сравнительно близкие точки
повторяем 1-4 много-много раз, держа в памяти только самую лучшую позицию, а точнее 3 угла и вектор, которые к ней привели. Опять-таки это было бы легко параллелизировать.

[Dmitriy40]

(Оффтоп)

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

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

Со степенью зависимости от расстояния я ещё не определился, пусть это будет свободный параметр.

Чем-то мне это не нравится: при низких степенях выгоднее расположить не слишком далеко много точек, а при высоких степенях выгоднее максимально сблизить отдельные точки. А не нравится тем что при этом могут быть разные стратегии оптимизации текущего положения, если не перебирать все возможные варианты (и на достаточно мелкой сетке для высоких степеней).

[_genius_]

Цитата:

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

Именно поэтому лучше было бы провести расчет несколько раз с разными степенями (допустим 2,3,4,5) и посмотреть что мне больше нравится.

[alex55555]

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

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

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

Экстремумов стоит много взять, алгоритм выявления удалённых друг от друга экстремумов тоже простой. Далее перебор по каждому экстремуму. Вручную можно ограничить зоны притяжения (например - около складки на большей поверхности). Повороты можно как для алгоритмов расположения графов вычислять по силам отталкивания. Сила отталкивания с одной стороны равна силе с другой - это критерий, по нему однозначно вычисляется положение. Ограничение при этом на позицию экстремума. Плюс что-то опять же вручную задавать.

В общем - задача простая. И количественно и качественно.

[_genius_]

alex55555 в сообщении #1356940 писал(а):

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

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

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

Слишком неточно получится, поверхности очень уж далеки от идеала. Если мне удастся убедить админа поставить какой-нибудь блендер на наш кластер, то этот вопрос действительно будет решен. Если же нет, то придется изобретать велосипед самому и это отнюдь не так просто как вы говорите. Я не представляю как это сделать быстро в случае если у каждой поверхности по 30 тысяч точек. И тут ничем пренебречь нельзя, т.к. форма у поверхностей произвольная.

alex55555 в сообщении #1356940 писал(а):

Экстремумов стоит много взять, алгоритм выявления удалённых друг от друга экстремумов тоже простой. Далее перебор по каждому экстремуму. Вручную можно ограничить зоны притяжения (например - около складки на большей поверхности). Повороты можно как для алгоритмов расположения графов вычислять по силам отталкивания. Сила отталкивания с одной стороны равна силе с другой - это критерий, по нему однозначно вычисляется положение. Ограничение при этом на позицию экстремума. Плюс что-то опять же вручную задавать.

Это все очень расплывчато, мне бы как-то поконкретнее. Пусть максимальное расстояние между релевантными экстремумами будет 5. Как мне отсечь лишние точки не проводя при этом $M\cdot N$ вычислений расстояний (а в моем случае это миллиард) с последующим сравнием с 5?
И как перевести в код вашу идею с поворотами? Это может быть легко вообразить, но конкретного алгоритма я здесь не вижу. Опять-таки после поворота может получиться что придется снова смещать, а после смещения снова поворачивать и постоянно проверять не произошло ли наложение.

[Dmitriy40]

Ну миллиард (а на самом деле 450 млн) расстояний посчитать совсем не страшно, это доли секунды даже на одном ядре центрального процессора, не говоря уж про GPU.
Тут можно конечно повозиться с известными методами оптимизации количества вычислений (преобразованием исходной структуры в список ближайших точек или делением всей структуры на соседние [под]области), но гораздо лучше думать над более высоким уровнем оптимизации - как быстро отбрасывать заведомо плохие расположения, не доводя расчёт до конца.
А вот тут я вижу конкретную засаду, причём в обоих случаях (и низкой степени расстояния и высокой): кроме как полным перебором всех комбинаций адекватную оценку не получить, и нет гарантии что в процессе оптимизации положения не пропустишь локальный максимум (особенно при высокой степени, там максимумы могут быть весьма острыми и придётся сетку делать очень мелкой - а это объём вычислений).
Единственное что хорошо при высокой степени расстояния - можно не проверять наложение каждый раз, оно автоматом будет исключено в процессе оптимизации положения, потому что энергия по мере погружения будет снова уменьшаться (точки расходятся и расстояние увеличивается, при высокой степени это пересилит уменьшение расстояния для других точек).

[vpb]

А можно спросить, какова постановка задачи ? Я читал тему, и как-то плохо понятно. Я догадываюсь, что это две молекулы (если правильно догадываюсь), но в чем задача математически ? (Впрочем, в том, что напишу что-то полезное, отнюдь не уверен).

Верно ли, что речь идет о следующем. Есть две поверхности $X$ и $Y$ в ${\mathbb R}^3$, и на них заданы две функции $f\colon X\longrightarrow {\mathbb R}$, $g\colon Y\longrightarrow {\mathbb R}$. Рассматриваются все движения $\Phi$ такие, что $\Phi(X)\cap Y=\emptyset$. Для каждого такого $\Phi$ находятся две точки $x_0\in X$, $y_0\in Y$, реализующие минимум
расстояния между $\Phi(X)$ и $Y$, и рассматривается величина $h(d(\Phi x_0,y_0))(f(x_0)-g(y_0))$, где $h$ --- некоторая функция, вид которой сейчас еще не известен. Требуется минимизировать эту величину, по всем допустимым $\Phi$.

[alex55555]

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

Слишком неточно получится, поверхности очень уж далеки от идеала.

Тогда уточняйте огибающую разбивая её на меньшие фигуры, а дальше опять - просто с какой стороны плоскости находится точка. Вообще софт для 3D моделирования уже имеет встроенные алгоритмы выявления пересечений, но там ведь всё вручную, то есть далеко не везде есть макроязык и возможность писать вменяемые программы.

Можно аппроксимировать поверхности шарами, что упростит нахождение пересечений - просто расстояние от центра шара должно быть больше радиуса, и так для всех шаров (эллипсоидов, но эту уже сложнее).

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

Я не представляю как это сделать быстро в случае если у каждой поверхности по 30 тысяч точек. И тут ничем пренебречь нельзя, т.к. форма у поверхностей произвольная.

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

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

И как перевести в код вашу идею с поворотами?

Задаёте произвольную ось для одной из поверхностей, но проходящую через экстремум. Далее крутите эту ось в телесном угле вокруг точки фиксации экстремума. Затем по положению оси восстанавливаете всю фигуру.

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

Опять-таки после поворота может получиться что придется снова смещать, а после смещения снова поворачивать и постоянно проверять не произошло ли наложение.

Да, в этом суть итеративных алгоритмов.

Общее решение я предложить не могу. Оно конечно найдёт наилучший вариант (если само решение кто-то найдёт), но этот наилучший вариант будет всего процентов на 10 лучше итеративно подобранного. Так что в вашем случае - либо ждать чудесного общего решения, либо взять и сделать на 90% оптимальное решение.

-- 26.11.2018, 21:21 --

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

Для каждого такого $\Phi$ находятся две точки $x_0\in X$, $y_0\in Y$, реализующие минимум
расстояния между $\Phi(X)$ и $Y$

Как я понял, автору нужно не две точки, а все сразу. То есть точки взаимодействуют по типу каждая с каждой. А две точки - это лишь произвольно выбранные места привязки. Как вариант устранения произвола предложен выбор экстремумов.

-- 26.11.2018, 21:23 --

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

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

А расходятся ли точки?

[Dmitriy40]

alex55555 в сообщении #1356989 писал(а):

А расходятся ли точки?

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

[alex55555]

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

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

Я имел в виду, что точки могут быть неподвижными (поверхность негибкая). В физике, возможно, всё гнётся, но есть ведь и другие приложения. Какой-нибудь анализ рынков не предполагает изменения данных.

[Dmitriy40]

alex55555
Я разумеется говорил везде о неизменных структурах/фигурах, сдвигаемых и вращаемых как целое.

[Papazol]

Фигуры ведь не обязательно выпуклые?

[_genius_]

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

А можно спросить, какова постановка задачи ? Я читал тему, и как-то плохо понятно. Я догадываюсь, что это две молекулы (если правильно догадываюсь), но в чем задача математически ? (Впрочем, в том, что напишу что-то полезное, отнюдь не уверен).

Верно ли, что речь идет о следующем. Есть две поверхности $X$ и $Y$ в ${\mathbb R}^3$, и на них заданы две функции $f\colon X\longrightarrow {\mathbb R}$, $g\colon Y\longrightarrow {\mathbb R}$. Рассматриваются все движения $\Phi$ такие, что $\Phi(X)\cap Y=\emptyset$. Для каждого такого $\Phi$ находятся две точки $x_0\in X$, $y_0\in Y$, реализующие минимум
расстояния между $\Phi(X)$ и $Y$, и рассматривается величина $h(d(\Phi x_0,y_0))(f(x_0)-g(y_0))$, где $h$ --- некоторая функция, вид которой сейчас еще не известен. Требуется минимизировать эту величину, по всем допустимым $\Phi$.

Я к сожалению не совсем математик, но в целом похоже на правду. Я только не понимаю, что вы подразумеваете под $x_0, y_0$, ведь из моих предыдущих сообщений видно что эта "h" должна зависеть от всех релевантных (находящихся достаточно близко) пар точек, а не от какой-то одной конкретной пары.

-- Ср ноя 28, 2018 03:18:07 --

alex55555 в сообщении #1356989 писал(а):

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

Слишком неточно получится, поверхности очень уж далеки от идеала.

Тогда уточняйте огибающую разбивая её на меньшие фигуры, а дальше опять - просто с какой стороны плоскости находится точка. Вообще софт для 3D моделирования уже имеет встроенные алгоритмы выявления пересечений, но там ведь всё вручную, то есть далеко не везде есть макроязык и возможность писать вменяемые программы.

Можно аппроксимировать поверхности шарами, что упростит нахождение пересечений - просто расстояние от центра шара должно быть больше радиуса, и так для всех шаров (эллипсоидов, но эту уже сложнее).

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

Я не представляю как это сделать быстро в случае если у каждой поверхности по 30 тысяч точек. И тут ничем пренебречь нельзя, т.к. форма у поверхностей произвольная.

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

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

И как перевести в код вашу идею с поворотами?

Задаёте произвольную ось для одной из поверхностей, но проходящую через экстремум. Далее крутите эту ось в телесном угле вокруг точки фиксации экстремума. Затем по положению оси восстанавливаете всю фигуру.

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

Опять-таки после поворота может получиться что придется снова смещать, а после смещения снова поворачивать и постоянно проверять не произошло ли наложение.

Да, в этом суть итеративных алгоритмов.

Общее решение я предложить не могу. Оно конечно найдёт наилучший вариант (если само решение кто-то найдёт), но этот наилучший вариант будет всего процентов на 10 лучше итеративно подобранного. Так что в вашем случае - либо ждать чудесного общего решения, либо взять и сделать на 90% оптимальное решение.

-- 26.11.2018, 21:21 --

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

Для каждого такого $\Phi$ находятся две точки $x_0\in X$, $y_0\in Y$, реализующие минимум
расстояния между $\Phi(X)$ и $Y$

Как я понял, автору нужно не две точки, а все сразу. То есть точки взаимодействуют по типу каждая с каждой. А две точки - это лишь произвольно выбранные места привязки. Как вариант устранения произвола предложен выбор экстремумов.

-- 26.11.2018, 21:23 --

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

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

А расходятся ли точки?

Для выявления пересечений наверное лучше и правда использовать "блендер". Мне это кажется слишком сложной задачей (по крайней мере если все делать серьезно и максимально точно) чтобы решать её самому с нуля.

Надо будет попробовать создать тестировные примерчики где точек поменьше раз эдак в 50-100, а потом уже применить готовое решение к основной задаче.

Я всеми конечностями за итеративную оптимизацию. Просто я честно не могу себе представить последствия вращений, чисто интуитивно мне кажется что из-за них ни о какой сходимости можно и не мечтать.

-- Ср ноя 28, 2018 03:20:06 --

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

alex55555 в сообщении #1356989 писал(а):

А расходятся ли точки?

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

И ведь правда! Надеюсь что так оно и будет. Это здорово сэкономило бы время расчета.

-- Ср ноя 28, 2018 03:21:09 --

Papazol в сообщении #1357174 писал(а):

Фигуры ведь не обязательно выпуклые?

К сожалению нет, я думаю это видно из картинок. Там совсем безумные неправильные формы.