URSS.ru - Издательская группа URSS. Научная и учебная литература
Об издательстве Интернет-магазин Контакты Оптовикам и библиотекам Вакансии Пишите нам
КНИГИ НА РУССКОМ ЯЗЫКЕ


 
Вернуться в: Каталог  
Обложка Бондаренко В.А., Максименко А.Н. Геометрические конструкции и сложность в комбинаторной оптимизации
Id: 72597
 
252 руб.

Геометрические конструкции и сложность в комбинаторной оптимизации

URSS. 2008. 184 с. Мягкая обложка. ISBN 978-5-382-00687-1.

 Аннотация

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

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


 Оглавление

Предисловие
1. Введение
 1.1. Задачи и алгоритмы комбинаторной оптимизации
 1.2. Элементы теории выпуклых многогранников
2. Алгоритмы, использующие линейные сравнения
 2.1. Унифицированная постановка задач
 2.2. Многогранники задач. Конусное разбиение
 2.3. Линейные разделяющие деревья
 2.4. Алгоритмы прямого типа
3. Алгоритмы и многогранники конкретных задач
 3.1. Предварительные замечания
 3.2. Задачи сортировки, перестановочные многогранники
 3.3. Матроиды и "жадный" алгоритм
 3.4. Задача о кратчайшем пути
 3.5. Задачи о паросочетаниях
 3.6. Задача коммивояжера
 3.7. Другие труднорешаемые задачи
4. Аффинная сводимость
 4.1. Граф полиэдрального разбиения
 4.2. Аффинная сводимость
 4.3. Задача о клике
 4.4. Задача коммивояжера
 4.5. Задача о трехмерном сочетании
 4.6. Задачи рюкзак и разбиение
 4.7. Задача о назначениях
5. Многогранники с высокой плотностью графа
 5.1. Об одной гипотезе Д.Гейла
 5.2. К вопросу о полиномиальной разрешимости задач
 5.3. Корневые полуметрические многогранники
Список литературы

 Предисловие

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

Общим для задач этого типа является выраженный комбинаторный характер множества X, причем число его элементов |Х| стремительно растет при увеличении размерности задачи. Так, для упомянутых задач значения |Х| равны соответственно (п - 1)!/2, пn-2 и n!, где п -- число вершин неориентированного графа в случае задачи коммивояжера и задачи о минимальном остовном дереве, и число работников (и работ) в случае задачи о назначениях. В связи с этим важным оказывается вопрос о существовании алгоритмов, более эффективных, чем полный перебор вариантов. Учитывая, что для многих задач эффективные алгоритмы не найдены, поставленный вопрос можно уточнить вопросом о том, какие свойства той или иной задачи характеризуют ее как труднорешаемую.

Частичный ответ на поставленные вопросы можно получить на основании теории С. Кука NP-полных задач [28]. Именно, если данная задача в варианте задачи распознавания является NP-полной, то, согласно распространенной гипотезе, эффективного алгоритма для нее не существует. (Здесь под задачей распознавания понимается следующая: верно ли, что для заданного С существует такой х [in] X, что с(х) >- С.) То есть, говоря огрубленно, данная задача объявляется труднорешаемой, если некоторая признанно труднорешаемая задача является частным случаем данной.

Другой подход к исследованию задач с точки зрения поставленных выше вопросов связан с изучением комбинаторно-геометрических свойств этих задач и геометрической интерпретацией алгоритмов. Этот подход основывается на представлении множества X как множества точек в вещественном евклидовом пространстве Rm и на предположении (обычно оно выполняется), что функция цели с(х) является линейной: с(х) = (с, x), где с [in] Rm. Первые попытки исследования задач комбинаторной оптимизации в таком виде предприняты, по-видимому, Г.Куном [25] для задачи коммивояжера, и касались геометрического моделирования непосредственно задачи. В дальнейшем, начиная с работ Ю.И.Журавлева [31,32], предметом комбинаторно-геометрического анализа часто является система "задача-алгоритм"; основное направление этого анализа сосредоточено на получении оценок сложности задач в тех или иных классах алгоритмов. В работе Й.Моравека [95] формализуется класс алгоритмов, основанных на линейных сравнениях, и предпринимается попытка получения нижних оценок числа сравнений, необходимых для решения задачи. Источником получения таких оценок обычно служат различные характеристики графа многогранника conv X задачи; в частности, оказывается, что плотность графа многогранника является нижней оценкой сложности соответствующей задачи в широком классе алгоритмов, использующих линейные неравенства. Последним обстоятельством объясняется интерес к комбинаторным многогранникам с высокой плотностью графа. Здесь уместно упомянуть фундаментальный факт, установленный К.Каратеодори [71] и "переоткрытый" впоследствии Д.Гейлом [25]: в пространстве Rm при т >- 4 существуют выпуклые многогранники с любым количеством попарно смежных вершин.

Настоящая работа объединяет полученные за последние десять лет результаты, направленные на выяснение причин, препятствующих построению эффективных алгоритмов для большинства задач комбинаторной оптимизации. Содержательную основу этих результатов составили геометрические конструкции, появляющиеся при естественной интерпретации задач и алгоритмов. Материал, собранный в книге, служит дополнением к опубликованным в последние годы обзорам и монографиям, посвященным различным аспектам дискретных задач: А.Ахо, Дж. Хопкрофт, Дж. Ульман [1], Э.Рейнгольд, Ю.Нивергельт, Н.Део [55], В.К.Леонтьев [43], В.А. Емеличев, М.М.Ковалев, М.К.Кравцов [30], М.Гэри, Д.Джонсон [28], X. Пападимитриу, К.Стайглиц [53] и др.

 
© URSS 2016.

Информация о Продавце