2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Моделирование упаковок сферами областей
Сообщение27.03.2014, 04:14 
Известна оптимальность упаковок равными кругами (сферами)
Изображение
Предмет вопроса - алгоритмы расчета оптимального заполнения большой выпуклой области, прежде всего –многоугольника треугольной решеткой L2 (шаг $  h=2$ ). Невыясненным является характер оптимального наложения решетки на область. В случае круга разные виды наложения решетки характеризуются 2 параметрами $h_x,h_y $ см.(рис.)
Изображение
формула расчета заполнения плоской задачи имеет вид:
$ k=\sum\sum{b_{ij}}$
где $ b_{ij}=1 $ при $ (x,y)\in G $ и $ b_{ij}=0$ при $ (x,y)\notin G $
где координаты задаются формулами $ x=(i+j)\sqrt{3} $, $ y=-i+j $
В случае анизотропной области (многоугольная) добавляется 3-й параметр - угол поворота области относительно решетки $ \alpha  $
. Эффективный алгоритм должен выдавать кроме наибольшего числа заполнения еще и значения параметров смещения и углов поворота,
Алгоритм имеет блоки:
1)варьирование углов поворота с некоторым шагом
2) сканирование области смещений $ 0 \le h_x \le \sqrt{3} , $ 0 \le h_y \le 1
(варьирование $h_x,h_y $ )
3)при каждом значении тройки $\alpha, h_x,h_y $ расчет числа элементов заполнения $\k(\alpha, h_x,h_y) $
4)нахождение максимального числа элементов с запоминанием его параметров $\alpha, h_x,h_y $
Вопросы:
1)Слабым местом алгоритма даже в плоском случае является большое количество (3) варьируемых параметров. Неизбежно встает вопрос об шаге варьирования
2)Мною были проделаны подобные расчеты для области-круга.(2 параметра $h_x,h_y $ ) Они показали что сама процедура сканирования области смещений усложняя трудоемкость приводит к очень незначительному улучшению заполнения. Например, при
$ R=8.9$ получено $ k_{\max}(0.89,0)=58 $
в то время как при отсутствии смещений $ k(0,0)=55 $
3) интереснее для практики было бы не только получение точечных значений параметров $\alpha, h_x,h_y $ ,но и их интервальных значений (допусков) в пределах которых оптимум сохраняется. Но это еще больше усложнит и замедлит описанный алгоритм.
4) Для пространственной L3-решетки формально число варьируемых параметров увеличивается с 3 до 5 (3 смещения и 2 угла поворота), что еще усложнит алгоритм.
5)Данный алгоритм относится к классу алгоритмов "грубой силы". Мне неизвестны и, видимо трудно рассчитывать на какие-то дополнительные математические рекомендации упрощающие или изменяющие его. В частности, ранее предполагал для круга$h_x=h_y=h$ т.е 1 параметр вместо двух, что видимо неприемлемо для анизотропной области

 
 
 
 Re: Моделирование упаковок сферами областей
Сообщение18.03.2015, 20:13 
Е. Федер "Фракталы" глава 3. Возможно немного упростит задачу.

 
 
 [ Сообщений: 2 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group