Методы синтеза технических решений, страница 22

48

Здесь и в дальнейшем знаком | • | будем обозначать мощность множества. На основе формулы (4.18) можно построить алгоритм вычисления числа элементов множества rt-

Алгоритм вычисления мощности множества Ry.

1.  Приписать всем дугам, входящим в вершины из К, вес 1;
пометить все вершины из К.

2.  Найти непомеченную вершину х ЕЕ X такую, что все выхо­
дящие из нее дуги имеют некоторые веса.

3.  Если х — #i, то перейти к 7.

4.  Пометить вершину х\ если х е Х₂, то перейти к 6...

5.  Приписать входящей в х дуге вес,  равный произведению
весов всех дуг, выходящих из х\ перейти к 2.

6.  Приписать входящей в х дуге вес, равный сумме весов всех
дуг, выходящих из х\ перейти к 2.

7.  Если х_г ЕЕ ^i, то | Лт | есть  произведение весов всех дуг,

в   противном случае

выходящих из этих дуг.

8. Конец.*

Примеры.

1.  Т — одна   вершина   | /?т | — 1.

2.  Т — такое, что Х^ = X; тогда | Д_т

3.  Т — такое, что Х₂ = Х\ тогда | R^ \

4.  Пусть Т — равномерно растущее прадерево высоты h— 2 нг+1»
причем  количество  дуг,   исходящих  из  вершин  любого  яруса,
одинаково для всех ярусов и равно р. Пусть Х₂ есть множество
всех   вершин,    лежащих   на   четных    ярусах.    Тогда    нетруд-

но   показать,    что   | /?т | = £°S   ^гД^{е   а} = ^п/1 + У^ + (Р — 1) ^п и п — число всех вершин прадерева Т .

4.4. Алгоритм поиска рациональных комбинаций

Пусть имеется задача нахождения рациональных относитель­но А комбинаций из /?_т. Для нахождения множества /?_т (А) предлагается следующий алгоритм:

1.  Построить множество К.

2.  Построить множество  5Г.

3.  Если х_г ЕЕ X, то решений нет.  Конец.                                __

4.  Из прадерева Т удалить все подпрадеревья с корнями из Х\
результат — прадерево N с корнем х_г.

5.  Дт (А) = rn',  конец.

Этот алгоритм представляет собой алгоритм глобального поис­ка на множестве Л_т, а время его работы эквивалентно числу вер­шин прадерева Т, что на несколько порядков меньше мощности множества Ry. Для практической реализации алгоритма удобно использовать представление прадерева Т (X, U) в виде списковой структуры [58, 59].

50

Описание на естественном языке технического решения, соот­ветствующего найденной комбинации, легко построить, используя терминологический словарь Ф и отображение Р: X -> Ф.

4.5. Определение расстояния на множестве Л_т

Определение    расстояния   на   множестве   путей    прадерева     Т.

Обозначим через Е^ множество всех путей прадерева Т (X, СУ), идущих из корня х_г в висячие вершины. Пусть аир— произволь­ные пути из Еу Символами аир обозначим множества вершин прадерева Г, через которые проходят пути аир соответственно. Определим расстояние р (а, Р) как