13.2 Алгоритм подсчета вариантов

Рассмотрим алгоритм подсчета вариантов решений в дереве И/ИЛИ. Для этого запишем следующую рекурсивную функцию:

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

- множество сыновей узла z;

n - количество сыновей.

Подсчитав значение функции для корня дерева, можно получить общее чис- ло вариантов подстановок, имеющихся в данном дереве. При этом будет подсчитано количество вариантов подстановок для каждого узла всего д ерева. Пример под- счета вариантов показан на рис.12.3.

Рис.12.3 Пример подсчета вариантов в И/ИЛИ дереве