Разделите n-мерное квадратное пространство на кубы

прямо сейчас я застрял в решении следующей «полу»-математической задачи.

Я хотел бы разделить n-мерное ограниченное пространство (точнее, гиперкуб)

D={(x_1, ...,x_n), x_i \in IR and -limits<=x_i<=limits \forall i<=n} На более мелкие кубики.

Это означает, что я хотел бы указать n,limits,m, где m было бы количеством разделов на сторону куба - 2*limits/m было бы длиной маленьких кубов, и я получил бы m^n таких кубов.

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

По сути, я понятия не имею, возможно ли что-то подобное даже с использованием С++. Реализация этого для фиксированного n не представляет проблемы. Но я хотел бы, чтобы пользователь мог свободно выбирать размер.

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

Мое предложение: использовать деревья B+?


c++ optimization mathematical-optimization
person Andrey Lujankin    schedule 21.03.2013    source источник
comment
Мне кажется, что вы ищете n-мерное расширение октодеревьев: en.wikipedia.org/ вики/Октри   -  person Kristian Duske    schedule 21.03.2013
comment
Делает что-л. такие существуют?   -  person Andrey Lujankin    schedule 21.03.2013
comment
Я уверен, что это так, но я не знаю, как это будет называться. Должно быть относительно просто расширить октодерево до N измерений. Вместо 8 детей на узел вам понадобится n^2. Операции вставки, поиска и удаления в основном очень похожи.   -  person Kristian Duske    schedule 21.03.2013
comment
Такая дискретизация пространства определенно не бесценна для оптимизации; на самом деле это приводит к экспоненциальному увеличению набора переменных. Я думаю, что большая часть оптимизации посвящена методам, позволяющим избежать этого.   -  person Andrew Mao    schedule 23.03.2013
comment
конечно - но в случае, когда вам нужно разместить сетку на вашем n-dminsional пространстве - это было бы очень полезно. Я согласен с вами, что это не самый эффективный способ, но в некоторых случаях он может быть самым точным. Поэтому, когда точность важнее времени выполнения. Но все же ваш аргумент вполне действителен :D   -  person Andrey Lujankin    schedule 23.03.2013

Ответы (1)


arrow_upward
2
arrow_downward

Пусть m — количество разделов на измерение, т. е. на ребро, гиперкуба D.

Тогда, как вы говорите, существует m^n различных подпространств S пространства D. Пусть подпространства S однозначно представлены целочисленными координатами S=[y_1,y_2,...,y_n], где y_i — целые числа в диапазоне 1, ..., m. Тогда в декартовых координатах S=(x_1,x_2,...,x_n), где Delta*(y_i-1)-limits ‹= x_i ‹ Delta*y_i-limits, а Delta=2*limits/m.

«Левый внешний угол» или начало координат S, которое вы искали, — это просто точка, соответствующая наименьшему x_i, то есть точка (Delta*(y_1-1)-limits, ..., Delta*(y_n-1)- пределы). Вместо того, чтобы представлять разные S в этой точке, гораздо логичнее (и быстрее на компьютере) представлять их, используя целочисленные координаты, указанные выше.

person Douglas B. Staple    schedule 23.03.2013