11.2.3. Улучшенный перебор

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

ЗАМЕЧАНИЕ

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

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

Идея: начинаем с пустого множества и пополняем его вершинами с сохранением независимости (пока возможно).

Пусть S_k — уже полученное множество из k вершин, Q_k — множество вершин, которое можно добавить к S_k, то есть S_k П T(Qk) = 0. Среди вершин Q_k будем различать те, которые уже использовались для расширения S_k (обозначим Q_k), и те, которые еще не использовались (Q_k). Тогда общая схема нерекурсивной реализации поиска с возвратами будет состоять из следующих шагов.

Шаг вперед от k к k + 1 состоит в выборе вершины х 6 Q_k:

Sk+i = S_k U {х},

Шаг назад от fc + 1 к fc:

Sk — S_k+i - {х},

Ql = Qt- to,

Qk = Qk ^u (4-

Если S_k — максимальное, то Q% = 0. Если Q^ Ф 0, то S_k было расширено раньше и не является максимальным. Таким образом, проверка максимальности задается следующим условием: Q+ = Q~ = 0.

Перебор можно улучшить, если заметить следующее.

Пусть х € Q^" и r(x)r\Q~£ = 0. Эту вершину х никогда не удалить из Q^, так как из Q~ удаляются только вершины, смежные с Q~£. Таким образом, существова­ние х, такого что х € Q_k и Г(х) n Q% = 0, является достаточным условием для возвращения. Кроме того, k ^ р — I.