Задача. Найти многочлен попаданий для доски 3 х 3 с запрещенными позициями на рис. 3.12. Запрещенные позиции отмечены темным цветом.

Решение. Найдем ладейный многочлен доски запрещенных позиций, которая состоит из двух неза- Рис. 3.12 висимых досок. Тогда

Щх) = Д® • ДДВ) = (1 + Х)(1 + Зх + Х2) = 1 + 4х + 4.Г + х3.

Значит

Щ =R((t-\)z~l)n\=(\+A{t-\)z~l+4[(t-\)z~ l]2+[(t- 1)е 1]3)3! = = 1-3! + 4(t- 1)б 13! + 4[(f- 1)е-1]2 3! + [(t- l)s~lf 3! = = 3! +4(f- 1)2! i 4(f- l)2 1! + (t- 1)30! . Итак, E(t) = l + 3t+t2 + t3.

Анализ коэффициентов ДО при t показывает, что число перестановок, в которых ладьи не занимают запрещенных клеток, равно 1 (коэффициент при Г); перестановок с одной ладьей на запрещенных позициях — 3 (коэффициент при г1); перестановок с двумя ладьями на запрещенных позициях — 1 (коэффициент при t ); перестановок с тремя ладьями на запрещенных позициях -1 (коэффициент при t ).

3—2697

- Глава -

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

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

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

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

Использование компьютера для ответа на такие вопросы, как «сколько существует«перечислите все возмож-

или «есть лиобычно требует исчерпывающего

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

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

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

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

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

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

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

В самом общем случае полагаем, что решение задачи состоит из вектора (аь а2, а3,„.) конечной, но неопределенной длины, удовлетворяющего некоторым ограничениям. Каждое Д., где А, — конечное линейно упорядоченное множество. Таким образом, при исчерпывающем поиске должны рассматриваться элементымножества(яа,, а3,,.., а,) е Л, хА2х...х.4(, для = О, 1, в качестве возможных решений. В качестве исходного частичного решения примем пустой вектор () и на основании имеющихся ограничений выясним, какие элементы изАу являются кандидатами в а у. Обозначим это подмножество кандидатов через SyczAy. В результате имеем частичное решение В общем случае для расширения частичного решения отдо

ak y, ak) кандидаты на роль выбираются из сАк. Если частичное решениене представляет возможности для выбора элемента ак, то Sk 0: возвращаемся и выбираем новый элемент Если новый элемент выбрать нельзя, возвращаемся еще дальше и выбираем новый элемент ак 2 и т.д. Этот процесс удобно представлять в терминах прохождения дерева поиска в