Бондаренко В.А., Максименко А.Н. Геометрические конструкции и сложность в комбинаторной оптимизации

Оглавление

Предисловие

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

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

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

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

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