ВУЗ:
Составители:
Рубрика:
75
декомпозиционных формулах) в 4,22 … 6,00 раз в зависимости от числа
узлов подсхем.
Таблица 2.5.2. Сравнение числа равновесных и неравновесных ДВ
n+1 2 3 4 5 6 7 8 9 10
1n
2 6 20 70 252 924 3432 12870
48620
1n
1 4 15 56 210 792 3003 11440
43758
%100
1
1
n
n
50,0
67,0
75,0
80,0
83,0
86,0
87,5
89,0
90,0
Предложенные неравновесные ДВ в сочетании с равновесными ДВ
позволяют использовать единое сечение по узлам исходной схемы для
нахождения как числителя, так и знаменателя. Это сокращает число
операций по сравнению с традиционным подходом, то есть при
раздельном нахождении числителя и знаменателя, почти в два раза,
поскольку затраты на получение первого сечения преобладают в затратах
на формирование СПФ [75]. Для иллюстрации комбинаторного характера
алгоритма поиска сечения рассмотрим (n+1)-узловое сечение в схеме с q
узлами. В этом случае требуется рассмотреть
1n
q
C сочетаний узлов на
предмет существования половинного (близкого к половинному) деления
схемы на две подсхемы. В табл. 2.5.4 показано для случая n+1=3, что
затраты на поиск следующего (после первоначального) деления схемы на
подсхемы в несколько раз меньше. Поэтому для сложных схем доля
экономии операций на поиск первоначального сечения является
определяющей в затратах на поиск всех других сечений, необходимых для
формирования СПФ.
Таблица 2.5.3. Сравнение числа слагаемых в декомпозиционных формулах
для числителя, полученных на основе равновесных и неравновесных ДВ
n+1 2 3 4 5 6 7 8 9 10
%100
1
2
n
n
6,00
5,00
4,70
4,50
4,40
4,33
4,29
4,25
4,22
Таблица 2.5.4. Сокращение числа операций при использовании общего трехузлового
сечения для нахождения числителя и знаменателя СПФ
q 10 20 30 40 50 60 70 80 90
3
q
C
120 1140 4060 9880 19600
34220
57740
82160
117480
Страницы
- « первая
- ‹ предыдущая
- …
- 73
- 74
- 75
- 76
- 77
- …
- следующая ›
- последняя »
