Методы анализа и разработки параметризированных алгоритмов Быкова, Валентина Владимировна

Работа не может быть доставлена, но Вы можете
отправить сообщение автору

Быкова, Валентина Владимировна. Методы анализа и разработки параметризированных алгоритмов : диссертация ... доктора физико-математических наук : 05.13.17 / Быкова Валентина Владимировна; [Место защиты: Красноярский государственный университет].- Красноярск, 2012.- 257 с.: ил. РГБ ОД, 71 13-1/257

Введение к работе

Актуальность темы. Понятие алгоритма является не только одним из важнейших понятий математики, но одним из основных понятий современной науки. Чтобы ориентироваться в сегодняшнем мире алгоритмов, необходимо уметь сравнивать различные алгоритмы решения одних и тех же задач, причем не только по качеству выдаваемого решения, но и по характеристикам самих алгоритмов. Точный язык для обсуждения этих вопросов дает теория сложности вычислений. Ее результаты составляют теоретическую основу современной информатики и программной инженерии. Алгоритм как звено триады «задача - алгоритм - программа», с одной стороны, предопределяет производительность реализующей его программы, а, с другой стороны, способствует глубокому проникновению в решаемую задачу и нахождению эффективных методов ее решения.

В теории сложности вычислений выделяют два специальных раздела. Это собственно сложность вычислений — раздел, включающий в себя анализ сложности задач (нахождение нижних оценок времени решение задач), классическую дихотомию задач (классы сложности Р, NP), теорию NP-полноты. Анализ алгоритмов — раздел, направленный на изучение сложности алгоритмов с различных точек зрения, но главным образом с точки зрения ресурсов, необходимых для их выполнения. Анализ алгоритмов предполагает поиск критериев сравнения алгоритмов, нахождение асимптотических оценок сложности, классификацию алгоритмов по сложности и выработку рекомендаций по построению эффективных алгоритмов. При этом под сложностью алгоритма традиционно понимают время осуществления вычислительного процесса, порождаемого алгоритмом, то есть ресурсную или вычислительную сложность алгоритма. Типичный уровень анализа — установление класса сложности и асимптотических оценок функции временной сложности исследуемого алгоритма с ориентацией на худший случай. Такие функции формально задают время выполнения алгоритма на равнодоступной адресной машине (РАМ) в зависимости от длины исходных данных (длины входа алгоритма). Полученные в результате анализа асимптотические оценки сложности алгоритма служат верхними оценками сложности решаемой задачи и согласно ГОСТ 28195-89 определяют производительность программы, реализующей этот алгоритм.

Необходимость исследований в области анализа и разработки эффективных (с точки зрения потребляемых ресурсов) алгоритмов обусловлена, прежде всего, тенденциями развития современных информационных технологий и особенностями подлежащих решению вычислительных задач. Задачи, возникающие в системах принятия решений, распознавания образов, компьютерной безопасности, искусственного интеллекта и биоинженерии, при создании и эксплуатации крупномасштабных информационных и

телекоммуникационных систем, характеризуются, как правило, большой размерностью и высокой вычислительной сложностью. Сложность вычислений порой настолько высока, что с ней не могут справиться мощности современных компьютеров. Актуальность разработки теоретических основ создания программных систем для решения подобных задач отражена в приоритетных направлениях развития науки, технологий и техники (приказ президента РФ от 7 июля 2011 г. № 899).

Широкий класс задач, возникающих в рамках современных информационных технологий, составляют задачи выбора. Отличительная особенность этих задач — поиск решения в конечной области. В них требуется найти одно из допустимых решений (в задачах удовлетворения ограничений) или оптимальное решение (в задачах комбинаторной оптимизации). Для NP-трудных задач выбора характерен стремительный рост числа допустимых решений с увеличением размерности задачи, что делает поиск решения полным перебором, алгоритмически неэффективным. Многие задачи выбора могут быть математически сформулированы как задачи на графах и гиперграфах. Именно NP-трудные задачи выбора, допускающие графовое и гиперграфовое представление, составляют класс рассматриваемых в диссертации задач.

Теория сложности вычислений сформировала фактический стандарт эффективной вычислимости задачи. Задачу считают эффективно (полиномиально) вычислимой, если существует алгоритм, время выполнения которого ограничено полиномом от длины входа. В то же время имеется большое число NP-трудных задач, для которых пока не получено эффективных алгоритмов. Справедливость гипотезы Р ф NP означает, что таких алгоритмов вообще не существует. Выполнение этого неравенства предполагается в рамках всей диссертационной работы. В развитие классических основ теории сложности вычислений и анализа алгоритмов значительный вклад внесли А.Н. Колмогоров, А.А. Марков, Н.М. Нагорный, А.И. Мальцев, Г.С. Цейтин, Ю.И. Янов, Л.А. Левин, Ю.Л. Ершов, А.А. Разборов, А.Л. Семенов, В.А. Успенский, Б.А. Трахтенброт, Э.Л. Пост, A.M. Тьюринг, А. Черч, Р. Карп, С. Кук, М. Гэри, Д. Джонсон, Д. Кнут, Р. Тарьян, X. Пападимитриу, К. Стайглиц и многие другие российские и зарубежные ученые.

На сегодняшний день основными подходами к решению NP-трудных задач выбора являются: сужение задачи с целью выделения легких частных случаев, сокращение перебора за счет «разумной» организации стратегии поиска решения, нахождение приближенных решений с гарантированной ошибкой, применение эвристик и метаэвристик, параметризация задачи. Параметризированный подход — сравнительно новый подход «борьбы» с трудноразрешимостью задач выбора. Основная идея параметризированно-го подхода состоит в том, чтобы с помощью некоторого числового пара-

метра структурировать и измерить конечное пространство поиска . Роль параметра — выделить основной источник неполиномиальной сложности NP-трудной задачи и показать, «комбинаторный взрыв» какой величины можно ожидать при ее решении на тех или иных исходных данных. Возникающие при этом алгоритмы называются параметризированными. Па-раметризированный алгоритм — основной объект исследования диссертационной работы.

Параметризированный алгоритм — это алгоритм, осуществляющий поиск точного решения задачи путем просмотра всего или некоторой части конечного отструктурированного пространства поиска. Время его выполнения представляется функцией, зависящей от двух переменных: п — длины входа алгоритма и к — числового параметра задачи. Необходимо отметить, что для одной и той же задачи возможны разные параметризации относительно различных параметров. Иногда возникают параметризации с несколькими параметрами. Наибольший интерес представляют параметризации NP-трудных задач, приводящие к алгоритмам, время выполнения которых полиномиально зависит от длины входа и неполиномиальным образом — от значения параметра. Если такой параметр для рассматриваемой задачи существует, то задача называется FPT-разрешимой (Fixed-Parameter Tractable) относительно этого параметра, а соответствующий алгоритм — FPT-алгоритмом. С помощью FPT-алгоритмов можно решать задачи выбора большой размерности при малых фиксированных значениях параметра.

Параметризированный подход к оценке сложности вычислений был сформулирован в конце прошлого столетия Р. Дауни и М. Феллови². Конечно, алгоритмы с функциями сложности от двух и более переменных встречались всегда. Параметризированный подход к сложности вычислений использован еще в теории графовых миноров Н. Робертсона и П. Сеймура³. Однако только Р. Дауни и М. Феллови четко определили роль параметра и ввели понятие FPT-разрешимости задачи. В российской научной среде параметризированный подход также известен и востребован. Его идеи и воплощения можно найти в публикациях российских ученых, работающих в области дискретной оптимизации и целочисленного программирования: Ю.И. Журавлева, И.В. Сергиенко, В.А. Емеличева, М.М. Ковалева, М.К. Кравцова, В.К. Леонтьева, В.Л. Вереснева, Э.Х. Гимати, В.Г. Ви-зинга, СВ. Севастьянова, А.А. Колоколова, И.В. Романовского, Ю.А. Ко-четова, И.Х. Сигала, А.В. Пяткина, В.В. Серваха, В.П. Ильева, В.Е. Алек-

^lum J., Grohe М. Parameterized complexity theory. - Berlin, Heidelberg: Springer-Verlag, 2006.

