Комбинированные алгоритмы решения задачи одномерной упаковки (1095033)
Текст из файла
На правах рукописиНаумова Ольга АнатольевнаКОМБИНИРОВАННЫЕ АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧИОДНОМЕРНОЙ УПАКОВКИСпециальность 05.13.17 – теоретические основы информатикиАВТОРЕФЕРАТдиссертации на соискание ученой степеникандидата технических наукМосква — 2013Работа выполнена на кафедре «Прикладная математика и моделированиесистем» федерального государственного бюджетного образовательногоучреждения высшего профессионального образования «Московскийгосударственный университет печати (МГУПечати) имени Ивана Федорова».Научный руководитель:доктор технических наук, профессорУльянов Михаил ВасильевичОфициальные оппоненты:Сметанин Юрий Геннадиевич,докторфизико-математическихнаук,старший научный сотрудник, ведущийнаучный сотрудник Вычислительного центраРАН имени академика А.А.
ДородницынаКовшов Евгений Евгеньевич,доктор технических наук, профессор,заведующий кафедрой «Управление иинформатика в технических системах» МГТУ«СТАНКИН»Ведущая организация:Институт радиоэлектроники иинформационных технологийНижегородского государственноготехнического университета имениР.Е. АлексееваЗащита состоится «04» апреля 2013 г. в 1230 часов на заседаниидиссертационного совета Д 212.147.03 при Московском государственномуниверситете печати имени Ивана Федорова (127550, г. Москва, ул.Прянишникова, 2А).С диссертацией можно ознакомиться в библиотеке ФГБОУ ВПО«Московский государственный университет печати имени Ивана Федорова»Автореферат разослан «__» ___________ 2013 г.Ученый секретарьДиссертационного совета Д 212.147.03д.т.н., профессорВ.Н.
АгеевОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫАктуальность работы. Задача одномерной оптимальной по стоимостиупаковки, или задача о ранце, более полувека не оставляет равнодушнымиалгоритмистов всего мира. Безусловно, в первую очередь подобный интересобусловлен многообразием практического приложения задачи. Помимовопросов упаковки в явном виде (оптимальная загрузка судов, вагонов)задача одномерной упаковки применима к целому ряду финансовоэкономических задач. Например, планирование инвестиций с максимальнойвыгодой.
В то же время к задаче о ранце успешно сводится ряд задачлогистики. Возросла актуальность применения и в технологическихпроцессах — в настоящий момент поиск оптимальной упаковки являетсяосновой алгоритмов распределения дискового пространства и размещенияэлементов на микросхемах.Специфика исследуемой задачи такова, что все алгоритмы ее решенияделятся на два множества — эвристические быстрые алгоритмы и точныеалгоритмы. В настоящее время отсутствуют быстрые точные алгоритмырешения для больших размерностей. Поэтому до сих пор актуальнаразработка новых алгоритмов, отвечающих жестким требованиям как поточности, так и по временной эффективности.Что касается комбинированных алгоритмов решения исследуемойзадачи, то на данный момент этот подход, пожалуй, является наиболееперспективным способом разработки эффективных алгоритмов, так каксочетает достоинства и учитывает недостатки разработанных ранееалгоритмов.Помимо практического интереса, высока теоретическая значимостьпоиска быстрых алгоритмов точного решения задачи упаковки.
Это связано свопросом о совпадении или вложении классов P и NP -сложности задач.Степень разработанности проблемы. Фундаментальный вклад висследование и развитие решений задачи о рюкзаке внесли зарубежные и3отечественные ученые, среди которых Р. Беллман, Д. Б. Данциг, П. Колесар,Бабат Л.Г., Р.С. Барр, Д.Т. Росс, Корбут А.А., Курейчик В.М, Мухачева Э.А.,Норенков И.П., Валеева А.Ф., Сигал И.Х., П. Тот, С. Мартелло, Д. Писингер,Р. Андоров и др.Большинствоизвестныхработпосвященорешениюбинарнойупаковки. Стремительный рост производительности вычислительных средствиразработкановыхметодоврешенийпозволилитакжедобитьсязначительных успехов и для других постановок задачи о ранце.
В частности,благодаря развитию теории нейронных сетей и параллельных вычисленийсегодня активно исследуется многокритериальная упаковка.В целом, при решении задачи упаковки, с алгоритмической точкизрения, актуальна, как разработка новых алгоритмов, так и повышениеэффективности известных алгоритмов. Касательно методов решения — упорделается на приближенные алгоритмы: эвристические, генетические и ихразличные комбинации, в том числе и с точными алгоритмами.Объектом исследования диссертационной работы являются точныеалгоритмырешениязадачиодномернойнеограниченнойупаковки,реализующие принцип динамического программирования.Областьсоответствииисследования.сп.14Диссертационная«Разработкаработатеоретическихвыполненаосноввсозданияпрограммных систем для новых информационных технологий» паспортаспециальности05.13.17—«Теоретическиеосновыинформатики»(технические науки).Целью работы является разработка комбинированного алгоритматочного решения задачи одномерной оптимальной по стоимости упаковки иего сравнительный анализ с исходными схемами.Методы исследования.
В ходе диссертационного исследования былиспользован аппарат теории сложности вычислений, теории ресурснойэффективностикомпьютерныхалгоритмовэксперимента.4итеориипланированияНаучная новизна диссертационной работы заключается в следующихположениях:1. В теорию разработки эффективных алгоритмов введено новоепонятие «алгоритмическая система».2. Предложены оригинальные классификации алгоритмическихсистемиметодовпостроенияалгоритмическихсистем,ориентированные на повышение ресурсной эффективностиалгоритмического обеспечения.3. Разработан новый волновой алгоритм точного решения задачиодномерной оптимальной по стоимости упаковки, отличающийсяот известных лучшими ресурсными характеристиками.4. Проведен теоретический анализ волнового алгоритма, полученоаналитическое выражение функции трудоемкости в среднем, чтопозволяет выполнять адекватное прогнозирование временнойэффективности на реальных диапазонах длин входов.Теоретическая значимость.
Предложенные классификации позволяютне только систематизировать имеющиеся ныне решения, использующиесовместное применение нескольких алгоритмов, но и разрабатывать новыекомбинированные алгоритмические решения и комбинированные алгоритмы.Показано, что разработанный новый волновой алгоритм точного решениязадачи одномерной оптимальной по стоимости упаковки имеет лучшие посравнению с аналогами ресурсные характеристики.Практическая значимость диссертационной работы определяетсяследующими положениями:1. Предложенные классификации являются удобным инструментомвыбора и разработки алгоритмических систем.2.
Разработанный с использованием предложенных классификацийкомбинированныйалгоритмобладаетлучшимиресурснымихарактеристиками по сравнению с базовыми алгоритмами, а егопрограммная реализация — лучшими временными характеристики.5Основные положения, выносимые на защиту:1. Понятие «алгоритмическая система».2. Классификация алгоритмических систем.3. Классификация методов построения алгоритмических систем.4. Новый волновой алгоритм точного решения задачи одномернойоптимальной по стоимости упаковки.Достоверность и обоснованность научных положений и выводовобеспечивается корректным использованием базовых методов исследованияиматематическогоаппарата.Достоверностьрезультатовработыподтверждается сравнительным анализом существующих подходов крешению поставленной задачи, а также результатами экспериментальныхисследований.Реализациярезультатовработы.Временнаяэффективностьпредложенного волнового алгоритма в среднем вдвое выше, чем у базовыхалгоритмов.
Подобное улучшение ресурсных характеристик позволилоиспользовать волновой алгоритм в системе реального времени. С помощьюволнового алгоритма реализуется одна из функций программного модуля«Ведение оперативной базы данных активных планов полетов в комплексесредствавтоматизации»(ВОБДАПП)всоставекомплексасредствавтоматизации управления воздушным движением в режиме реальноговремени.НаразработанныймодульвФедеральнойслужбепоинтеллектуальной собственности получено Свидетельство о государственнойрегистрации программы для ЭВМ № 2012615176 от 08.06.2012.Апробация работы. Основные научные и практические результатыработы докладывались и обсуждались на следующих конференциях исеминарах:— международная научно-техническая конференция «Информационныетехнологии и системы», НГТУ, Нижний Новгород (ИСТ-2008, ИСТ-2009,ИСТ-2010, ИСТ-2011).6— II и III Всероссийская студенческая научно-техническая конференция«Прикладная информатика и математическое моделирование», МГУП,Москва, 2008, 2009.— 52-я и 54-я Всероссийская научная конференция «Современные проблемыфундаментальных и прикладных наук», МФТИ, Москва, 2009, 2011.— XI Международная конференция по математическому моделированию иинформационным технологиям «YM-2010», ИВТ СО РАН, Новосибирск,2010.— научная школа-семинар «Задачи системного анализа, управления иобработки информации», МГУП, Москва, 2009.Публикации.Основноесодержаниедиссертационнойработыизложено в 13 публикациях, в том числе — в 3 статьях, опубликованных вжурналах Перечня ВАК.
Получено Свидетельство о государственнойрегистрации программы для ЭВМ.Структура и объем диссертации. Диссертация состоит из введения, 4глав, заключения, списка литературы и двух приложений. Общий объемработы — 134 страницы. Список литературы включает 107 источников.ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫВведениесодержитобоснованиеактуальности,научнойипрактической значимости диссертационной работы.В первой главе рассматривается математическая постановка задачиодномерной оптимальной по стоимости упаковки, что позволяет выявитьособенности ее решения.
Приводится исторический обзор известных кнастоящему моменту решений. В виду многообразия известных алгоритмоввыделяются предпосылки к их совместному использованию для повышениявременной эффективности решений задачи упаковки.7Во второй главе вводится понятие алгоритмической системы какосновополагающее при разработке новых решений методом эффективногосочетания алгоритмов из пакета имеющихся для той или иной задачи.Под алгоритмической системой предлагается понимать объединениеразличных алгоритмов решения рассматриваемой задачи. При этомиспользование в полученной системе алгоритмов, наиболее рациональныхдля соответствующих условий применения, гарантирует, в общем случае,лучшие ресурсные характеристики всей системы в целом по сравнению сотдельными входящими в нее алгоритмами.Разработка алгоритмических систем является сегодня одним изперспективныхнаправленийсовершенствованияалгоритмическойподдержки программного обеспечения.Предпосылкой к появлению понятия алгоритмической системы сталтот факт, что в настоящее время для большинства задач компьютернойматематики известен целый ряд различных алгоритмов, доставляющихправильное решение этих задач, и обладающих при этом различнымиресурсными характеристиками, зависящими от особенностей входныхданных.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
