Метод решета

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

Методы решета, прежде всего, используются в теоретико-числовых вычислениях. Например, одним из известных методов отыскания простых чисел является «решето Эратосфена». Это решето перечисляет составные (не простые) числа между N и N² для некоторого N.

Просеивание начинается с выписывания всех чисел от N до N², и затем из них поэтапно удаляются составные числа. Сначала удаляются все числа, кратные двум, затем – все, кратные трем, и т.д. Процесс прекращается после просеивания для наибольшего простого числа меньшего N.

Пример 5.

1,2,3 – простые.

N=4.

4,5,6,7.8,9,10,11,12,13,14,15,16 – интервал от N=4 до N²=16.

4,5,6,7.8,9,10,11,12,13,14,15,16 – исключили кратные 2.

4,5,6,7.8,9,10,11,12,13,14,15,16 – исключили кратные 3.

5,7,11,13 – простые. 

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

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

В задаче из примера 1 исходным множеством S (множеством из которого формируются траектории) является совокупность из n камней, а траекторией будет его разбиение на два подмножества S₁ и S₂, таких, что S₁S₂=S и S₁S₂=. Если {a₁,a₂,…,a_n} - массы камней, то - функционал, а - оптимальное значение функционала. Перебор траекторий осуществляется с помощью систематического порождения подмножеств S₁, множества S. Всего траекторий 2ⁿ.

В задаче из примера 2, в качестве исходного множества выступают все возможные пары городов. Траекторией будет совокупность этих пар, образующая маршрут из начального города, удовлетворяющий всем перечисленным требованиям. Функционалом является сумма стоимостей проезда между парами городов, образующих траекторию. Оптимальным решением будет траектория с минимальным значением функционала. Дня организации полного перебора траекторий в данной задаче необходимо порождение всех перестановок из n-1 элементов. Всякая такая перестановка Р=(р₁,р₂,…,р_n-1) определяет допустимый маршрут:

"начальная вершина"р₁р₂…р_n-1"начальная вершина".

Всего траекторий (n-1)!.

Задача из примера 3 также сводится к порождению всех перестановок n-элементного множества.

3. Некоторые вопросы теории сложности

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

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

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

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

Как следует из таблицы 4, например, при сложности 3ⁿ даже увеличение быстродействия ЭВМ в 1000 раз по сравнению с имеющимися в настоящее время позволяет увеличить размерность задачи, которая доступна для расчета лишь на 6 или 7 единиц. А из таблицы 5 видно, что при той же сложности задача размерности 33 единицы будет решаться около трех веков. Вот почему необходимо искать пути уменьшения сложности. То есть применять эффективные алгоритмы для решения задачи. Однако, эффективные алгоритмы существуют не для всех задач. Причем, как будет рассмотрено ниже, среди задач, для которых пока нет эффективных алгоритмов, есть задачи, составляющие особый класс. Если будет найден эффективный алгоритм для решения хотя бы одной задачи из этого класса, то это будет означать, что эффективный алгоритм найден для всех задач этого класса.

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

Эвристическими называют алгоритмы, основанные на неформальных соображениях. Корректность таких алгоритмов теоретически не обоснована.

Таблица 4

Слож-ность	Размеры наибольшей задачи, разрешимой за 1 час.
	На современных ЭВМ	На ЭВМ в 100 раз более быстрых	На ЭВМ в 1000 раз более быстрых
N	N1	100 N1	1000 N1
n^2	N2	10 N2	31.6 N2
n^3	N3	4.64 N3	10 N3
n^5	N4	2.5 N4	3.98 N4
2^n	N5	6.64+N5	9.97+N5
3^n	N6	4.19+N6	6.29+N6

Таблица 5

Сложность	Время решения задачи
	1 с.	10 ^2 с. 1.7 мин.	10 ^4 с. 2.7 ч.	10^6 с. 12 сут.	10^8 с. 3 года.	10 ^10 с. 3 века.
1000n	10^3	10^5	10^7	10^9	10^11	10^13
1000nlog n	140	7.710^3	5.210^5	3.910^7	3.110^9	2.610^11
100n^2	10^2	10^3	10^4	10^5	10^6	10^7
10n^3	46	2.110^2	10^3	4.610^3	2.110^4	10^5
2^n^/3	59	79	99	119	139	159
2^n	19	26	33	39	46	53
3^n	12	16	20	25	29	33

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

Понятие сложности решения задачи с трудом поддается математическому анализу. При проведении такого анализа нужно иметь формальное определение задачи и способа получения решения.

Американский математик С. Кук предложил под решением задачи понимать распознавание формального языка L в алфавите {0,1}

Формальным языком в алфавите  называется некоторое подмножество множества всех цепочек (слов) в алфавите .

Множество всех цепочек (слов) в алфавите  формально определяется следующим образом:

1)  - цепочка в , где  - пустая цепочка, т.е. цепочка, не содержащая ни одного символа;

2) если  – цепочка в  и a, то a – цепочка в ;

3)  - цепочка в  тогда и только тогда, когда она получена по правилам 1 или 2.

