Алгоритмы построения оптимальных упаковок в эллипсы
Автор: Ушаков Владимимир Николаевич, Лебедев Павел Дмитриевич, Лавров Никита Георгиевич
Рубрика: Математическое моделирование
Статья в выпуске: 3 т.10, 2017 года.
Бесплатный доступ
В задачах теории управления часто требуется проводить аппроксимацию множеств наборами из конгруэнтных элементов. Одним из вариантов такой аппроксимации служит упаковка в фигуры на плоскости набора кругов равного радиуса. В статье рассмотрены два варианта задачи о построении оптимальной упаковки в эллипсы различной формы: в первом фиксировано число элементов и требуется максимизировать их радиус, во втором фиксирован радиус кругов и требуется максимизировать их число. В первом варианте применяются итерационные методы, имитирующие отталкивание центров кругов друг от друга и от границы множества. В них используются конструкции чебышевского центра, ортогональных проекций и отталкивания точек. Во втором - рассматриваются упаковки с гексагональной решеткой, которые близки к оптимальным. Реализован программный комплекс построения упаковок для эллипсов с различным соотношением осей.
Упаковка, хаусдорфово отклонение, максимизация, чебышевский центр, производная по направлению
Короткий адрес: https://sciup.org/147159444
IDR: 147159444 | DOI: 10.14529/mmp170306
Список литературы Алгоритмы построения оптимальных упаковок в эллипсы
- Красовский, Н.Н. Позиционные дифференциальные игры/Н.Н. Красовский, А.И. Субботин. -М.: Наука, 1974. -456 с.
- Ушаков, В.Н. Конструирование решений в задаче о сближении стационарной управляемой системы/В.Н. Ушаков, Н.Г. Лавров, А.В. Ушаков//Труды Института математики и механики УрО РАН. -2014. -Т. 20, № 4. -С. 277-286.
- Kurzhanski, A.B. Ellipsoidal Calculus for Estimation and Control/A.B. Kurzhanski, I. Valyi. -Basel: Birkhäuser, 1997.
- Слоэн, Дж. Упаковка шаров/Дж. Слоэн//Scientific American. -1984. -№ 3. -С. 72-82.
- Ушаков, В.Н. Оптимизация хаусдорфова расстояния между множествами в евклидовом пространстве/В.Н. Ушаков, А.С. Лахтин, П.Д. Лебедев//Труды Института математики и механики УрО РАН. -2014. -Т. 20, № 3. -C. 291-308.
- Казаков, А.Л. Алгоритмы построения оптимальных упаковок для компактных множеств на плоскости/А.Л. Казаков, П.Д. Лебедев//Вычислительные методы и программирование. -2015. -Т. 16, № 3. -С. 307-317.
- Демьянов, В.Ф. Недифференцируемая оптимизация/В.Ф. Демьянов, Л.В. Васильев. -М.: Наука, 1981. -384 с.
- Демьянов, В.Ф. Основы негладкого анализа и квазидифференциальное исчисление/В.Ф. Демьянов, А.М. Рубинов. -М.: Наука, 1990. -432 с.
- Сухарев, А.Г. Курс методов оптимизации/А.Г. Сухарев, А.В. Тимохов, В.В. Федоров. -М.: Наука, 1986. -326 с.
- Лейхтвейс К. Выпуклые множества/К. Лейхтвейс. -М.: Наука, 1985. -335 с.
- Szabó, P.G. Packing up to 200 equal circles in a square/P.G. Szabó, E. Specht//Models and Algorithms for Global Optimization. -2007. -P. 141-156.
- Гаркави, А.Л. О чебышевском центре и выпуклой оболочке множества/А.Л. Гаркави//Успехи математических наук. -1964. -Т. 19, № 6. -С. 139-145.
- Белобров, П.К. К вопросу о чебышевском центре множества/П.К. Белобров//Известия высших учебных заведений. Математика. -1964. -№ 1. -C. 3-9.
- Тот, Л.Ф. Расположения на плоскости, на сфере и в пространстве/Л.Ф. Тот. -М.: Государственное издательство физико-математической литературы, 1958. -365 c.
- Graham, R.L. Dense Packings of Congruent Circles in a Circle/R.L. Graham, B.D. Lubachevsky, K.J. Nurmela, P.R.J. Östergård//Discrete Mathematics. -1998. -№ 181. -P. 139-154.
- Lubachevsky, B.D. Curved Hexagonal Packings of Equal Disks in a Circle/B.D. Lubachevsky, R.L. Graham//Discrete & Computational Geometry. -1997. -V. 18, № 2. -P. 179-194.
- Markót, M.Cs. A New Verified Optimization Technique for the "Packing Circles in a Unit Square" Problems/M.Cs. Markót, T.A. Csendes//SIAM Journal on Optimization. -2005. -V. 16, № 1. -P. 193-219.
- Goldberg, M. Packing of 14, 16, 17 and 20 Circles in a Circle/M. Goldberg//Mathematics Magazine. -1971. -V. 44, № 3. -P. 134-139.
- Чен, К. MATLAB в математических исследованиях/К. Чен, П. Джиблин, А. Ирвинг. -М.: Мир, 2001.
- Erich's Packing Center. -URL: www2.stetson.edu (дата обращения: 10.05.2017)
