11.2.2. Поиск с возвратами

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

Вход: граф G(V, E).

Выход: наибольшее независимое множество X. т : = 0 { наилучшее известное значение Д> } for Y е 2^V do if Г е£&|У| >mthen

m := |У|; X: = Y { наилучшее известное значение X } end if end for

ЗАМЕЧАНИЕ

Для выполнения этого алгоритма потребуется <9(2^Р) шагов.

ОТСТУПЛЕНИЕ

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

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

ЗАМЕЧАНИЕ —

Иногда употребляется термин бэктрекинг (от английского названия этого метода -backtracking).

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

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

Алгоритм 11.1. Поиск с возвратами

Вход: граф G(V, E).

Выход: наибольшее независимое множество X.

т: = О { наилучшее известное значение /Зо }

ВТ(0, V) { вызов рекурсивной процедуры ВТ }

Основная работа выполняется рекурсивной процедурой ВТ.

Вход: S — текущее независимое множество вершин, Т — оставшиеся вершины графа. Выход: изменение глобальной переменной X, если текущее множество не может быть расширено (является максимальным). е: = false { признак расширяемости множества } for v 6 V do if S U {v} € £ then

e : = true { множество можно расширить } BT(S U {г;}, Т \ Г*(г>)) { пробуем добавить v } end if end for if e then

if \S\ > т then

X := S;m := \S\ { наибольшее независимое множество } end if end if

обоснование

По построению вершина v добавляется в множество 5 только при сохранении независимости расширенного множества. В алгоритме это обстоятельство указа­но в форме условия 5 U {v} e £. Проверить сохранение условия независимости нетрудно, например, с помощью следующего цикла.

/: = true { множество 5 независимое } for и £ S do

if (и, v) e E then /: = false; exit for { множество 5 U {v} зависимое }

end if end for

Этот цикл не включен в явном виде в рекурсивную процедуру ВТ, чтобы не загромождать основной текст и не затуманивать основную идею поиска с воз вратами. Таким образом, множество S, а следовательно, и множество X -зависимые. В тот момент, когда множество S нельзя расширить (e = false), оно максимально по определению. Переменная т глобальна, поэтому среди всех мак­симальных независимых множеств в конце работы алгоритма X является наи большим независимым множеством вершин.