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