Куб минимального объема
1,00
р.
На множестве точек n-мерного пространства определить координаты вершин n-мерного гиперкуба содержащего внутри себя все точки исходного множества, гиперкуб должен быть минимального объема.
Возникла вот такая задача, не могу придумать адекватный алгоритм. Может есть у кого-нибудь идеи?
Ответ
Если речь идет просто о каком-то работающем алгоритме (возможно неоптимальном), то я бы подошел к вопросу так:
Сначала составляется функционал, то есть некая функция с некими параметрами, которая выдает на гора 1 значение Далее уже можно применить любой алгоритм минимизации функционала (а их туча)
То есть с точки зрения алгоритмирования, интерес представляет только составление самого функционала.
Шаги вычисления функционала я бы видел такие:
Задаемся кубом, вычисляем его объем - обозначим его как V Берем каждую из точек и определяем находится точка внутри куба или нет Если точка внутри куба определяем излишний объем dv=0 Если точка вне куба излишний объем dv определяем как 2*V (как вариант - можно придумать что-то более интересное и непрерывное) Суммируем все dv и прибавляем к V
В итоге получим 2n-мерный функционал (координаты 1-го из ребер куба однозначно характеризуют его положение в пространстве), который просто надо минимизировать - то есть понять при каком положении куба полученный объем будет минимален.
Теперь дело за малым - засовываем полученный функционал в более-менее любой алгоритм минимизации функционала (по сути это вообще чуть ли не библиотечные функции в вычметодах), задаем некое начальное значение положения куба и вперед.
Возникла вот такая задача, не могу придумать адекватный алгоритм. Может есть у кого-нибудь идеи?
Ответ
Если речь идет просто о каком-то работающем алгоритме (возможно неоптимальном), то я бы подошел к вопросу так:
Сначала составляется функционал, то есть некая функция с некими параметрами, которая выдает на гора 1 значение Далее уже можно применить любой алгоритм минимизации функционала (а их туча)
То есть с точки зрения алгоритмирования, интерес представляет только составление самого функционала.
Шаги вычисления функционала я бы видел такие:
Задаемся кубом, вычисляем его объем - обозначим его как V Берем каждую из точек и определяем находится точка внутри куба или нет Если точка внутри куба определяем излишний объем dv=0 Если точка вне куба излишний объем dv определяем как 2*V (как вариант - можно придумать что-то более интересное и непрерывное) Суммируем все dv и прибавляем к V
В итоге получим 2n-мерный функционал (координаты 1-го из ребер куба однозначно характеризуют его положение в пространстве), который просто надо минимизировать - то есть понять при каком положении куба полученный объем будет минимален.
Теперь дело за малым - засовываем полученный функционал в более-менее любой алгоритм минимизации функционала (по сути это вообще чуть ли не библиотечные функции в вычметодах), задаем некое начальное значение положения куба и вперед.
