The algorithms and enumerative characteristics tree and/or ..pdf Генераторы информационных объектов становятся необхо-димым элементом сложных программных систем [1]. Генерато-ры сценариев, карт местности, изображений, тестовых заданий ивопросов - вот неполный перечень таких программ. Математи-ческой основой построения таких генераторов является, какправило, модель предметной области и датчик случайных чисел.Однако исследования в области перечислительной комбинато-рики показали, что для комбинаторных объектов можно постро-ить алгоритмы генерации, которые по заданному номеру объек-та строит сам объект. Примерами таких алгоритмов являютсяалгоритмы генерации перестановок и сочетаний [2, 3] .Ниже предлагается рассмотреть подход к построению такихалгоритмов, основанных на использовании деревьев И/ИЛИ.Рассматриваются перечислительные свойства и алгоритмы.ДЕРЕВЬЯ И/ИЛИДеревья И/ИЛИ, понятие которого впервые былопредложено Слейглом [4], являются важным инструмен-том исследования и создания систем искусственного ин-теллекта [5−7]. Дерево И-ИЛИ содержит два типа узла: И-узел и ИЛИ-узел. В терминах решения задачи И-узел оз-начает, что решение задачи разбивается на подзадачи.Решение всей задачи зависит от решения всех подзадач.ИЛИ-узел означает, что задача может быть решена не-сколькими методами. Соответственно для решения зада-чи, представленного ИЛИ-узлом, необходимо использо-вать какой-то один метод. Существуют и другие интер-претации узлов дерева И/ИЛИ, например, И-узел описы-вает структуру некоторой системы, подсистемы, блока ит.д., а ИЛИ-узел − некоторое множество типов структур.Вариантом дерева И/ИЛИ назовем поддерево, котороеполучается из заданного путем отсечения выходных дугкроме одной у всех ИЛИ-узлов. Вариант в терминах реше-ния задачи задает одно из возможных решений задачи.Алгоритм 1 получения варианта V дерева И/ИЛИ Dследующий:1. Корнем варианта становится корень (root) дереваD и Stack ⎯⎯p⎯ushroot.2. Если стек пуст, завершаем работу алгоритма. Ина-че вытаскиваем узел из стека и делаем его текущимStack ⎯⎯p⎯ull z.3. Если рассматриваемый узел z − ИЛИ-узел, то ввариант V заносится один sj из сыновей узла z.4. Если рассматриваемый узел z − И-узел, то все егосыновья sj заносятся в вариант.5. Если рассматриваемый узел z − лист, то происхо-дит переход на шаг 2.Все листья варианта V являются подмножествоммножества листьев дерева И/ИЛИ D. Очевидно, чтовариантов в дереве И/ИЛИ может быть некоторое мно-жество. В связи с этим возникает задача подсчета ко-личества вариантов в дереве D.Рассмотрим алгоритм подсчета вариантов решенийв дереве И/ИЛИ. Для этого запишем следующую ре-курсивную функцию:( )( )( )⎪ ⎪ ⎪⎩⎪ ⎪ ⎪⎨⎧−ƒƒ = ƒƒ==1для листа,для И узла,для ИЛИ- у зла,11nizinizissz (1)где z − рассматриваемый узел дерева; { } zsi − множест-во сыновей узла z; n − количество сыновей; ƒ(z) − ко-личество вариантов для узла z.Подсчитав значение функции для корня дерева,можно получить общее число вариантов решений, име-ющихся в данном дереве. При этом будет подсчитаноколичество вариантов для каждого узла всего дерева.Пример подсчета вариантов показан на рис. 1.Рис.1. Пример подсчета вариантов в дереве И/ИЛИИспользуя значения функции ƒ(z) для каждого узлаz, можно построить алгоритм нумерации вариантов.Этот алгоритм по номеру из данного дерева получаетнеобходимый вариант поддерева. Предварительно за-дадим две функции нумерации, которые по номеруварианта для рассматриваемого узла вычисляют номе-ра вариантов для сыновей. Для И-узла будет следую-щая функция:⎪ ⎪⎩⎪ ⎪⎨⎧ƒ =ƒ >ƒ = ƒ−=( ) mod ( ) , 1.mod ( ) , 1,( )( )( )11I z s is isI zI szA izi ijzjAzA i (2)Для ИЛИ-узла необходимо определить не только но-мер варианта, но и номер соответствующего сына. Дляэтого запишем следующее уравнение относительно k:( )( )( ) ( ) ⎪⎩⎪⎨⎧> ≥ ⎥⎦⎤⎢⎣⎡− ƒ< ƒ == ƒ=min ( ) при 0, 1.( ) при ( ) , 1,0100 00 I z s I s kI z I z s kI s zkkjzjzkzk (3)Пусть дано И/ИЛИ дерево D, где { }nsi i 1 = − множест-во узлов, и некоторое число L, 0 ≤ L < ƒ (sroot), где sroot −корень дерева.Тогда алгоритм 2 построения варианта поддеревапо заданному номеру L будет следующий.1) Первоначально производится подсчет количествавариантов для каждого узла дерева ƒ(z), z{s}.2) Корень дерева записывается в вариант и заносит-ся в список list.add(sroot, L).3) Из списка вынимается пара =list.pull(). Ес-ли список пуст, то завершить работу.4) Определяется тип текущего узла. Если это И-узел,то переход на шаг 5, иначе переход на шаг 6.5) Все сыновья { } 1mjzjs = рассматриваемого узла z за-писываются в данный вариант, добавляются в список идля каждого узла вычисляется ( z ) ,L si используя вы-ражение (2).6) Если это ИЛИ-узел, то определяется единствен-ный сын z ,sk заносится в список и определяется ( z ) ,L skиспользуя выражение (3).7) Переход на шаг 3.На рис. 2 показаны все варианты для дерева И/ИЛИ,приведенного на рис.1, получаемые описанным алго-ритмом генерации варианта поддерева по заданномуномеру.Рис. 2. Все варианты для примера И/ИЛИ дереваПЕРЕЧИСЛИТЕЛЬНЫЕ СВОЙСТВАДЕРЕВЬЕВ И/ИЛИРассмотрим теперь перечислительные свойства де-ревьев И/ИЛИ.Свойство 1. Пусть дано два дерева И/ИЛИ d1 и d2.Известно, что деревья описывают два разных классаодного и того же объекта, тогда можно создать новоедерево И/ИЛИ Z, корнем которого будет ИЛИ-узел, асыновьями − корни деревьев d1, d2 и ƒ(Z) = ƒ(d1) + ƒ(d2).Свойство 2. Пусть дано два дерева И/ИЛИ d1 и d2. Из-вестно, что данные деревья описывают два разных объекта,из которых строится данный объект, тогда можно создатьновое дерево И/ИЛИ Z, корнем которого будет И-узел, асыновьями − корни деревьев d1, d2 и ƒ(Z) = ƒ(d1) + ƒ(d2).Свойство 3. Суть алгоритмов нумерации не изме-нится, если в выражении (1) вместо единицы для листа,записать константу, зависящую от конкретного листадерева. Тогда данное выражение будет следующее:( )( )⎪ ⎪ ⎪ ⎩ ⎪ ⎪ ⎪⎨⎧ƒƒƒ = ƒƒ==для - го листа,для И - узла,для ИЛИ - узла,( )11С ksszknizinizi(4)где Ck − константа k-го листа дерева.Эта константа может быть записана ранее или по-лучена некоторым алгоритмом, который связан с k-млистом дерева.Можно перечислить следующие классы вариантов:минимальные; максимальные варианты; варианты с ниж-ней границей числа листьев; варианты с верхней гра-ницей числа листьев; варианты с весами на листьях; смаксимальной глубиной; варианты с минимальной глу-биной.Вариант дерева И/ИЛИ будет максимальным, если унего максимальное число листьев. Подсчет числа лис-тьев у максимального варианта можно выполнить последующей рекурсивной функции:( )( )⎪ ⎪⎩⎪ ⎪⎨⎧ƒƒ= ƒ ƒ=1 для листа.для И - узла,max для ИЛИ - узла,( )1nizizissz (5)Вариант будем называть минимальным, если у негоминимальное число листьев.Подсчет числа листьев у минимального вариантаможно выполнить по следующей рекурсивной функции:( )( )⎪ ⎪⎩⎪ ⎪⎨⎧= ƒ=1 для листадля И - узла,min для ИЛИ - узла,( )1niziziv sv sv z (6)Алгоритм 3 нахождения варианта с максимальнымчислом листьев.Дано: дерево И/ИЛИ D и root− корень этого дерева.Необходимо: найти вариант V с максимальным чис-лом листьев.1. Находим значение функции ƒ(root) (выражение (5).2. Записываем корень дерева в стек Stack ⎯p⎯ush⎯ rootи создаем корень дерева варианта V.3. Если стек пуст, то завершаем работу алгоритма.Иначе вытаскиваем узел из стека и делаем его текущимStack ⎯⎯p⎯ull z.4. Если z И-узел, то переходим на шаг 5. Если z −ИЛИ-узел, переходим на шаг 6. Если это лист, то пере-ходим на шаг 3.5. Все сыновья узла z записываются в стекiStack ⎯p⎯ush⎯ s и в вариант V.6. Определяем, какой из сыновей Si узла z войдет ввариант, для этого используем значения ƒ(z) и ƒ(si)for (i=1, n)if ( ) ƒ(z) = ƒ si then k = i break endifЗаносим найденный узел в вариант и в стекk .Stack ⎯p⎯ush⎯ sОчевидно, что описанный выше алгоритм можно мо-дифицировать для нахождения варианта с минимальнымчислом листьев. Для этого необходимо заменить функ-цию ƒ(s) при описании шагов 1 и 6 на функцию v(s).Приведенный выше алгоритм находит один вари-ант. Однако таких вариантов может быть много, всезависит от значений функции ƒ(s) (или v(s)) при опре-делении сына ИЛИ-узла. Максимальных вариантов бу-дет два, если при выполнении шага 6 будет выполненосоотношение ƒ(z) = ƒ(s j )= ƒ(sk ).Общее число вариантов с максимальным количест-вом листьев будет равно сумме всех совпадений значе-ний ƒ(z) = ƒ(s j ).Можно предложить следующий алгоритм 4 вычис-ления количества максимальных вариантов:1. Находим значение функции ƒ(root).2. Записываем корень дерева в стек Stack ⎯p⎯ush⎯ rootvar = 1.3. Если стек пуст, то завершаем работу алгоритма.Иначе вытаскиваем узел из стека и делаем его текущимStack ⎯⎯p⎯ull z.4. Если z − И-узел, то переходим на шаг 5. Если zИЛИ-узел, переходим на шаг 6. Если это лист, то пере-ходим на шаг 3.5. Все сыновья узла z записываются в стек{ } . 1nk kStack push s = ⎯⎯⎯6. for (i = 1, n)if ( ) ƒ(z) = ƒ s j then k = k+1 iStack ⎯p⎯ush⎯ s endifendforvar = var+ k −1Для нахождения всех минимальных вариантов не-обходимо модифицировать алгоритм 4. Для это на шаге6 подсчет максимальной глубины варианта в деревеИ/ИЛИ можно вычислить по следующей формуле:( )⎩ ⎨ ⎧ƒ +ƒ =1 для листа.(z) max si 1для узла, (7)Как видно из выражения (7), максимальная глубинаварианта совпадает с глубиной дерева И/ИЛИ.Подсчет минимальной глубины

Скачать электронную версию публикации