ВУЗ:
Составители:
Рубрика:
AAAAA
AA AA
AAA
AAA
12436
1236
136
156
,,,,
,,,
,,
,,
⎧
⎨
⎪
⎪
⎩
⎪
⎪
AA A A
AA A
AAA
AAA
12 36
124
136
156
,,,
,,
,,
,,
⎧
⎨
⎪
⎪
⎩
⎪
⎪
AA A
AAA
AAA
AA
124
136
156
12
,,
,,
,,
,,
⎧
⎨
⎪
⎪
⎩
⎪
⎪
AA A
AAA
AAA
12 4
136
156
,,
,,
,,
⎧
⎨
⎪
⎪
⎩
⎪
⎪
применим правило
П2 к 1-му и 4-му
дизъюнктам, удалив
4-й дизъюнкт,
имеем
применим правило
П3 к 1-му и 3-му
дизъюнктам,
упорядочив, имеем
применим правило
П3 к 1-му и 2-му
дизъюнктам,
упорядочив, имеем
В результате исходная формула (3.1) упростилась до вида (3.2), количество
операций сократилось с 14 до 8. Вычислительные эксперименты показали, что
сокращения числа операций на реальных объектах в среднем составляет 50%, причем, с
ростом цикломатического числа, когда число маршрутов нарастает, производительность
алгоритма сжатия операций увеличивается.
3.4. Алгоритм классификации данных на основе частичного
перебора маршрутов ориентированного графа
Описанный выше алгоритм классификации данных агрегата использует
цикломатический анализ неориентированных графов, эквивалентных исходному.
Главной проблемой этого метода является комбинаторный рост числа циклов с ростом
цикломатического числа графа (см. табл.3.3) и ограниченность типов рассматриваемых
циклов. Цикломатика обеспечивает перечисление простых и сложных циклов, не
рассматривая составные циклы, когда одна или несколько дуг
повторяются. На рис.3.7
показан граф, имеющий составной цикл R={a, b, c, a, d}.
c
a
d
b
Рис. 3.7
В работах [26, 34] предлагается метод классификации типов данных, основанный
на реализации частичного перебора маршрутов граф-агрегата.
На этапе перечисления маршрутов из корневой вершины в концевые, метод
использует свойства алгебры 3-х значной логики классификации данных.
Маршруты ориентированного графа будем описывать списками вершин. Данный
подход менее удобен, чем при использовании списка дуг, поскольку
часто содержит
повторяющиеся вершины. Например, маршрут
M={A, B, E, F, B, C, D, B, G} графа G2 (см.
рис. 3.8) повторяет вершину
B три раза.
Однако, учитывая свойство 4 операции следования алгебры 3-значной логики, все
“повторные” вхождения вершин графа в список можно исключить.
Страницы
- « первая
- ‹ предыдущая
- …
- 33
- 34
- 35
- 36
- 37
- …
- следующая ›
- последняя »
