Об одном приближении плотной упаковки

• Автор: Псиола, Виктор Вадимович
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2011
• Место защиты: Москва
• Количество страниц: 143 с. : ил.

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

Формулировка задачи и е актуальность.

Одномерный случай упаковки

Современное состояние задачи

Цели работы

Основное содержание работы.

1 Постановка задачи и описание алгоритмов

1.1 Формальная постановка задачи

1.2 Общая идея алгоритма .

1.3 Алгоритм комбинирования предметов.

1.4 Сведение 3мерной укладки к 2мерной
1.5 Выбор области укладки для 2мерного алгоритма.
1.6 Алгоритм 2мерной укладки
1.7 Модель принятия решения на основе функционалов качества
2 Оценки сложности и качественных характеристик
2.1 Рполнота задач укладки.
2.2 Доказательства полиномиальности алгоритма.
2.3 Качественные характеристики алгоритма.
2.4 Экспериментальные оценки алгоритма
3 Вопросы нахождения коэффициентов
3.1 Принципы подбора коэффициентов
3.2 Общая оптимизация генетическими алгоритмами
3.3 Динамический выбор с помощью нейронных сетей
3.4 Улучшение качества за счет ограниченного перебора
4 Модификации задачи и алгоритмов
4.1 Обозначения
4.2 Дополнительные ограничения
4.3 Особенности модификаций алгоритмов укладки
4.4 Модификации алгоритмов
5 Практическая реализация и внедрения
5.1 Особенности программной реализации.
5.2 Внедрения
5.3 Существующие альтернативные решения.
5.4 Смежные задачи
Заключение
Литература


В качестве стратегий выбора предмета для упаковки, слоя и места для его установки в этом слое используются комплексные эвристики, заданные взвешенной суммой различных характеристик объекта выбора. Возможность использования в качестве стратегии выбора не одной определенной эвристики, а нескольких в совокупности рассматривается, например, в работах Норенкова И. О. [, ]. Однако, там применяется вероятностный выбор той или иной стратегии, при этом количество стратегий для выбора очень не велико (четыре). В данной работе предпочтительность использования той или иной стратегией оценивается некоторой числовой характеристикой и выбор осуществляется на основе взвешенной суммы этих характеристик, то есть каждая стратегия вносит свой вклад в каждом случае выбора. При этом количество рассматриваемых стратегий существенно больше (в совокупности - ). Результаты данной работы были представлены на механико-математическом факультете МГУ им. М.В. МаТИС «Теория автоматов» (рук. В.Б. Модели и методы дискретной математики» (рук. О.М. Математическое моделирование сложных систем и процессов» (рук. A.C. Строгалов и проф. И.Н. Проблемы современных информационно-вычислительных систем» под руководством проф. В. А. Васенина в году. IX международной конференции «Интеллектуальные системы и компьютерные науки» г. Дискретная математика и ее приложения» г. Знания — Онтологии — Теории» (ЗОНТ-) в институте Математики им. С. Л. Соболева СО РАН г. Новосибирск в году. Основные положения и выводы диссертации были опубликованы в 6 статьях (см. ВАК Минобрнауки России. Первая глава работы посвящена непосредственно описанию алгоритмов решения 2- и 3-мерных задач об упаковке, построенного на базе комплексных эвристик. Алгоритм решения 3-мерной задачи включает в себя алгоритм 2-мерной и является основным для рассмотрения. Сначала вводятся обозначения и предлагается формальная постановка задачи. Далее идет описание эвристических функционалов принятия решений и подробное обоснование выбора слагаемых этих функционалов для данной задачи. Алгоритм построен таким образом, что процесс формирования решения задачи разбивается не несколько подзадач, которые решаются многократно но циклу на различных этапах алгоритма. В каждой из этих подзадач требуется осуществить выбор из нескольких вариантов. Если делать этот выбор методом полного перебора, то будет найдено наилучшее решение задачи в 2-мерном ортогональном случае, и в некотором ограниченном классе решений в 3-мерном случае. Однако, использование метода полного перебора, приводит к неприемлемо большому времени работы алгоритма (экспоненциальная зависимость от количества предметов). По этой причине каждый раз, когда требуется выбрать решение подзадачи из нескольких вариантов, вместо полного перебора в алгоритме для принятия решения используется эвристический функционал качества. Результатом применения этого функционала к каждому варианту решения подзадачи является действительное число и в качестве- окончательного решения выбирается вариант с наибольшим значением функционала. Каждый такой функционал имеет полиномиальную сложность вычисления, что в совокупности приводит к 'тму, что сложность работы всего алгоритма также является полиномиальной. Таким образом для решения каждой подзадачи используется вариант жадного алгоритма, где в качестве критерия выбирается эвристический функционал качества. Вторая глава содержит различные оценки сложности алгоритма и качества работы, а также результаты вычислительных экспериментов. Теоретические результаты сформулированы и доказаны в виде следующих теорем. Время работы предложенного алгоритма для решения 2-мерной ортогональной задачи об упаковке можно оценить сверху как 0(Лг4), где N — количество предметов в задаче. Время работы предложенного алгоритма для решения 3-мерной ортогональной задачи об упаковке можно оценить сверху как 0(Аг°), где N — количество предметов в задаче. Время работы предложенного алгоритма для решения 3-мерной ортогональной задачи об упаковке с предварительным комбинированием предметов в прямоугольные блоки можно оценить сверху как 0(Л^5 х /7г(Лг)), где N — количество предметов в задаче.