²Downey R., Fellows M. Parameterized complexity. - New York, Springer-Verlag, 1999.

³Robertson N., Seymour P.D. Graph minors. II. Algorithmic aspects of treewidth // J. Algorithms. - 1986. - V. 7. - P. 309-322.

сеева, В.А. Бондаренко, О.А. Щербины и многих других.

В настоящее время параметризированный подход к оценке сложности вычислений развивается в нескольких направлениях: определение иерархии классов сложности параметризированных задач, установление условий FPT-разрешимости, выявление взаимосвязи между параметризированной сложностью и полностью полиномиальными схемами приближений, создание теоретических основ параметризированной алгоритмики (методов анализа и разработки параметризированных алгоритмов).

Существующие на сегодняшний день открытые проблемы параметризированной алгоритмики составляют предмет исследования диссертации. Укажем наиболее существенные из них, решению которых в работе уделено основное внимание.

В многочисленных работах по параметризированному подходу к анализу сложности вычислений традиционно применяются методы классической (одномерной) систематизации. Между тем классическая одномерность ограничивает глубину анализа параметризированных алгоритмов с функциями сложности двух и более переменных. Для исследования таких функций сложности нужны специальные инструменты анализа.
Для одномерного случая (когда функция сложности алгоритма зависит только от длины входа) также есть нерешенные проблемы. Суть одной из них состоит в отсутствии простых и удобных для практики математических средств распознавания современных сложност-ных классов алгоритмов. Сегодняшняя алгоритмическая практика уже давно вышла за рамки классической дихотомии (с классами полиномиальных и экспоненциальных алгоритмов) и оперирует пятью сложностными классами алгоритмов. Выделены субполиномиальные (быстрые) алгоритмы из полиномиального класса, субэкспоненциальные и гиперэкспоненциальные алгоритмы из экспоненциального класса. Использование непосредственного асимптотического оценивания в этих условиях, как правило, приводит к громоздким вычислениям. Известны попытки введения классификационного признака, позволяющего распознавать современные сложностные классы алгоритмов. Так, В.А. Головешкин и М.В. Ульянов предложили в качестве такого признака употреблять угловую меру асимптотического роста функций сложности⁴. Однако применение этой меры на практике зачастую ограничено трудностями вычислительного характера (она не просто находится для некоторых логарифмически-экспоненциальных

⁴Головешкин В.А., Ульянов М.В. Метод классификации вычислительных алгоритмов по сложности на основе угловой меры асимптотического роста функций // Вычислительные технологии. - 2006. - Т. 11. - №1. - С. 52-62.

функций) и сложностью ее обобщения на функции многих переменных. Другая проблема связана с анализом рекурсивных алгоритмов. В настоящее время основным инструментом анализа рекурсивных алгоритмов является метод рекуррентных соотношений. Идея этого метода состоит в построении и решении рекуррентного соотношения, которому удовлетворяет функция сложности анализируемого алгоритма. Как известно, общих правил решения рекуррентных соотношений пока не найдено. Поэтому всякий математический результат, дающий какой-либо общий подход к решению данной проблемы, интересен как теоретически, так и практически. К подобным результатам относятся методы решения линейных рекуррентных соотношений с постоянными коэффициентами, а также оценки Дж. Бентли, Д. Ха-кена, Дж. Сакса, полученные для времени выполнения рекурсивного алгоритма, организованного по принципу «разделяй и властвуй»⁵. Актуальны подобные оценки и для других широко употребляемых принципов организации рекурсии. Например, для принципа «уменьшай и властвуй», характерного для метода динамического программирования. В этом случае на каждом шаге рекурсии размерность задачи понижается на некоторую константу.

3. Параметризированный подход позволяет исследовать различные параметризации одной и той же задачи, каждая из которых может приводить или не приводить к FPT-алгоритмам. В настоящее время уже известны некоторые специальные методы конструирования FPT-алгоритмов. Наиболее универсальный метод разработки FPT-алгоритмов для задач выбора, представимых графами и гиперграфами, — метод динамического программирования по дереву декомпозиции, автором которого считается Г. Бодлаендер⁶. Пространство поиска здесь структурируется на основе специальной декомпозиции входного графа или гиперграфа и измеряется через числовой параметр, отражающий ширину этой декомпозиции. При всей теоретической привлекательности данного метода практическое его применение ограничивается двумя серьезными проблемами. Первая проблема связана с высокими потребностями в памяти получаемых FPT-алгоритмов, а вторая — с решением NP-трудной задачи — с вычислением древовидной ширины графа.

Целью диссертации является разработка теоретических основ и практических решений проблем анализа параметиризированных алгорит-

⁵Bentley J.L., Haken D., Saxe J.В. A general method for solving divide-and-conquer recurrences II SIGACT News. - 1980. №12 (3). - P. 36-44.

⁶Bodlaender H.L. Treewidth: Algorithmic techniques and results // Proc. 22nd MFCS, Springer-Verlag LNCS 1295. - 1997. - P. 19-36.

мов, а также проблем создания FPT-алгоритмов для решения NP-трудных задач выбора на графах и гиперграфах ограниченной древовидной ширины.

Задачи исследования:

Изучение вопросов систематизации алгоритмов по вычислительной сложности и параметризированного подхода к оценке сложности вычислений. Разработка удобных для широкой алгоритмической практики математических инструментов анализа параметризированных алгоритмов.
Исследование проблемы анализа рекурсивных процессов и ее решение для класса рекурсивных алгоритмов, организованных по принципу «уменьшай и властвуй».
Исследование проблем создания FPT-алгоритмов и практической применимости метода динамического программирования по дереву декомпозиции. Разработка методов решения этих проблем для NP-трудных задач выбора, представимых графами и гиперграфами.

Используемые в диссертации методы исследования опираются на аппарат математического анализа, теории графов, дискретной оптимизации и теории реляционных баз данных.

Научная новизна и выносимые на защиту положения. Все результаты диссертации являются новыми. Укажем наиболее существенные.

1. Разработаны математические инструменты анализа вычислительной
сложности параметризированных алгоритмов:

метод распознавания классов субполиномиальных, полиномиальных, субэкспоненциальных, экспоненциальных и гиперэкспоненциальных алгоритмов, базирующийся на асимптотике поведения эластичности функций сложности (одной переменной);

метод двумерной классификации параметризированных алгоритмов на основе частных эластичностей.

Введены и изучены новые понятия: эластичность алгоритма; неэластичные, эластичные и суперэластичные алгоритмы.
Получены верхние и нижние оценки времени выполнения рекурсивных алгоритмов, построенных путем аддитивного уменьшения размерности задачи на некоторую константу.
Разработаны теоретические положения и алгоритмические решения проблем, возникающих при построении FPT-алгоритмов методом динамического программирования по дереву декомпозиции. В их число входят:

теоретические и алгоритмические аспекты применения бинарного сепараторного дерева в решении проблемы памяти;

два рекуррентных и полиномиальных по времени метода вычисления верхних и нижних оценок древовидной ширины графа и гиперграфа.

Достоверность и обоснованность результатов диссертации подтверждаются строгими математическими доказательствами и аргументациями.

Теоретическая ценность диссертации. Основные результаты работы имеют преимущественно теоретический характер.

Предложен и изучен простой и удобный для алгоритмической практики математический аппарат исследования вычислительной сложности параметризированных алгоритмов на основе эластичности, который не зависит от числа учитываемых параметров. Эластичность, являясь математически точно определяемой величиной, легко вычисляется для логарифмически-экспоненциальных функций, имеет нужную для анализа алгоритмов интерпретацию, позволяет сравнивать между собой алгоритмы и выявлять степень влияния параметра на время выполнения алгоритма.
Решена проблема анализа класса рекурсивных алгоритмов, организованных по принципу «уменьшай и властвуй».
Разработаны и математически обоснованы методы, способствующие развитию и практическому применению специального метода конструирования FPT-алгоритмов (метода динамического программирования по дереву декомпозиции).
Совокупность представленных в диссертации математических методов составляет теоретическую основу параметризированной алгорит-мики и позволяет исследовать и создавать FPT-алгоритмы для решения широкого спектра NP-трудных задач выбора, возникающих в рамках новых информационных технологий.

