Файл: Алферова, З. В. Математическое обеспечение экономических расчетов с использованием теории графов.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 21.10.2024
Просмотров: 88
Скачиваний: 0
Затем осуществляется присоединение ряда подпутей из оди нарных круглых скобок. В процессе присоединения эти скобки сохраняются, а внутри скобок происходит присоединение по общим
правилам. Первым присоединяется |
равный подпуть |
П3 |
= СрОВ + |
|
-\-СрПрХПрПр. |
Непосредственно |
за Я 3 следуют |
два |
неравных |
подпути.
Так как предшествующий им равный подпуть заканчивается вершиной Пр, отличной от сравнения, то предполагается наличие дополнительной вершины сравнения. Это означает, что равный подпуть продляется на одну дугу, а начальные дуги неравных под путей соответствующим образом изменяются.
Таким образом, равный подпуть Я 3 будет иметь вид:
|
П3=СрОВ |
+ |
|
СрПрХПрПрХПрСр, |
|
|
|
|
|
|||||
а присоединяемые неравные пути |
|
|
|
|
|
|
|
|
||||||
|
|
ПрПрхПрВс |
|
и |
ПрВс'хВсВс |
|
|
|
|
|
||||
соответственно видоизменяются в пути следующего вида: |
|
|
|
|||||||||||
|
|
СрПрхПрВс |
|
и |
СрВсхВсВс, |
|
|
|
|
|
||||
Последним |
присоединяется |
равный |
подпуть Я 4 . Длина |
нерав |
||||||||||
ных подпутей больше |
нуля, |
поэтому |
Я 4 |
присоединяется |
|
без |
изме |
|||||||
нений. Результатом присоединения является логическая |
|
функция |
||||||||||||
вида: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Ф = ВСрХ |
|
(СрПхПСр |
|
+ СрСрХ |
(СрПхПСр |
+ |
СрСрХ |
|
||||||
(СрП |
|
хПСр |
+ |
|
|
|
СрПхПСр)))Х{СрПрХПрСр+\)Х |
|||||||
СрСр |
Х(СрСр |
+ СрС хССхССрХ{\ |
+ |
СрПрхПрСрХ |
||||||||||
СрСр)) |
X СрУх |
УСX |
ССрХ{СрСрX |
(СрС |
+ |
СрСрX |
|
|||||||
((СрПрXПрСр |
+ СрСрX |
СрПрXПрВсХВсСр) |
|
ХСрС |
+ |
|
||||||||
СрСрХСрС)) |
+СрСрХ |
(1 + (СрСрХ |
|
(1 + СрСрХ |
(1 |
+ |
|
|||||||
СрС) XСрПрXПрСр) |
|
хСрПрXПрВсхВсСр) |
XСрС)) |
|
х |
|||||||||
СДхДУхУУхУСхСДхДУХУПчХПчСрХ |
|
|
|
|
|
|
|
|
||||||
{СрОВ + СрПрXПрПрX.ПрСрX |
(СрПрXПрВс |
|
+ |
СрВсх |
||||||||||
|
|
|
ВсВс)ХВсВсХВсСр). |
|
|
|
|
|
|
|
||||
Подобным образом можно построить логическую функцию, ото бражающую присоединение любого числа алгоритмов. Процесс присоединения алгоритмов может быть выполнен механизирован ным путем после разработки соответствующего алгоритма.
Для механизированной реализации процесса синтеза алгорит
мов операции |
над графами целесообразно заменить операциями |
|||
над соответствующими матрицами смежности. |
|
|||
Выполняя |
синтез |
с применением |
матриц смежности, |
можно |
использовать |
тот же |
алгоритм, что |
и при использовании |
графов. |
Только теперь роль равных подпутей будут играть равные клетки матриц. В то же время, используя свойства матриц смежности,
можно несколько упростить алгоритм синтеза. Процесс синтеза
вэтом случае будет состоять из следующих этапов:
1.Построение матриц смежности, соответствующих графам ал горитмов.
2.Выполнение операции сложения этих матриц.
3.Корректировка итоговой матрицы с целью получения матри цы составного алгоритма.
Поскольку первые два этапа не требуют пояснений, остановим ся на последнем этапе.
Корректировка итоговой матрицы заключается в следующем. Среди элементов матрицы отыскиваются те, значения которых равны двум. (Если таких элементов нет, то алгоритмы не имеют общих частей.) Значение этих элементов заменяется единицей. После этого из матрицы выделяются строки, соответствующие операциям сравнения, и по каждой из них определяется сумма элементов. Если такой строки не найдется, то синтез алгоритмов закончен и полученная матрица есть матрица смежности графа, представляющего составной алгоритм. Если же найдется строка, сумма элементов которой больше двух, то к матрице добавляются две строки и два столбца, соответствующие дополнительным опе рациям сравнения при расширении графа. Значение элементов в этих строках определяется по элементам строки, в которой сумма элементов больше двух. Они соответственно переносятся. В най
денной же строке ставятся единицы на |
пересечении с вновь вве |
|||||||
денными |
столбцами. |
Соответствующим |
образом |
корректируется |
||||
и связь других |
операций с данной'операцией |
сравнения. |
||||||
Рассмотрим |
в качестве примера один |
из |
фрагментов задачи |
|||||
составления сводки |
о реализации фондов |
в |
отделе |
оборудования |
||||
и транспортном |
отделе. Графы |
алгоритмов |
этих задач приведены |
|||||
на рис. 21 и 22. |
|
|
|
|
|
|
|
|
Строим |
матрицы смежности |
фрагментов Ai и А2 |
(см. стр. 123— |
|||||
125). Вершины этих фрагментов выделены на графах кружками. Поскольку в матрице А имеются элементы, равные двум, то
производим корректировку ее (см. стр. 126). В результате коррек тировки получается матрица А*, число столбцов и строк которой на два элемента больше, чем в матрице А. Это результат расшире
ния |
графа, так как в строке с номером Ср4 |
сумма элементов после |
||
замены двоек единицами оказалась больше двух. |
А*, |
|
||
|
На рис. 23 часть графа, соответствующая матрице |
отмече |
||
на |
кружками. |
|
|
|
|
Задавая вектор операций конкретного |
алгоритма |
и |
выбирая |
из матрицы А* соответствующие строки, получаем матрицу смеж ности этого алгоритма.
Для оценки алгоритмов синтеза был проведен эксперимент на машине «Минск-22» для матриц размерностью 4X4, 12X12, 36Х
Х36. В табл. 2 приведены |
данные о времени |
синтеза алгоритмов |
по методу Карпа —строка |
К и с применением |
графов — строка Г. |
Время в таблице исчисляется в секундах. |
|
|
122
|
U |
|
|
о 3" |
t: |
|
|
>г |
СО |
|
о |
|
|
|
а-" CQ |
|
О |
|
||||
|
|
|
|
|
|
о |
3 |
|
|
|
|
|
|
|
||||||||
Cpi |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
npi |
l |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
Cp2 |
0 |
0 |
|
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
СРъ |
0 0 |
0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 |
||||||||||||||||||||
Пр2 |
0 |
0 |
|
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
0 |
0 |
|
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
c2 |
0 |
0 |
|
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
У1 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
Cp4 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
Ci |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
Л\ |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
У2 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
Уз |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
Сръ |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
|
Пр3 |
0 0 0 0 0 0 0 0 0 0 |
|
0 0 0 0 |
0 0 1 0 о jo |
||||||||||||||||||
Bct |
0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 |
0 0 0 |
||||||||||||||||||||
CPs |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
|
с. |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
|
|
0 0 0 0 0 0 0 0 0 с 0 0 0 0 1 0 0 0 0 0 |
|||||||||||||||||||||
123
ё |
со |
осо 3 о |
00 |
4S |
|
||||
«з- 1? о о |
а- |
oq |
Cpi |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
npi |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
СPi |
0 0 0 |
1 0 |
1 0 0 0 0 0 |
0 0 0 0 0 0 0 0 |
||||||||||||||||
Срг |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
||
Пр2 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
с, |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
с, |
0 0 |
0 |
1 0 0 |
0 |
0 0 0 0 |
0 0 |
0 0 0 |
0 |
0 |
| 0 |
||||||||||
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
= с3 |
0 0 0 0 0 0 0 0 0 |
1 0 |
0 |
0 |
0 0 0 0 |
0 0 |
||||||||||||||
Cpi |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
|
0 |
0 |
1 |
0 |
0 |
0 |
0 |
с, |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
1 |
0 |
0 |
0 |
0 |
0 |
0 |
у, |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
1 |
0 |
0 |
0 |
0 |
0 |
Уз |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
Ср7 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
|
Пръ |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
Ср& |
0 0 0 0 0 0 0 0 0 0 |
1 0 0 0 0 0 |
0 1 0 |
|||||||||||||||||
Пре |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
1 |
Вс2 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
Суммируем матрицы Ах и А2 и получаем матрицу А.
|
о о о О о о о о о о о о о о о о о о о о о о |
о - о |
|||
CD о о с о о о о о о о о о о о о о о о о о о о |
- о о |
||||
|
<= о о о о о о о о о о о о о » о о 5о о 1—1о о о о |
||||
а- |
о о о о о о о о о о о о о о о о о о о о - о о о |
||||
г- |
о о о о о о о о о т—< о о о о о о о о о о о о о о о |
||||
|
|||||
|
о о о о о о о о о о о о о о о о о |
- |
о о о о о о |
||
о |
о о о о о •= о о о о о о о о о о о |
- |
о о о о о о о |
||
со |
|
|
|
|
|
CD о о о о о о о о о о о о о о - |
о о о о о о о о о о |
||||
CQ - |
о о о о о о о о о о о о о о |
- о о о о о о о о о |
|||
•о1 |
о о о » о о о о о о о о о о - о о о о о о о о о |
||||
п |
|||||
а. |
|||||
о о = о о о о о о ~ о о о о о о о о о о о о о о
о
а-
«
о
1
со
i f
о |
о о |
о о о о о о о о о сч о о о о о о о о о о о о |
о о о о « о о о о о о (М о о о о о о о о о о о о о |
||
о о о о о - о о о о сч о о о о о о о о о о о |
о о о |
= о о о о о о о о сч о о с о о о о о о о о о |
- о о |
о о о о о о о о сч о о о о о о = - о о о о - |
о о - |
о о о о о о о <мо о о о о о о о о о о о о о о о о
о о |
с СЧ |
о о о о о о о о о о о о о о о о о о о о о |
||
о о о о |
о о |
о о о <=> о |
о о о о о о о о о о о о о |
|
о о сч о о ( N |
о о о о о ~ о о о о о о о о о о о о о |
|||
о о о сч о о о о о о о о о о о о о о о о о о о о о |
|
о о сч о о о CN о о о о о о о |
о о о о о о о о о о о |
<мо о о сч о о о о => о о о о |
о о о о о о о о о о о |
см о о о о о о о о о о о о о о о о о = о о о о о о |
|
о сч о о о о о о о о о о о о о о о о о о о о о => о |
|
|
со |
о ^ |
in |
со |
<s |
с». |
|
<и >г о |
|
||||
|
|
|
|
|
ОС а |
|
3" с5 а" |
|
II |
5- а-оа о |
с5 о |
||
|
|
|
|
|
|
|
12а