Разделете 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 такива кубчета.

Сега бих искал да върна вектор от вектори, съдържащ някои различни координати на тези малки кубчета. (или може би може да се представят кубовете като обекти, които се характеризират с вектор, сочещ към "левия" външен ъгъл?)

По принцип нямам представа дали нещо подобно дори е възможно с помощта на C++. Прилагането на това за фиксирано n не представлява проблем. Но бих искал да дам възможност на потребителя да има свободен избор на измерението.

История: Нещо подобно би било безценно при оптимизирането. Където човек би разделил пространството на по-малки и използва напр. генетични алгоритми за всяко от подпространствата и по-късно сравнете резултатите. По този начин може да се избегнат огромни първоначални популации и резултатите от търсенето да се подобрят драстично. Освен това просто съм любопитен дали sth. така става :)

Моето предложение: Да се ​​използват B+ дървета?


c++ optimization mathematical-optimization
person Andrey Lujankin    schedule 21.03.2013    source източник
comment
Звучи ми, че търсите n-измерно разширение на окдървета: en.wikipedia.org/ wiki/Octree   -  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), където делта*(y_i-1)-граници ‹= x_i ‹ делта*y_i-граници и делта=2*граници/m.

„Левият външен ъгъл“ или началото на S, което търсите, е просто точката, съответстваща на най-малкото x_i, т.е. точката (Делта*(y_1-1)-граници, ..., Делта*(y_n-1)- граници). Вместо да представяме различните S от тази точка, има много по-смислено (и ще бъде по-бързо в компютър) да ги представяме с целочислените координати по-горе.

person Douglas B. Staple    schedule 23.03.2013