13.3 Алгоритм нумерации вариантов

Далее, используя значения функции для каждого узла, можно построить алгоритм нумерации вариантов. Этот алгоритм по номеру из данного дерева по- лучает необходимый вариант подстановки. Предварительно зададим две функции нумерации, которые по номеру варианта для рассматриваемого узла вычисляют номера вариантов для сыновей. Для И-узла будет следующая функция:


где z - рассматриваемый узел дерева;

	- множество сыновей узла z;
	- количество вариантов в поддереве с узлом

ПРИМЕЧАНИЕ. При выполнении операции деления используются алгоритмы целочисленной арифметики. Рассмотрим пример использования этой функции. Пусть задан И-узел z, у которого имеется три сына ( S1, S2, S3 ), и известно количество вариантов w(z) = 6, w(S1) = 1, w(S2) = 3, w(S3) = 2.

Тогда можно записать следующую таблицу значений номеров вариантов для сыновей в зависимости от номера варианта узла z:

Таблица 13.1: Таблица значений номеров вариантов для сыновей

Для ИЛИ-узла необходимо определить не только номер варианта, но и номер соответствующего сына. Для этого запишем следующую функцию:
где z - рассматриваемый узел дерева;

	- множество сыновей узла z;
	- количество вариантов в поддереве с узлом

Рассмотрим пример. Пусть задан ИЛИ-узел с 3 сыновьями и w(z) = 9, w(S1) = 3, w(S2) = 2, w(S3) = 4.
w(z) = w(S1) + w(S2) + w(S3)

Тогда можно записать следующую таблицу значений для номера сына и номера варианта в зависимости от значения варианта узла z:

Таблица 13.1: Таблица значений для номера сына

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

1. Первоначально производится подсчет количества вариантов для каждого узла дерева.
2. В вариант записывается корень дерева, и он становится текущим узлом.
3. Определяется тип текущего узла. Если это И-узел, то переход на шаг 4, иначе переход на шаг 5.
4. Все сыновья рассматриваемого узла записываются в данный вариант подстановки и для них соответственно с функцией для И-узлов определяются номера вариантов для соответствующих поддеревьев.
5. Если это ИЛИ-узел, то определяется единственный сын и номер варианта для соответствующего поддерева.
6. Происходит переход на рассмотрение следующего узла из списка включенных в данный вариант подстановок.
7. Процесс определения варианта подстановок будет происходить до тех пор, пока не будут достигнуты листья для всех рассматриваемых узлов варианта подстановок.