Упаковка кругов и эллипсов в ограниченную область

• Автор: Лисафина, Мария Сергеевна
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2014
• Место защиты: Казань
• Количество страниц: 125 с. : ил.

Оглавление
Введение

Г лава 1. Упаковка равных кругов

1.1. Постановка задачи

1.2. Математическая модель задачи

1.3. Алгоритм решения задач упаковок равных кругов в заданную область

1.4. Подбор параметров алгоритма

1.5. Численные результаты

1.6. Выводы

Глава 2. Упаковка равных эллипсов

в прямоугольную область
2.1. Постановка задачи
2.2. Случай эллипсов с большими осями параллельными друг другу
2.2.1. Условие касания эллипсов
2.2.2. Способы построения сетки
2.2.3. Упаковка горизонтальных эллипсов
2.2.4. Упаковка вертикальных эллипсов
2.3. Случай эллипсов с взаимно перпендикулярными большими осями
2.3.1. Условия касания эллипсов
2.3.2. Упаковка эллипсов
2.4. Алгоритм решения задач упаковок эллипсов в заданную область
2.5. Подбор параметров алгоритма
2.6. Численные результаты
2.7. Выводы
Глава 3. Упаковка кругов разных радиусов
3.1. Постановка задачи
3.2. Упаковка кругов радиусов г и гг
3.3. Алгоритм решения задач упаковок кругов радиусов г и гг
3.4. Численные результаты
3.5. Выводы
Глава 4. Программное обеспечение
4.1. Описание комплекса программ
4.2. Структура комплекса программ
4.3. Руководство пользователя
4.4. Выводы
Заключение
Список использованной литературы.

Введение
Проблема упаковок тел и фигур возникает в различных практических задачах. Первая математическая постановка задачи упаковок, видимо, принадлежит И. Кеплеру. Если частицы имеют форму шаров, то ясно, что как бы они ни располагались в пространстве, между ними неизбежно останутся зазоры, и вопрос состоит в том, чтобы объем зазоров свести к минимуму. Кеплер рассмотрел несколько различных вариантов расположения шаров и для каждого варианта вычислил коэффициент заполнения пространства. Один из первых вариантов расположения шаров, рассмотренных Кеплером, сейчас принято называть гранецентрированной кубической решеткой. Гипотеза Кеплера (1611г.) гласит:
«Никакая упаковка шаров равного размера в пространстве не имеет среднюю плотность больше, чем для гранецентрированной кубической упаковки и упаковок, равных ей по плотности».
Математически доказать гипотезу не удавалось на протяжении 400 лет. Сообщение о компьютерном доказательстве гипотезы Кеплера появилось в 1998 году в работе математика Томаса Хейлса. В 1998 году Хейлс объявил о найденном им строгом математическом решении задачи Кеплера, основанном на сочетании аналитической геометрии и сложных компьютерных вычислений. Журнал «Анналы математики» принял статью на экспертизу и создал комиссию из двадцати ведущих специалистов в этой области для составления отзыва о статье. Экспертная комиссия начала свою работу на конференции в Принстонском университете по выработке общей стратегии. Шли годы, референты постепенно выходили из состава комиссии, и наконец, в начале 2004 года было окончательно решено отказаться от усилий рецензировать статью. Редколлегия журнала решила опубликовать «теоретическую часть» работы, а «компьютерную часть» переадресовать в какой-нибудь другой журнал.
Проблема упаковки шаров в трех и многомерных пространствах находят важные приложения, например при кодировании и передачи информации. Инженер Гордон Лэнг разрабатывал модемы, и в своей работе пытался применять знания по упаковкам шаров в многомерных пространствах. Его задача заключалась в отправке сигнала по каналу с помехами, например, по телефонной линии. Для ее решения естественно выбирать набор тонов для сигналов. Но полученный при этом звук может отличаться от того, который был послан. Чтобы исключить это, он описал сигналы, сопоставив каждому свой номер. После этого стало проще определять, какой из отправленных сигналов ближе всего к полученному. В результате появилась возможность рассматривать сигналы как сферы, которые немного колеблются из-за

использования деления области на части имеем следующее. Для каждого значения радиусов
0.625, 0.5625, 0.5, 0.4375 и 0.3125 решение получено не более чем за 25 минут (см. таблицу 1.2). Для каждого из радиусов 0.375 и 0.275 решение получено за 4.5 часов.
а) б)
Рисунок 1.8. Упаковка кругов радиуса 0.1875 с условием прижимания их вниз: а) упаковка 111 кругов, б) упаковка 118 кругов.
При расчете упаковок в прямоугольник R удалось решить задачу (1.4) без привлечения эвристического алгоритма, когда число кругов не превосходит 18, а размерность задачи не больше, чем 2449. Как исключение получено решение без привлечения эвристического алгоритма для N=32, см. таблицу 1.3. Для упаковок в фигуру Rj без привлечения эвристического алгоритма получены решения, когда число кругов не превосходит 39, см таблицу 1.4.
Отметим еще раз, что во всех случаях, когда задача (1.4) решалась без привлечения эвристического алгоритма и с привлечением этого алгоритма, числа упаковываемых кругов оказывались одинаковыми. Для случаев, когда задача решалась только эвристическим алгоритмом, качество решения характеризует плотность упаковки. В частности, для упаковок в R плотность упаковки сравнивалась с плотность наилучших известных упаковок, см. комментарий после таблицы 1.3.
Приведенные численные результаты демонстрируют результативность предложенного подхода.