Практическая ценность диссертации. Основные предложенные в работе методы доведены до методик, рекомендаций, алгоритмов и программ, что подтверждается свидетельствами о регистрации программных разработок в фонде электронных ресурсов «Наука и образование» РАО. В широкой алгоритмической практике и программной инженерии могут быть использованы следующие результаты диссертации.

1. Методика сравнения алгоритмов по асимптотике поведения эластич-ностей функций сложности.

Методика установления степени воздействия параметра на сложность параметризированного алгоритма через коэффициент замещения одного аргумента функции другим аргументом. Такой анализ дает возможность исследовать вычислительные возможности параметризированного алгоритма на входах большой длины и регулировать эти возможности путем изменения значения параметра.
Верхние и нижние оценки времени выполнения рекурсивных алгоритмов, построенных путем аддитивного уменьшения размерности задачи на некоторую константу. Данные оценки могут служить рекомендациями к эффективной организации соответствующих рекурсивных вычислений.
Методы, алгоритмы и программы, касающиеся метода динамического программирования по дереву декомпозиции. Это математическое и программное обеспечение поможет решать задачи выбора большой размерности на графах и гиперграфах ограниченной древовидной ширины.

Использование результатов диссертации. Результаты диссертационной работы переданы и используются: в Институте вычислительного моделирования СО РАН (г. Красноярск) при выполнении проекта «Разработка интеллектуальных вычислительных комплексов для поддержки принятия решений при конструировании и эксплуатации сложных технических систем и объектов» в рамках Программы Президиума РАН, а также темы «Разработка и исследование методов компьютерного моделирования и обработки данных для информационно-управляющих систем поддержки принятия решений по повышению уровня пожарной безопасности зданий» в рамках междисциплинарного интеграционного проекта СО РАН; в филиале ОАО «РЖД» (г. Красноярск) для управления терминально-складской и транспортно-экспедиционной логистикой грузоперевозок; в ОАО «РУСАЛ-Ачинск» для разработки программ и мероприятий, направленных на совершенствование управления производством и повышение информационной безопасности компьютерных систем предприятия. Результаты диссертации применяются в учебном процессе Института математики Сибирского федерального университета (г. Красноярск) для подготовки бакалавров и магистров направления «Математика. Компьютерные науки», а также Института информатики и телекоммуникаций Сибирского государственного аэрокосмического университета им. академика М.Ф. Ре-шетнева (г. Красноярск) для подготовки бакалавров направления «Прикладная математика» и магистров направления «Теоретическая информатика». Имеются акты об использовании.

Апробация работы. Основные результаты исследования докладывались и обсуждались на следующих конференциях и семинарах междуна-

родного, всероссийского и региональных уровней: Всероссийских конференциях «Проблемы оптимизации и экономические приложения» (Омск, Россия, 1997, 2012); VI-VII Всероссийских конференциях по финансово-актуарной математике и смежным вопросам (Красноярск, Россия, 2007, 2008); V-VI Всесибирских конгрессах женщин-математиков (Красноярск, Россия, 2008, 2010); 9-11 Сибирских научных школах-семинарах с международным участием «Компьютерная безопасность и криптография» (Тюмень, Россия, 2010; Томск, Россия, 2011; Иркутск, Россия, 2012); XIV Международной конференции по эвентологической математике и смежным вопросам (Красноярск, Россия, 2010); XII Всероссийской научно-практической конференции «Проблемы информатизации региона» (Красноярск, Россия, 2011); IX-X Международных конференциях по финансово-актуарной математике и эвентоконвергенции технологий (Красноярск, Россия, 2010, 2011); The Third International Conference «Problems of cybernetics and informatics» (Baku, Azerbaijan, 2010); The Third IASTED International Multi-Conference on Automation, Control, and Information Technology, ACIT-CDA2010 (Novosibirsk, Russia, 2010); The Conference devoted to 20 anniversary of independence of the Republic Uzbekistan «Modern Mathematics Problems» (Karshi, Uzbekistan, 2011); The 14th Applied Stochastic Models and Data Analysis International Conference, ASMDA2011 (Rome, Italy, 2011).

Публикации. По материалам диссертации автором опубликовано 39 работ, включая монографию [1], 35 печатных работ в журналах и сборниках (из них 17 статей в ведущих рецензируемых журналах и журналах из перечня ВАК [2-18]), 3 свидетельства о государственной регистрации комплексов программ [37-39].

Личный вклад автора. Результаты диссертации получены соискателем самостоятельно. В соавторстве выполнены работы [23, 27, 28, 30, 32, 37-39], в которых вклады авторов равнозначны.

Структура и объем работы. Диссертация состоит из введения, шести глав, заключения, библиографического списка и трех приложений. Изложение иллюстрируется 41 рисунком и двумя таблицами. Библиографический список включает 222 наименования. Общее число страниц диссертации — 257, в том числе приложения — 25 страниц.

Во введении обосновывается актуальность темы исследования, формулируются цель и задачи диссертационной работы, отмечаются новизна, теоретическая и практическая ценность полученных результатов, кратко излагается содержание работы.

В первой главе даны основные понятия, обозначения и соглашения.

Приведены концептуальные основы анализа алгоритмов, на которых базируются результаты работы.

В диссертации под словом «задача» подразумевается массовая задача П. Там, где речь идет об индивидуальной задаче /, применяются словосочетания «экземпляр / задачи П», «I — вход алгоритма, решающего задачу П» и т.п. Следуя классическим традициям и позициям парамет-ризированной теории сложности вычислений, функция вычислительной сложности алгоритма поставлена в центр внимания исследования: вначале в главах 2 и 3 как функция t(n) одной переменной п, а затем в главах 4-6 как функция t{n, к) двух аргументов пик. Эта функция представляет время выполнения алгоритма (в худшем случае применительно к РАМ) в зависимости от длины входа п = \1\ и значения числового параметра к (если он учитывается). Сравнение алгоритмов осуществляется по порядку роста их функций сложности. При этом используются традиционные асимптотические обозначения:

t\{n) -< t2(n), или t\{n) = o\t2{n)\. Функция t\{n) меньше функции г(^п) ^п0 порядку роста;

