Дискретные экстремальные задачи

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

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

1. Задача поиска минимального остовного дерева. Одной из возможных содержательных интерпретаций будет, например, прокладка сети дорог минимальной стоимости, связывающих n населенных пунктов, что на математическом языке означает поиск минимального остова рёберно-взвешенного графа.
2. Задача об упаковке в контейнеры конечного множества из предметов с заданными весами с использованием наименьшего возможного числа одинаковых контейнеров с заданным ограничением по общему весу всех предметов, помещенных в один контейнер.
3. Задача на покрытие носит весьма универсальный характер и допускает множество различных содержательных интерпретаций при распознавании образов, при контроле исправности и диагностике неисправностей управляющих систем, при минимизации формул алгебры логики и во многих других случаях. Покрытием множества называется любая система подмножеств множества Q, объединение которых равно Q; подмножества считаются при этом элементами покрытия . При заданной системе подмножеств задача нахождения минимального покрытия или просто, как говорят, задача на покрытие заключается в нахождении покрытия, являющегося частью заданного покрытия , содержащей наименьшее число элементов покрытия (т.е. подмножеств из числа ).

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

При решении дискретных экстремальных задач обычно бывает нетрудно построить некоторые достаточно простые (в содержательном смысле) алгоритмы переборного характера для нахождения нужного решения. Скажем, при решении задачи на покрытие на первом шаге проверяется, образует ли покрытие одно из подмножеств , т.е. существует ли одночленное покрытие? Если да, то соответствующее подмножество и дает решение. Если нет, то перебираются всевозможные двухэлементные множества , и проверяется, является ли покрытием хотя бы одно из этих множеств, и т.д. Ясно, что такой способ позволит найти минимальное покрытие, но его практическое использование при достаточно больших значениях (от и более) параметров m и n может оказаться невозможным из-за неприемлемо большой трудоемкости поиска требуемого решения.

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

Теория сложности алгоритмов связана в основном с изучением времени или числа элементарных операций, необходимых для решения задачи. Исходные данные каждой конкретной или, как говорят, индивидуальной задачи представляют закодированными, например, в виде двоичных наборов (из нулей и единиц); такие наборы определяют длину описания задачи в битах или размер входа этой задачи. Например, для задачи на покрытие размер входа легко оценить по матрице, в которой строки отвечают элементам из Q, столбцы – подмножествам , и на пересечении i-й строки и j-го столбца ставится 1, если , или 0, если ; размер входа при этом получается порядка mn.

Алгоритм решает задачу с полиномиальной сложностью (или за полиномиальное время) и называется полиномиальным, если можно указать константы k и r такие, что при решении конкретной задачи с размером входа x этот алгоритм потребует выполнения не более чем элементарных операций (или условных единиц времени). Градиентный алгоритм решения задачи поиска минимального остова, как нетрудно заметить, является полиномиальным.

Из соображений удобства математическая теория дискретных задач (в том числе и экстремальных, а они на практике составляют подавляющее большинство) строится для задач распознавания свойств, которые, по определению, могут иметь только два ответа: «да» или «нет». Например, задачу поиска минимального остова можно видоизменить так: верно ли, что для заданного взвешенного графа и заданного положительного числа l существует остов с суммой весов составляющих его рёбер не превосходящей l?

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

Значительно более обширный класс NP составляют такие дискретные задачи распознавания, для которых существует полиномиальный алгоритм обоснования ответа «да» в тех случаях, когда именно такой ответ имеет место. Скажем, условием принадлежности задачи на покрытие классу NP является существование алгоритма A и констант k и r таких, что для любой конкретной задачи на покрытие с размером входа x и с ответом «да» можно указать подходящее подмножество элементов покрытия, для которого алгоритм A за время, не превосходящее , установит, что это подмножество является покрытием, содержащим не более чем l элементов, т.е. подмножеств (число l указывается в постановке задачи).

Вопрос о соотношении между классами P и NP (в частности вопрос о том, совпадают или не совпадают эти классы) является открытым и составляет одну из крупнейших проблем современной математики. Таким образом, открытым является и вопрос о существовании алгоритмов, позволяющих решать многие важные в прикладном отношении дискретные экстремальные задачи за полиномиальное время. В связи с этим актуальным становится уже просто сравнение различных дискретных экстремальных задач по трудности их решения. В основу такого сравнения положена известная в математической логике и в теории алгоритмов с первой половины прошлого века идея сводимости задач. Считается, что задача сводится к задаче , если алгоритм решения задачи можно использовать и для решения задачи . Например, полиномиальная сводимость задачи об упаковке в контейнеры к задаче на покрытие означает, что существует алгоритм A и константы k и r такие, что по любой конкретной задаче об упаковке алгоритм A за время, не превосходящее , где – размер входа задачи , строит задачу на покрытие так, что ответы в задачах и совпадают. Сводимость позволяет получать сравнительные оценки (качественного характера) для сложности решения дискретных задач типа: «если задача Z сводится к задаче , то не проще, чем задача Z».

Дискретная задача Z из класса NP считается NP-полной, если к ней полиномиально сводится любая задача из класса NP. В настоящее время известен уже весьма обширный список NP-полных задач; в этом списке оказались, в частности, и задачи об упаковке в контейнеры и на покрытие.

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