Под распознаванием языка понимается ответ на вопрос: принадлежит ли произвольная цепочка заданному формальному языку.

Пример 6. Пусть x – натуральное число. Необходимо определить делится ли x на 4.

Язык L, связанный с этой задачей, это множество всех натуральных чисел, записанных в двоичной системе счисления, делящихся на 4. Распознавание принадлежности слова x языку L в данном случае простое и сводится к просмотру двух последних букв слова x. Если они –нули, то xL; если нет, то xL. 

Пример 7. Пусть задан граф G и натуральное число k. Произвольная функция вида f:VG{1,2,...,k} называется вершинной k-раскраской графа G (раскраской графа в k цветов). Если при этом выполняется условие f(u)f(v) для любых смежных вершин графа G, то раскраска называется правильной. Необходимо определить, можно ли построить правильную k-раскраску графа G.

Язык L, связанный с данной задачей, это множество всех матриц смежности графов, для которых существует правильная k-раскраска (матрицу смежности размера nn можно представить в виде двоичного слова длины n²). Теперь задачу о раскраске графа в k цветов можно сформулировать так: определить принадлежит матрица смежности исходного графа G языку L или нет. 

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

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

Пример 7. (продолжение). Всего способов раскраски n-вершинного графа в k цветов существует kⁿ. Требуется узнать, является ли хотя бы одна из таких раскрасок правильной.

Для проверки правильности раскраски графа достаточно просмотреть все его ребра. Если вершины каждого ребра имеют разный цвет, то раскраска является правильной, в противном случае – неправильной. Если граф задан матрицей смежности, то для такой проверки потребуется порядка n² действий (задача класса P).

Если представить себе возможность проведения одновременной проверки правильности всех возможных раскрасок, то вся процедура проверки возможности раскраски графа в k цветов также потребует выполнения порядка n² действий. 

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

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

Следующее важное понятие связано со сводимостью задач.

Пусть L₁,L₂R – некоторые два языка. Язык L₁ сводится к языку L₂, если существует функция f:RR такая, что слово xL₁ тогда и только тогда, когда f(x)L₂. Если для вычисления функции f существует вычисляющая ее программа полиномиальной сложности, то сводимость называется полиномиальной.

Основным результатом, полученным С. Куком, является установление того факта, что всякую задачу из класса NP можно полиномиально свести к некоторой одной специальной задаче из этого класса.

Такая задача называется проблемой выполнимости и формулируется следующим образом: найти набор значений переменных (x₁,x₂,...,x_n), обращающих функцию f(x₁,x₂,...,x_n) в единице, если f задана в конъюнктивной нормальной форме (КНФ).

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

Пример 8. Подмножество V вершин графа G называется кликой, если любые две входящие в него вершины смежны. Определить существует ли в графе клика мощности k.

Проблема выполнимости полиномиально сводится к задаче о клике мощности k. Проведем сводимость на частном примере.

Рассмотрим граф G, вершинами которого являются пары, перечисляющие переменные, входящие в функцию

.

Перечисление идет следующим образом: переменной x_r, входящей в i-ю скобку и занимающей в ней j-е место, сопоставляется пара (i,j). Таким образом, получим следующее соответствие:

Две вершины графа G являются смежными, если для соответствующих им пар (i,j) и (k,l) выполняются следующие условия:

1) ik;

2) , где под ипонимаются переменные, соответствующие парам(i,j) и (k,l).

Граф G представлен на рис 4.

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

Таким образом, задача о клике мощности k является NP-полной.

Пример 9. Антиподом понятия клики является понятие независимого множества вершин. Подмножество V вершин графа G называется независимым, если любые две входящие в него вершины не смежны. Определить существует ли в графе независимое множество вершин мощности k.

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

Пример графа G и его дополнения представлен на рис. 5.

Нетрудно заметить, что при переходе от графа G к его дополнению каждая клика вG переходит в независимое множество в . Переход от графаG к графу можно осуществить с помощью алгоритма, время работы которого ограничено полиномом от числа вершин графаG (предложите такой алгоритм). Таким образом задача о клике мощности k полиномиально сводится к задаче о независимом множестве мощности k, а как было показано в предыдущем примере, проблема выполнимости полиномиально сводится к задаче о клике мощности k. Отсюда следует, что проблема выполнимости также полиномиально сводится к задаче о независимом множестве мощности k. Таким образом, задача о независимом множестве мощности k является NP-полной.

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

Пример 10. Задача поиска клики наибольшей мощности является NP-трудной. Решение данной задачи может быть получено путем многократного решения задачи поиска клики мощности k. 

Пример 11. Задача поиска наибольшего независимого множества является NP-трудной. Решение данной задачи может быть получено путем многократного решения задачи поиска независимого множества мощности k.

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

Интересен вопрос о том, какие свойства NP-полных задач затрудняют построение эффективных алгоритмов их решения и чем эти свойства отличают NP-полные задачи от задач из класса P. Очевидно, что PNP, вопрос же о справедливости равенства P=NP остается одним из важнейших вопросов в современной математике.