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

48


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

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

равен сумме весов

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

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

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

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

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

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

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

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

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

8. Конец.*

Примеры.

= 1. =   К .

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

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

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

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

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

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

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

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

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

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

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

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

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

50


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

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

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

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