Глава 4. Генерация комбинаторных объектов

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

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

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

4.1. Поиск с возвращением

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

Идею поиска с возвращением легче всего понять в связи с задачей прохода через лабиринт: цель — попасть из некоторого заданного квадрата в другой заданный квадрат путем

(см. скан)

последовательного перемещения по квадратам. Трудность состоит в том, что существующие преграды запрещают некоторые перемещения. Один из способов прохода через лабиринт — это двигаться из начального квадрата в соответствии с двумя правилами:

• в каждом квадрате выбирать еще не исследованный путь;

• если из исследуемого в данный момент квадрата не ведут неисследованные пути, то нужно вернуться на один квадрат назад по последнему пройденному пути, по которому пришли в данный квадрат.

Первое правило говорит о том, как расширить исследуемый путь, если это возможно, а второе правило — о том, как выходить из тупика. В этом и состоит сущность поиска с возвращением: продолжать расширение исследуемого решения до тех пор, пока это возможно, и когда решение нельзя расширить, возвращаться по нему и пытаться сделать другой выбор на самом близком шаге, где имеется такая возможность.

Общий алгоритм

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

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

Алгоритм 4.1. Общий алгоритм поиска с возвращениями

(см. скан)

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