t2("0 =^ t\{п), или t\{n) = Cl\p2(n)]. Функция t\{n) не меньше функции t2(n) по порядку роста;

t\{n) =4 ^2(п), или t\{n) = 0[t2(n)]. Функция t\(n) не больше функции t2(n) по порядку роста;

t\{n) х t2(n), или t\{n) = Q\t2{n)\. Функция t\{n) равна функции t2(n) по порядку роста.

На функции сложности накладываются отдельные ограничения. Во-первых, полагается, что областью значений этих функций выступает множество неотрицательных действительных чисел R+, а областью определения — множество целых положительных чисел Z₊ (или Z₊ х N), где N — множество натуральных чисел. Во-вторых, при необходимости дискретные пик формально заменяются непрерывными ж и у, а нужные значения вычисляются в целочисленных точках х = п и у = к. В этом случае вместо t(n) или t{n, к) используется запись z{x) или z{x,y) соответственно. В-третьих, предполагается, что функции сложности принадлежат семейству С — рекурсивно определяемому множеству монотонно неубывающих, «по существу положительных» логарифмически-экспоненциальных функций.

Функция z{x) считается «по существу положительной», если существует хо такое, что z{x) > 0 для всех х > хо- Известно, что каждая функция из С (далее просто -функция) непрерывна и дифференцируема в той области, где она определена. Кроме того, если z\{x), 2(ж) Є С, то при х —> оо

либо zi(x) -< Z2(x), либо 2(ж) -< zi(x), либо zi(x) х Z2(x)⁷. Поэтому любые две -функции асимптотически сравнимы между собой по порядку роста, а значит, сравнимы между собой по сложности соответствующие им алгоритмы.

Сделанные в работе предположения относительно функций сложности являются естественными и выполнимыми для большинства реальных алгоритмов.

Вторая глава состоит из восьми параграфов и посвящена классификации алгоритмов по вычислительной сложности. Установление класса сложности алгоритма — один из этапов анализа алгоритма. В данной главе предложен новый метод систематизации алгоритмов, базирующийся на асимптотике поведения эластичности функций сложности. Теоретическое обоснование метода — теорема 2.10. Здесь анализ ограничивается одномерным случаем (когда функция сложности z{x) зависит только от непрерывного аргумента х — длины входа алгоритма).

В параграфе 2.1 исследована классическая систематизация алгоритмов. Отмечено, что данная систематизация — это дихотомия, которая выделяет низкозатратные (полиномиальные) и высокозатратные (экспоненциальные) алгоритмы. Причем эти классы определены с точностью до полиномиальных преобразований длины входов алгоритмов и традиционно устанавливаются путем непосредственного асимптотического оценивания порядка роста функций сложности алгоритмов. Классическая систематизация алгоритмов лежит в основе классификации задач по сложности. Соответственно выделены классы полиномиально разрешимых и трудноразрешимых задач, а для задач разрешения определены классы Р, NP и класс NP-полных задач. В современной алгоритмической практике используют пять сложностных классов алгоритмов (с субполиномиальным, полиномиальным, субэкспоненциальным, экспоненциальным и гиперэкспоненциальным порядком роста функций сложности). В диссертации доказано, что все эти пять классов математически точно и достаточно просто устанавливаются исходя из такой дифференциальной характеристики функций сложности алгоритмов, как эластичность.

В параграфах 2.2 и 2.3 исследуются свойства эластичности -функций. Под эластичностью E_x(z) функции z = z{x) принято понимать предел отношения относительного приращения этой функции к относительному приращению аргумента:

^ , ч , ( Az Ах\ х , Az х , .,

EJz) = Km : =- Km — = -z' = x(lnz '. (1

^v ' Дх^о у z x J z Ax^o Ax z ^v ' ^w

Согласно (1) эластичности присущи свойства, сходные со свойствами

⁷Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. - М.: Мир, 2006.

операций логарифмирования и дифференцирования, поэтому она легко определяется для всякой -функции. Кроме того, при малых Ах справедливо приближение

которое задает подходящую для анализа алгоритмов интерпретацию эластичности: E_x(z) — коэффициент пропорциональности между темпами роста величин z и х. Справедливо

Утверждение 2.1. Для любой С-функции z = z{x) всегда существует эластичность, и E_x{z) > О, E_x{z) = 0(2/In ж). Асимптотическое поведение эластичности С-функции z = z{x) при х —> оо инвариантно относительно полиномиального преобразования, заключающегося в умножении этой функции на константу О 0 и возведении в положительную и отделенную от нуля степень т > 0, то есть E_x{cz^m) = Q[E_x{z)].

В параграфе 2.4 формально выделены шесть классов -функций с принципиально различным порядком роста. С использованием асимптотических обозначений эти классы определены следующим образом:

CONST = {z(x) I z{x) = 0(1)} — асимптотические константы;
SUBPOLY = {z(x) I 1 -< z(x) -< е^в(^1пж)} — функции субполиномиального порядка роста;
POLY = {z(x) I z(x) x е^в(^1пх>} — функции полиномиального порядка роста;
SUBEXP = {z(x) | _е^в(^1пж) -< z(x) -< е^&^} - функции субэкспоненциального порядка роста;
EXP = {z(x) | z(x) х е^в(^ж)} - функции экспоненциального порядка роста;
HYPEREXP = {z(x) | е^в(^ж) -< z(x)} - функции гиперэкспоненциального порядка роста.

В параграфе 2.5 доказана теорема 2.10 о классификации -функций на основе эластичностей. Доказательство базируется на утверждении 2.1 и леммах 2.4—2.9, справедливость которых математически обоснована в диссертации. Согласно этим леммам разным (по порядку роста) классам -функций свойственно принципиально различное поведение эластичности и, наоборот, по асимптотике поведения эластичности можно определить класс, к которому относится эта функция. При этом данное соответствие однозначно, если объединить CONST, SUBPOLY в один класс SUBPOLY.

Теорема 2.10. Разбиение семейства монотонно неубывающих, «по существу положительных» С-функций на классы SUBPOLY, POLY, SUBEXP, EXP, HYPEREXP в соответствии с порядком их роста эквивалентно надлежащему разбиению по асимптотике эластичности этих функций на бесконечности:

SUBPOLY = lz(x) I z(x) -< е^в(-^ЫхЛ = {z(x) \ E_x(z) = o(l)} ; (2)

POLY = [z{x) | z(x) x e^e('^na;)} = {z(x) | E_x(z) x 1} ; (3)

SUBEXP = lz{x) | е^в(^1пж) -< z(x) -< e^e(-^xA = {z(x) | 1 -< E_x(z) -< x} ; (4)

EXP = lz{x) | z(x) x е^в(^ж)} = {z(x) | E_x(z) x x} ; (5)

HYPEREXP = lz{x) | е^в(ж) -< z(x)\ = {z(x) \ x -< E_x(z)} . (6)

Данное разбиение инвариантно относительно полиномиального преобразования, заключающегося в умножении С-функции на константу и возведении в положительную и отделенную от нуля степень.

Из теоремы 2.10 и свойств эластичности вытекают важные следствия.

Следствие 2.11. Разбиение С-функций на указанные в теореме 2.10 классы инвариантно относительно следующего полиномиального преобразования: если и(х) є POLY и z(x) е К, К є { SUBPOLY, POLY, SUBEXP, EXP, HYPEREXP}, mo u(z(x)) Є К.

Следствие 2.12. Класс SUBPOLY замкнут относительно суперпозиции (композиции) С-функций: если z(x), и(х) Є SUBPOLY, то u(z(x)) Є SUBPOLY.

Следствие 2.13. Класс POLY замкнут относительно суперпозиции С-функций: если z{x),u[x) Є POLY, то u(z(x)) Є POLY.

Следствие 2.14. Класс HYPEREXP замкнут относительно суперпозиции С-функций: если z(x),u(x) Є HYPEREXP, то u(z(x)) Є HYPEREXP.

В параграфах 2.6 и 2.7 определены классы сложности алгоритмов через соответствующие классы -функций и описана методика сравнения алгоритмов по асимптотике поведения эластичностей их функций сложности. Если z[x) — время выполнения алгоритма при длине входа х, то E_x(z) — эластичность этого алгоритма. Эластичность алгоритма — это коэффициент пропорциональности между темпом роста времени выполнения алгоритма и темпом роста его длины входа. С учетом этой интерпретации

полученные в теореме 2.10 эквивалентности (2)-(6) порождают пять соответствующих сложностных классов, которые полностью отвечают современной детальной классификации алгоритмов. Класс субполиномиальных (быстрых) алгоритмов образуют алгоритмы, которым свойственна тождественно нулевая или бесконечно малая эластичность. Класс полиномиальных алгоритмов — это множество алгоритмов, для которых эластичность есть асимптотически постоянная величина. Класс субэкспоненциальных алгоритмов — алгоритмы, для которых эластичность есть бесконечно большая величина с порядком роста ниже линейной функции. Класс экспоненциальных алгоритмов состоит из алгоритмов, для которых эластичность — бесконечно большая величина, асимптотически равная (по порядку роста) линейной функции. Класс гиперэкспоненциальных алгоритмов образуют алгоритмы, для которых эластичность есть бесконечно большая величина с порядком роста выше линейной функции.

В параграфе 2.8 предложено более крупное разбиение алгоритмов на классы: выделены и определены неэластичные, эластичные, суперэластичные алгоритмы — алгоритмы с бесконечно малой, асимптотически постоянной и бесконечно большой эластичностью соответственно. Неэластичные и эластичные алгоритмы практически значимые, так как эффективные. Суперэластичные алгоритмы очень чутко реагируют на изменение длины входа и с этой точки зрения хорошо управляемые по сложности через эту величину.

В выводах к главе 2 указаны следующие достоинства предложенного метода систематизации алгоритмов. Эластичности достаточно легко вычисляются и представляются более простыми по виду функциями, чем отвечающие им логарифмически-экспоненциальные функции сложности алгоритмов. Поэтому их применение на практике обеспечивает «прозрачность» сложностных классов и облегчает анализ алгоритмов. Прежняя традиционная классификация с полиномиальными и экспоненциальными алгоритмами не разрушается, а лишь дополняется и уточняется. Допустимо обобщение данного метода на функции сложности многих переменных.

Третья глава диссертации состоит из четырех параграфов и посвящена анализу сложности рекурсивных алгоритмов. В этой главе установлены и теоретически обоснованы верхние и нижние оценки времени выполнения рекурсивного алгоритма, построенного на основе принципа «уменьшай и властвуй», то есть путем аддитивного уменьшения размера задачи на некоторую константу (теорема 3.3). Здесь анализируются функции сложности t(n) от одного дискретного аргумента п — длины входа алгоритма.

В параграфе 3.1 раскрыты проблемы анализа рекурсивных алгоритмов. В параграфе 3.2 представлены рекуррентные соотношения, которые характерны для прямой рекурсии, организованной по принципам «разделяй и властвуй» и «уменьшай и властвуй». Указаны наиболее распространен-

ные случаи, когда эти соотношения могут быть решены: постоянное число подзадач, создаваемых на каждом шаге рекурсии, и полиномиальная трудоемкость рекурсивного перехода.

В параграфе 3.3 исследованы оценки Дж. Бентли, Д. Хакена, Дж. Сакса, полученные ими для времени выполнения рекурсивного алгоритма, организованного по принципу «разделяй и властвуй». Этот широко известный результат уже давно применяется при анализе и разработке эффективных алгоритмов. Согласно нему рекурсивная реализация принципа «разделяй и властвуй» всегда приводит к быстрым и полиномиальным алгоритмам.

В параграфе 3.4 сформулирована и доказана теорема 3.3. Данная теорема позволяет находить верхние и нижние асимптотические оценки времени выполнения рекурсивного алгоритма, построенного путем аддитивного уменьшения размера задачи на некоторую константу к Є N. Такие алгоритмы, например, порождает рекурсивная реализация метода динамического программирования.

Теорема 3.3. Пусть дано рекуррентное соотношение

с, если 0 < п < к — 1,

(7) at(n — к) + Ъп^Т, если п > к,

где а > О, к > 1 — целые константы, b >0, с >0, т >0 — вещественные константы. Тогда при п = km, т Є Z+ ип->оо верны оценки

t(n) = Q(n), t(n) = О (n^T+1) , а=1, Ь>0; (8)

t(n) = Q(aⁿ/^k), t{n) = o(n^Taⁿl^k\ a > 1, b > 0; (9)

t(n) = 6(1), a= 1, 6 = 0; (10)

t(n) = Є (a^n/k) , a > 1, b = 0. (11)

В рекуррентном соотношении (7) константа а трактуется как число подзадач, порождаемых рекурсивной ветвью алгоритма, а степенная функция Ьп^Т определяет трудоемкость рекурсивного перехода. Оценки (10) и (11) отвечают случаю «бесплатного» рекурсивного перехода. В работе установлены другие частные случаи, когда из (8), (9) вытекают О-оценки. Они отражены в следствиях 3.4-3.7.

Следствие 3.4. В предположениях теоремы 3.3 при т = 0 решением рекуррентного соотношения (7) является функция

Ъ
с+ —п, если а = 1,

t(n)

а^п/кс+Ъ —, если а > 1.

а — 1

Следствие 3.5. При т = О, любых значениях b > О, с >0 и п —» оо для решения рекуррентного соотношения (7) верны оценки

О(п), если а = 1, Ъ > О,

в (a^n/fc) , если a > 1, 6 > 0.

Следствие 3.6. Для решения рекуррентного соотношения (7) при а = 1, с>0, Ъ > 0, целых положительных тип-»оо справедлива оценка

t{n) = в (n^T+1) .

Следствие 3.7. Для решения рекуррентного соотношения (7) при а > 1, с>0, Ъ > 0 и целых положительных т верна оценка

t(n) = в (n^Taⁿ'^k\ .

Из оценок теоремы 3.3 и следствий 3.4-3.7 вытекают важные для практики положения: рекурсивные алгоритмы, образованные аддитивным уменьшением размера задачи на некоторую константу, могут быть быстрыми, полиномиальными и экспоненциальными. Быстрый алгоритм возможен только в тривиальной ситуации (при одной подзадаче и нулевых затратах на рекурсивный переход). Полиномиальные алгоритмы возникают лишь в случае, когда исходная задача сводится к одной подзадаче меньшего размера. При числе подзадач а > 1 рекурсивный алгоритм, построенный путем аддитивного уменьшения размера задачи на некоторую константу, всегда экспоненциальный по времени и никакие усовершенствования процедуры разбиения и объединения подзадач не способны изменить класс его сложности. Причина этого кроется в возникновении на каждом шаге рекурсии перекрывающихся подзадач. Данные положения служат математическим обоснованием тому факту, что метод динамического программирования для большинства задач выбора реализуется итерационно (с помощью табличной техники): для него перекрытия подзадач обязательны, но

именно эти перекрытия — источник экспоненциальной сложности рекурсивной реализации метода.

В выводах к главе 3 отмечено, что результат Дж. Бентли, Д. Хаке-на и Дж. Сакса и доказанная в диссертации теорема 3.3 предоставляют разработчикам алгоритмов и программ средства асимптотической оценки сложности рекурсивных алгоритмов, построенных определенным образом. Их применение не требует особых математических знаний, и потому они могут быть использованы в широкой алгоритмической практике для построения эффективных алгоритмов.

Четвертая глава содержит шесть параграфов. Основной результат этой главы — метод двумерной классификации параметризированных алгоритмов на основе частных эластичностей. Метод позволяет сравнивать между собой параметризированные алгоритмы по времени выполнения и легко распространяется на параметризации задач с несколькими параметрами.

В параграфе 4.1 кратко обсуждаются традиционные классы сложности задач, концепция NP-полноты и современные подходы к решению трудноразрешимых задач. В параграфах 4.2 и 4.3 диссертации исследуется пара-метризированный подход к оценке сложности вычислений, вводится необходимый понятийный аппарат.

Параметризованная задача П (в распознавательной формулировке) — язык, определяемый как Ь(П) С * х N, где — некоторый конечный алфавит, * — множество всех слов в данном алфавите, N — множество натуральных чисел. Каждая пара значений (/, к) Є L(TV) выступает в качестве экземпляра параметризированной задачи П и входа алгоритма, решающего данную задачу. При этом величина п = \1\ задает длину входа алгоритма, к — значение параметра. Если параметризированная задача П может быть решена некоторым алгоритмом за время, не более чем

n^-f(k), (12)

то ее называют FPT-разрешимой относительно параметра к, а соответствующий алгоритм — FPT-алгоритмом⁸. Примечательно, что в (12) функция f(k) зависит только от к. Соотношение (12) определяет верхнюю асимптотическую оценку времени выполнения FPT-алгоритма и свидетельствует о том, что при каждом фиксированном к данный алгоритм полиномиальный относительно п. В этом смысле t(n, к) = О (п * ' /(&)).

В параграфе 4.4 излагается метод двумерной классификации параметризированных алгоритмов на основе частных эластичностей. Здесь вновь формально дискретные п и к заменяются на непрерывные х и у соответственно, и вместо t{n,k) используется запись z{x,y).

⁸Niedermeier R. Invitation to fixed-parameter algorithms: Oxford Lecture series in mathematics and its applications, V. 31. — Oxford University Press, 2006.

Частная эластичность E_x(z) функции z = z{x,y) по аргументу х — эластичность переменной z, которая рассматривается как функция только от ж и при постоянных значениях у. Аналогичным образом определяется частная эластичность E_y(z) функции z = z{x,y) по аргументу у.

Если функция z{x,y) отражает время работы параметризированного алгоритма при длине входа х и значении параметра у, то E_x(z) — коэффициент пропорциональности между темпом роста времени выполнения этого алгоритма и темпом роста длины входа (при постоянном значении параметра). Аналогично E_y(z) — коэффициент пропорциональности между темпом роста времени выполнения параметризированного алгоритма и темпом роста параметра у (при постоянной длине входа).

В общем случае частные эластичности E_x(z), E_y(z) являются функциями, зависящими от ж и у. Однако ситуация значительно упрощается, если время работы параметризированного алгоритма описывается -функцией, имеющей мультипликативную форму записи: z{x,y) = q(x) f(y), где q(x) Є С — количественная компонента, a f(y) Є С — параметрическая компонента функции z{x,y). Так, условие FPT-разрешимости (12) традиционно определяется именно через мультипликативную форму записи функции сложности параметризированного алгоритма.

В параграфе 4.4 в условиях мультипликативной формы записи функций сложности и в границах семейства -функций разработан метод двумерной классификации параметризированных алгоритмов на основе частных эластичностей. Суть метода состоит в следующем.

Рассмотрим функцию z{x, у) = q(x) f(y) Є С. Согласно свойствам эластичностей величины E_x(z) и Ey(z) вырождаются в обычные эластичности функции одного аргумента:

E_x(z) = E_x[q(x) f(y)] = E_x[q(x)\ + E_x[f(y)\ = E_x[q(x% (13)

E_y(z) = E_v[q{x) f(y)] = E_y[q(x)] + E_y[f(y)] = E_y[f(y)]. (14)

Теперь E_x(z) зависит лишь от x, a E_y(z) зависит только от у. По теореме 2.10 каждая из функций q(x), f(y) принадлежит только одному сложност-ному классу (по надлежащему аргументу) из множества

К, = {SUBPOLY, POLY, SUBEXP, EXP, HYPEREXP} .

Пусть К_х — класс сложности функции q{x) по аргументу ж, и К_у — класс сложности функции f(y) по аргументу у. Пусть эти классы определены исходя из теоремы 2.10 и соответствующих частных эластичностей (13)-(14). Тогда всякому параметризированному алгоритму с функцией сложности z(x, у) = q{x)-f{y) Є С отвечает пара (К_х, К_у) Є KLxKL. Эта пара характеризует сложность данного алгоритма по длине входа х и значению параметра у. Таким образом, мы приходим к двумерной классификации

параметризированных алгоритмов по вычислительной сложности. Очевидно, что при наличии нескольких параметров возможно введение подобным образом многомерной классификации параметризированных алгоритмов. При двумерном подходе отчетливую формулировку получает определение FPT-алгоритма. Параметризированный алгоритм является FPT-алгоритмом, если время его работы задается функцией z{x, у) = q(x) f(y), для которой

(К_х, К_у) є {SUBPOLY, POLY} х К.

В параграфе 4.4 диссертации FPT-алгоритмы систематизированы по сложности относительно параметра у. Алгоритмы, вычислительная сложность которых соответствует парам

(К_Х,К_У) є {SUBPOLY, POLY} х {SUBPOLY, POLY} ,

(K_x, К_у) є {SUBPOLY, POLY} x {SUBEXP} ,

(K_x, K_y) є {SUBPOLY, POLY} x {EXP} ,

(K_x, K_y) є {SUBPOLY, POLY} x {HYPEREXP} ,

определены как полиномиальные, субэкспоненциальные, экспоненциальные и гиперэкспоненциальные FPT-алгоритмы соответственно. Субэкспоненциальные, экспоненциальные и гиперэкспоненциальные FPT-алгоритмы присущи NP-трудным задачам. Они суперэластичные по параметру (при постоянной длине входа).

Анализ параметризированных алгоритмов предполагает не только определение класса сложности алгоритма, но и установление степени влияния параметра на время выполнения алгоритма. В параграфе 4.5 диссертации разработана методика, позволяющая проводить такие исследования. Она основана на коэффициенте замещения одного аргумента функции другим аргументом. Этот коэффициент определяется и интерпретируется следующим образом. Пусть z{x, у) Є С. Тогда величина

dx xEy(z) dy yE_x(z)

есть коэффициент замещения одного аргумента функции другим, при условии, что значения функции постоянные (отвечают некоторой линии уровня). Формулу (15) можно записать так:

-dx=^44=Mdy. (16)

Соотношение (16) дает следующее толкование коэффициенту замещения: при некотором постоянном значении z (реально осуществимой нормы времени исполнения алгоритма) уменьшение значения параметра у на

Ay = 1 позволяет увеличить х — длину входа алгоритма — примерно на М, то есть регулировать вычислительные возможности алгоритма на входах большой длины.

Для определения FPT-алгоритма традиционно применяется мультипликативная форма представления функции сложности алгоритма. В параграфе 4.6 диссертации предложены аддитивная и смешанная формы представления, доказана их эквивалентность мультипликативной форме в смысле FPT. Этот результат отражает

Утверждение 4.1. Пусть задана задача П, параметризированная относительно параметра у.Следующие высказывания эквивалентны.

Для задачи П существует FPT-алгоритм со временем работы 0[q{x) f{y)}, где q{x) — функция полиномиального или субполиномиального порядка роста от длины входа х.
Для задачи П существует FPT-алгоритм со временем работы 0[и{х) + w{yj\, где и{х) — функция полиномиального или субполиномиального порядка роста от длины входа х.
Для задачи П существует FPT-алгоритм со временем работы 0[qi{x) /і(у) + qi{x) fi{y)}, где qi{x), 72(^) — функции полиномиального или субполиномиального порядка роста от длины входа х.

Утверждение 4.1 расширяет область применимости разработанных в главе 4 математических средств анализа параметризированных алгоритмов.

Пятая и шестая главы диссертации посвящены алгоритмическим аспектам развития метода динамического программирования по дереву декомпозиции. Обсуждаются две проблемы, сдерживающие практическое применение этого метода при решении задач выбора большой размерности: проблема памяти и проблема вычисления древовидной ширины. В пятой главе разработаны и математически обоснованы средства решения первой из указанных проблем. Методам и алгоритмам решения второй проблемы отведена шестая глава диссертации.

В параграфе 5.1 дан краткий обзор основных методов разработки FPT-алгоритмов. Отмечено, что в настоящее время уже предложены и апробированы несколько специальных методов конструирования FPT-алгоритмов, наиболее универсальный из них — метод динамического программирования по дереву декомпозиции. Этот метод ориентирован на параметризированные задачи выбора, представимые графами и гиперграфами ограниченной древовидной ширины. Именно по древовидной ширине должна быть осуществлена параметризация решаемой задачи.

В параграфе 5.2 приводятся определения и известные свойства дерева декомпозиции и древовидной ширины графа⁹. Пусть О = (V, Е) — связный неориентированный граф, \V\ > 1 и \Е\ > 1. Дерево декомпозиции графа G = (V, Е) представляет собой пару {Mq, Tq), задающую разбиение множества вершин и множества ребер графа О, где Mq = {Хі \ і Є Iq} — семейство подмножеств множества V, называемых «мешками», а Tq = {la, W) — дерево, узлам которого сопоставлены эти «мешки». Вершины дерева Tq принято называть узлами, чтобы избежать путаницы с вершинами графа О. Семейство Mq и множество W ребер дерева Tq такие, что справедливы условия:

объединение множеств вершин, образующих «мешки» Хі, і Є Iq, дает множество V;
для всякого ребра графа О обязательно имеется хотя бы один «мешок», содержащий обе вершины этого ребра;
для любой вершины v графа О множество узлов {і Є Iq \ v Є Хі}, «мешки» которых содержат эту вершину, индуцирует связный подграф, являющийся поддеревом дерева Tq.

Ширина дерева декомпозиции {Mq, Tq) равна наибольшей вместимости его «мешка», уменьшенной на единицу:

тахЦХіІ-1}.

iela

Древовидная ширина {treewidth) графа О определяется как наименьшая ширина всех допустимых его деревьев декомпозиции и обозначается через tw{G). Дерево декомпозиции {Mq,Tq) ширины tw{G) называется оптимальным, а без кратных и вложенных «мешков» — фундаментальным. Для tw{G) верны естественные границы: 1 < tw{G) < \V\ — 1. Пусть к — некоторая заданная целая положительная константа, и к < \V\. Если tw{G) < к, то говорят, что граф О обладает ограниченной (значением к) древовидной шириной.

Структуру многих задач выбора удобно представлять и интерпретировать в терминах гиперграфов. В параграфе 5.2 понятия дерева декомпозиции и древовидной ширины обобщены применительно к гиперграфам и доказано

Утверждение 5.6. Всякое дерево декомпозиции {Мн, Тн) связного гиперграфа Н есть дерево декомпозиции графа L^'{H) и наоборот, любое

^sBodlaender H.L. Discovering treewidth // Proc. of the 31st Conference SOFSEM 2005, Springer-Verlag LNCS 3381. - 2005. - P. 1-16.

дерево декомпозиции графа L^²'(H) задает дерево декомпозиции гиперграфа Н. Кроме того, древовидная ширина гиперграфа Н равна древовидной ширине графа LW(H).

Таким образом, с точки зрения древовидной ширины граф L^\H), отражающий отношение смежности вершин гиперграфа Н, полностью определяет этот гиперграф. Поэтому гиперграфовое описание задач выбора, хотя и не вносит ничего существенного в метод динамического программирования по дереву декомпозиции в сравнении с представлением таких задач графами, зато позволяет привлекать для его реализации свойства ациклических гиперграфов. Ограниченная древовидная ширина исходного графа и гиперграфа — это условие применимости данного метода. Чем меньше древовидная ширина, тем меньше вычислительных ресурсов нужно FPT-алгоритму, реализующему динамическое программирование по дереву декомпозиции.

В параграфе 5.3 дано описание метода динамического программирования по дереву декомпозиции. Указаны рекурсивные правила выделения подзадач. В параграфе 5.4 исследованы достаточные условия FPT-разрешимости задач выбора относительно древовидной ширины, устанавливаемые теоремой Курселя¹⁰. Согласно теореме Курселя, данный метод приводит к FPT-алгоритму со временем работы 0(|V| /(&)), если решаемая задача может быть сформулирована в виде конечной формулы монадической логики второго порядка и входной граф О = (У, Е) имеет tw(G) < к.

Динамическое программирование по дереву декомпозиции по своей сути — рекурсивный метод. Число подзадач, возникающих на каждом шаге рекурсии, определяется арностью дерева, которая в общем случае больше единицы. По теореме 3.3 рекурсивная реализация метода неминуемо приводит к неполиномиальному времени вычислений относительно длины входа. Для получения FPT-алгоритма требуется этот метод реализовывать с помощью табличной техники. Однако данная техника порождает проблему памяти для размещения создаваемых таблиц динамического программирования: сколько узлов содержит дерево декомпозиции, столько таблиц возникает; размер всякой таблицы экспоненциально зависит от арности и ширины применяемого дерева декомпозиции. В частности, если в методе динамического программирования исходить из бинарного дерева декомпозиции графа О = (У, Е) ширины к и с 0(|У|) узлами, то общая потребность соответствующего алгоритма в памяти и времени составит 0(|У| к q^3k), где q — число состояний, в которых может находиться вершина графа к допустимому решению. Таким образом, проблема памяти — серьезное пре-

¹⁰Courcelle В. The monadic second-order logic of graphs. III. Tree decompositions, minors and complexity issues // RAIRO Inform. Theor. Appl. - 1992. - 26(3). - P. 257-286.

пятствие применимости этого метода на практике.

Для решения проблемы памяти применяют различные преобразования дерева декомпозиции¹¹. Наиболее известное в этом отношении — Kloks-дерево¹². Данное дерево дает возможность удерживать размер всякой таблицы динамического программирования в пределах оценки 0(к q^k). Между тем это достигается за счет увеличения числа таблиц примерно в к раз. В параграфе 5.5 предложено бинарное сепараторное дерево декомпозиции (BfeS-дерево), которое обеспечивает компромисс между размером и числом таблиц динамического программирования.

В диссертации BfeS-дерево определено следующим образом. Корневое дерево декомпозиции (Ма,Та), Mq = {Хі \і є Іа},Та = (Ig,W), связного графа О = (V, Е) называется BfeS-деревом, если в нем каждый узел имеет не более двух прямых потомков и относится к одному из четырех типов узлов:

узел-лист — узел, у которого нет потомков;
узел-сепаратор — узел s с одним прямым потомком j и узлом і в роли родителя. Всегда X_s — сепаратор (разделяющее множество вершин) графа G ж X_s=X_iC\X_j^ &, X_s С Хі, X_s С X,-;
узел-расширение — узел г с одним прямым потомком s. В данном случае X_s СХ₄;
узел-соединение — узел г с двумя прямыми потомками 1 я j. Здесь

XtUXjCXi.

В параграфе 5.5 доказано

Утверждение 5.11. Всякое фундаментальное дерево декомпозиции

{Ма, Та) графа G = (У, Е), где Mq = {Хі \ і є Іа\, Та = {la, W), имеющее ширину k и 0(\V\) узлов, может быть преобразовано за время 0(\V\) в B&iS-depeeo, которое обладает той же шириной и 0{\V\) узлами.

Показаны и теоретически обоснованы следующие достоинства В&Я-дерева. Переход от бинарного корневого дерева декомпозиции к BfeS-дереву увеличивает число таблиц не более чем в два раза (за счет добавления узлов-сепараторов). BfeS-дерево удерживает размер всякой таблицы динамического программирования в тех же пределах, что и Kloks-дерево. Для вычисления таблиц динамического программирования по В&Б-дереву возможно привлечение аппарата реляционной алгебры и

¹¹Aspvall В., Proskurowski A., Telle J.A. Memory requirements for table computations in partial k-tree algorithms // Algorithmica. - 2000. - 27(3). - P. 382-394.

¹²Kloks T. Treewidth. Computations and Approximations. - Springer-Verlag LNCS 842, 1994.

свойств ациклических баз данных. Это способствует алгоритмической конкретизации метода и сокращению числа строк в промежуточных таблицах (за счет применения монотонного плана соединения и программы полусоединений таблиц).

В параграфе 5.6 показано применение метода динамического программирования по В&Я-дереву при решении оптимизационных задач (на примере задачи о вершинном покрытии) и задач удовлетворения ограничений (на примере задачи SAT, Satisfiability). Для задач удовлетворения ограничений употреблено гиперграфовое описание.

В выводах к главе 5 отмечено, что реляционный взгляд на процесс динамического программирования (как процесс соединения таблиц, находящихся в разных узлах дерева декомпозиции) позволяет при решении задач выбора применять свойства ациклических баз данных и выполнять поиск решения в режиме распределенных вычислений. Использование при этом В&8-дерева дает возможность существенно снижать теоретические и реальные потребности в вычислительных ресурсах FPT-алгоритмов, реализующих метод динамического программирования на графах и гиперграфах ограниченной древовидной ширины.

Для практического применения метода динамического программирования по дереву декомпозиции необходимо убедиться, что входной граф имеет ограниченную (значением к) древовидную ширину и при положительном ответе построить дерево декомпозиции такой ширины. Между тем, сама задача вычисления древовидной ширины является NP-трудной. Хотя на сегодняшний день известен широкий спектр точных, приближенных и эвристических алгоритмов решения этой задачи, вопрос ее алгоритмического обеспечения нельзя считать закрытым. Необходимость практического решения данной задачи в условиях большой размерности для произвольных видов графов и гиперграфов требует новых алгоритмов и подходов.

В шестой главе диссертации разработаны и теоретически обоснованы два рекуррентных метода, позволяющие снижать размерность задачи вычисления древовидной ширины и вычислять нижние и верхние оценки древовидной ширины входного графа и гиперграфа.

В параграфе 6.1 представлен краткий обзор популярных на сегодняшний день методов вычисления древовидной ширины графа. В параграфе 6.2 приведены известные нижние границы значений древовидной ширины графа G = (V, Е), связывающие tw{G) с другими числовыми параметрами этого графа. Отмечено, что наиболее существенные из этих оценок труд-новычисляемые и потому актуальны различные способы предобработки, снижающие размерность задачи вычисления древовидной ширины. В параграфе 6.3 разработан и теоретически обоснован рекуррентный метод, позволяющий редуцировать входной граф и гиперграф и вычислять нижние оценки его древовидной ширины. Данный метод реализует принцип

«уменьшай и властвуй» и опирается на свойства хордальных графов и ациклических гиперграфов. Обоснованием метода служат доказанные в диссертации следующие положения.

Лемма 6.5. Если v Є V — симплициалъная вершина графа G = (V, Е) степени deg(v), то

tw(G) = max.{deg(v),tw(G — v)}. (17)

Лемма 6.6. Всякая висячая вершина гиперграфа Н = (X, U) — симплициалъная вершина графа Ь^\Н).

Утверждение 6.7. Пусть х Є X является висячей вершиной гиперграфа Н = [X, U) степени d (для нее в обозначениях теории гиперграфов¹³: х Є Х(и), U(x) = {и} и d = \Х(и)\ — 1). Пусть гиперграф Н' = Hfj,(X — х) получен из Н слабым удалением вершины х с последующей минимизацией (удалением кратных и вложенных ребер). Тогда

tw(H) = maxjd, tw(H')}. (18)

Рекуррентные формулы (17), (18) дают способ вычисления древовидной ширины путем последовательного удаления симплициальных вершин в графе и висячих вершин в гиперграфе. В работе представлен рекурсивный алгоритм, реализующий данный метод. Если входной граф хордальный (или гиперграф ациклический), то алгоритм вырождается в рекурсивный процесс вычисления древовидной ширины этого графа (или гиперграфа). По теореме 3.3 алгоритм имеет полиномиальную временную сложность относительно числа входящих в граф (или гиперграф) вершин.

В параграфах 6.4-6.6 изложен и теоретически обоснован рекуррентный метод верхнего оценивания древовидной ширины. Этот метод основан на свойствах сепараторов. Он воплощает принцип «разделяй и властвуй» (разбивая исходный граф или гиперграф на части) и потому всегда имеет полиномиальную относительно числа вершин рекурсивную реализацию при условии, что применяемые сепараторы полиномиально вычисляемые. Изложим суть данного метода применительно к графам.

Говорят, что множество вершин S С V разделяет несмежные вершины а и b связного графа G = (V,E), если в графе G(V \ S) вершины а и b принадлежат различным компонентам связности. Множество S при этом называется (а, Ь)-сепаратором и минимальным (а, Ь)-сепаратором, если S есть (а, Ь)-сепаратор, и в нем нет собственного подмножества, являющегося (а, Ь)-сепаратором. Сепаратор S называется минимальным, если

¹³Зыков А.А. Гиперграфы // УМН. - 1974. - Т. 29. - Вып. 6. - С. 89-154.

в графе G существует такая пара вершин а и 6, что S — минимальный (а, Ь)-сепаратор.

Пусть A(G) — множество сепараторов связного графа G = (V, Е) и S є A(G). Обозначим через Yi, 1) ) ^т области связности графа G(V \ S*). Части Gi, G2, ..., G_T графа G, выделенные в результате его разделения сепаратором S, определим следующим образом:

Gi=G(YiUS)UK(S),

где K(S) — полный граф на множестве вершин S, і Є Is = {1, 2,..., т}. В частности, если S — точка сочленения графа G, то G\, G2, ..., G_T — блоки этого графа. Сепаратор S графа G назовем целесообразным относительно tw(G), если справедливо равенство

tw(G) = max{tw(Gj) | і Є Is}- (19)

Данное равенство определяет рекуррентное соотношение для вычисления древовидной ширины графа через его части, полученные разделением G сепаратором S. В параграфе 6.4 доказаны утверждения 6.9, 6.13, согласно которым кликовые сепараторы и минимальные почти кликовые сепараторы гарантируют справедливость (19). Кликовый сепаратор — сепаратор графа G, образующий в G клику. Сепаратор S графа G считается почти кликовым, если существует вершина v Є S такая, что множество S\ {v} — клика графа G.

В параграфе 6.5 исследуются минимальные кликовые и минимальные почти кликовые сепараторы. Показано, что такие сепараторы всегда можно извлечь за полиномиальное время из минимальной триангуляции графа. Напомним, что триангуляцией графа G = (V, Е) называется хордальный граф G' = (У, Е'), который содержит граф G в качестве остовного подграфа (Е С Е'). Триангуляция G' минимальная, если для G не существует другой триангуляции, которая образует собственный подграф графа G'. Известно, что всякий минимальный сепаратор S минимальной триангуляции G' = (V, Е') — минимальный сепаратор исходного графа G = (V,E), Е С Е', а для вычисления минимальной триангуляции G' = (У, Е') достаточно 0(|У]³) времени¹⁴.

В параграфе 6.5 также дано описание рекурсивного алгоритма разложения заданного графа на части минимальными кликовыми и минимальными почти кликовыми сепараторами и вычисления верхней оценки древовидной ширины этого графа с использованием формулы (19). Верхние оценки для частей графа вычисляются на основе неравенств tw(Gi) < twiG'j), где G^ — соответствующие минимальные триангуляции.

¹⁴Berry A., Bordat J.P., Heggernes P., Simonet G., Villanger Y. A wide range algorithm for minimal triangulation from an arbitrary ordering // J. Algorithms. - 2006. 58(1). - P. 33-66.

В параграфе 6.6 предложенный метод обобщен на гиперграфы (лемма 6.18, утверждение 6.19). Указаны правила формирования частей разложения.

Результат разложения графа и гиперграфа на части минимальными кликовыми и минимальными почти кликовыми сепараторами зависит от порядка выбора этих сепараторов, поскольку допустимы разделяющие друг друга сепараторы. Между тем, если для разложения использовать только минимальные кликовые сепараторы, то результат уникален. Уникальность такого разложения применительно к графам была установлена Г. Лаймером¹⁵ в 1993 г. В параграфе 6.7 диссертации доказано утверждение 6.20, согласно которому уникальность сохраняется и для гиперграфов.

Пусть Н = (X, U) — связный гиперграф без кратных и вложенных ребер и Y С X — это максимальное по включению подмножество вершин такое, что гиперграф H(Y) связен и не содержит минимальных кликовых сепараторов. Гиперграф H(Y) назовем атомом гиперграфа Н. Заметим, что H(Y) — часть гиперграфа Н = [X,U), индуцированная множеством Y С X. Пусть А(Н) — множество минимальных кликовых сепараторов, Ф(і7) — множество частей гиперграфа Н, полученных рекурсивным разложением этого гиперграфа сепараторами из А(Н), при этом каждая часть — некоторый гиперграф H(Yl) с областью связности Yi(i Є Ін)-

Утверждение 6.20. Разложение Ф(Д") = {H(Yi) | г Є Ін} определяет уникальное для заданного гиперграфа Н множество атомов.

Эта уникальность означает следующее. Результат разложения не зависит от порядка выбора минимальных кликовых сепараторов. Каждый из гиперграфов H(Yi) Є ^(Н) — атом гиперграфа Н, и никакой из атомов этого гиперграфа не утерян при разложении. Состав атомов, образующих Я>(Н), не зависит от минимальных триангуляции, используемых для нахождения минимальных кликовых сепараторов.

В выводах к главе 6 отмечено, что разработанные в диссертации методы нижнего и верхнего оценивания древовидной ширины имеют полиномиальную сложность относительно числа вершин входного графа (или гиперграфа) и потому представляют ценность для практического применения метода динамического программирования по дереву декомпозиции при решении задач выбора, возникающих в рамках новых информационных технологий. Конечно, существуют графы и гиперграфы, для которых использование данных методов не приводит к желаемому эффекту (в них нет симплициальных и висячих вершин, отсутствуют минимальные кликовые и минимальные почти кликовые сепараторы). Поэтому перспективны дальнейшие исследования, направленные на разработку других методов

¹⁵Leimer H.G. Optimal decomposition by clique separators // Discrete Mathematics. 1993. - 113. - P. 99-123.

вычисления и оценивания древовидной ширины. Утверждение 6.20 открывает дополнительные вычислительные возможности приложений гиперграфовых моделей систем, поскольку атомарное разложение гиперграфа может быть использовано не только в аспекте древовидной ширины, но в других задачах, базирующихся на отношениях смежности вершин.

В заключении сформулированы основные результаты диссертационной работы. В приложениях 1 и 2 приведены свойства хордальных графов и ациклических гиперграфов, алгоритмы построения минимальных триангуляции и тесты на ацикличность, цитируемые в главах 5 и 6 диссертации. В приложении 3 дано описание комплексов программ, в которых реализованы основные алгоритмы диссертации.

Методы анализа и разработки параметризированных алгоритмов Быкова, Валентина Владимировна

Похожие диссертации на Методы анализа и разработки параметризированных алгоритмов