Диссертация (1149691), страница 10
Текст из файла (страница 10)
. , } и такие нагрузки = {1 , 2 , . . . , }, причем для всех из — является нагрузкойвершины [120; 166].Определение 2.6.4 ([104; 116; 166]).иПересечение нагрузок двух вершинбудем называть сепаратором.Определение 2.6.5 ([166]). Число элементов в заданном сепараторе назовем мощностью сепаратора.Определение 2.6.6 ([166]).Будем называть списком набор объектов,доступных по индексу.Определение 2.6.7 ([116]).= ⟨′,′⟩:′= { : ∈= ⟨ , ⟩, тогда граф′= {⟨, ⟩ : , ∈ &⟨, ⟩ ∈ }Пусть дан граф&∈},′↓.Введем ряд дополнительных обозначений, введенных в [104; 115], которые понадобятся нам при описании алгоритмов. [115] — упорядоченная по убыванию мощностей сепараторов очередь уникальных элементов, рассматриваемая как некоторое множество.Генерация множества осуществляется следующим образом: для любыхдвух вершин из множества вершин вычисляется их сепаратор, затем изполученного набора сепараторов в множество добавляются сепараторы впорядке убывания их мощностей (например: {{,,,},{,}, {,},{},{}}).Может возникнуть ситуация [105], когда в наборе сепараторов будут содержаться одинаковые сепараторы, в таком случае в множество необходимодобавить только один из них (см.
пример). Очередь реализуется в языкахпрограммирования C#, C++ и Java с помощью Queue [44; 45; 54]. [115] — структура данных, реализующая представление множества.Элементами S являются вершины. Порядок элементов в не важен, значит,54для реализации представления множества можно использовать структуруданных список. Для реализации такого списка в языках программированияв языках C++,C# и Java можно использовать List [42; 43; 53].Delegate( ) [115] — функция, которая возвращает произвольный элемент множества S. При этом сам возвращаемый элемент не удаляется измножества . Если пусто, алгоритм предусматривает добавление новыхэлементов в множество; таким образом, функция Delegate всегда будет принимать на вход непустое множество.Component(, , ) [115] — функция, которая принимает в качествепервого аргумента граф, второго — вершину, третьего — сепаратор (нагрузку). Первым шагом своей работы функция генерирует граф ↓ , затемполучает множество достижимых вершин в графе ↓ из вершины ,включая саму эту вершину.
Таким образом, функция вернет множестводостижимых вершин, содержащее, как минимум, вершину .Q.Top() [104; 115] — функция, которая возвращает очередной элементиз очереди и удаляет этот элемент из .PathExists(G, edge, nodeBegin, nodeEnd) [105] — функция, котораяопределяет, связаны ли магистрально вершины nodeBegin и nodeEnd гра′′′фе = ⟨ , ⟩, причем, = ⟨ , ⟩, и = {⟨, ⟩ : ⟨, ⟩ ∈ &⟨, ⟩ ̸= }.edge.First, edge.Second [105] — вершины ребра edge.edge.RemoveAllowed [105] — метка, которая показывает, возможно лиудаление ребра или нет. Изначальное значение — true.Прямой и жадный алгоритмы синтезируют структуру минимальногографа смежности «с нуля», т.е.
не учитывают структуру ребер, котораямогла «накопиться» в существующем графе. Такое поведение алгоритмане является его недостатком, ведь, с одной стороны, чтобы в графе были связи между ребрами, необходимо «с нуля» такие связи выстроить, сдругой стороны, в некоторых случаях более актуальной задачей является построение минимального графа смежности без учета существующихсвязей между ребер. Однако в динамических системах и онлайн-взаимодействиях, при значительном числе вершин в минимальном графе смежности,особо важной задачей является поддержка «минимальности» в таком графесмежности: при добавлении нового «клиента» (в графе - вершины) или удалении существующего, граф смежности должен оставаться минимальным.55МГС может широко использоваться в сетях передачи данных и шифровании, о чем будет рассказано далее.
Рассмотрим подробно каждый изсуществующих алгоритмов синтеза МГС.Прямой алгоритмНа листинге 2.1 приведен алгоритм прямой генерации минимальногографа смежности, который был формализован в статье [115], а в статье [108]был подробно описан. Алгоритм состоит из двух основных частей. В строках 2–7 формируется множество сепараторов.
В строках 8–18 происходитформирование минимального графа смежности. Подробнее алгоритм рассмотрен в [166; 171], здесь же приведем только листинг [108; 115].Листинг 2.1 — Прямой алгоритм построения минимального графасмежности [101; 104].input : ,output : = ⟨ , ⟩function Straight = ∅5 = ⟨ ,∅⟩foreach ( in )foreach ( in ∖ )if ( ∩ ̸= ∅ && = ∪ ∩ 10while ( ̸= ∅ ) = . Top () = ∅15∩̸⊂) thenforeach ( in )if ( in && ( not inif ( ̸= ∅ ) thend = Delegate ( ) = ∪ Component ( ,, ). = .
∪ (, )else = (,, )return 20) ) then56Жадный алгоритмНа листинге 2.2 приведен жадный алгоритм генерации минимальногографа смежности, рассмотренный в статьях [105]. Его отличие от прямогоалгоритма рассмотрено в [104], там же дано доказательство корректности,существенно опирающееся на то, что система графов смежности является матроидом [116].Листинг 2.2 — Жадный алгоритм построения минимального графасмежности [101; 104; 105].input : ,output : = ⟨ , ⟩function Greedy = ⟨ ,∅⟩5foreach ( in )foreach ( in ∖ )if ( ∩ ̸= ∅ ) then.
= . ∪ (, )101520while ( true )edge = ∅foreach ( in . )if ( e . RemoveAllowed ) thenedge = ebreakif ( edge == ∅ ) thenbreakif ( PathExists ( , edge , edge . First , edge . Second ) ) then. − . ∖ edgeelseedge . RemoveAllowed = false ;return 572.6.4Третичная и четвертичная структурыМатериалы изложенные в данном параграфе излагаются в соответствие с работами [121; 175]. В то время как первичная и вторичнаяструктуры необходимы для проведения глобального вывода, третичнаяи четвертичная структуры являются в некотором роде вспомогательными и служат другим целям: выявлению ацикличности вторичнойструктуры [179; 180], построению всего множества минимальных графовсмежности [171], а также поиску наиболее эффективной вторичной структуры [175].
Кроме того третичная и четвертичная структуры в некоторыхалгоритмах участвуют в синтезе вторичной структуры [171].Определение 2.6.8 ([175]).Третичная структура — это граф, представленный в виде диаграммы Хассе с порядком следования сверхувниз, построенный на множестве непустых сепараторов.Определение 2.6.9 ([175]).Родитель сепаратора — это сепаратор,предшествующий данному в третичной структуре.Определение 2.6.10 ([175]).Сын сепаратора — это сепаратор, следующий за данным в третичной структуре.Определение 2.6.11 ([171]). Полусиблинговый граф сепаратора — этограф, построенный над множеством его сыновей, ребро между двумявершинами которого проведено тогда и только тогда, когда сужения,соответствующие данным вершинам, пересекаются.Из предложенных выше определений следует что сужения максимального графа пересекаются, если пересекаются множества вершинрассматриваемых сужений. Такое возможно в том случае, когда существует 2 или более вершины, принадлежащие обоим сужениям, из чего следует,что рассматриваемые вершины содержат оба сепаратора, по которым построены сужения.
Отсюда следует, что сужение двух сыновей сепаратора пересекаются, если в максимальном графе присутствует вершина с нагрузкой, включающей в себя оба сына.58Определение 2.6.12 ([169]).Четвертичная структура — это семейство полусиблинговых графов, построенных для каждого элементамножества сепараторов, которое пополнено пустым сепаратором.Отметим, что третичная структура активно используется при построении и перестроении четвертичной структуры. Алгоритмы синтезатретичной и четвертичной структур подробно описаны в работах [88; 121;122; 171; 175].2.6.5Глобальный логико-вероятностный выводОдним из применений вторичной структуры является глобальный логико-вероятностный вывод, а именно вторая задача апостериорного вывода— пропагация свидетельства [139]. Алгоритм пропагации (распространения) свидетельства по алгебраической байесовской сети подразумеваетиспользование декомпозиции предметной области над отдельные фрагменты знаний.
Такой подход позволяет существенно сократить объемвычислений в сравнении с проведением апостериорного вывода с погружением сети в объемлющий фрагмент знаний, дающим экспоненциальныйрост количества операций при увеличении мощности алфавита. Приведемниже общий алгоритм распространения свидетельства по алгебраическойбайесовской сети. Алгоритм можно представить следующей последовательностью действий:– пропагация свидетельства извне в первый ФЗ ⟨1 ,1 ⟩ и переозначивание оценок вероятностей элементов в нем;– формирование виртуального свидетельства над подалфавитом алфавита 1 ;– пропагация виртуального свидетельства в во всех ФЗ, соединенныес данным;Определение 2.6.13 ([139]).гируемым из ФЗ ⟨1 ,1 ⟩ вВиртуальным свидетельством, пропаФЗ⟨2 2⟩,называется свидетельство,59Рисунок 2.3 — Распространение виртуального свидетельства по АБСпостроенное над алфавитом=1 ∩ 2, оценки вероятности истинности которого совпадают с оценками вероятностей элементов1 .Таким образом, виртуальное свидетельство является фрагментом знаний, выделенным из первого фрагмента знаний после пропагации в негосвидетельства и получения апостериорных оценок вероятностей.Утверждение 2.6.1 ([139]).Пропагация стохастического свидетельства, поступающего в один из фрагментов знаний и последующеераспространение виртуального свидетельства по алгебраической байесовской сети дает те же апостериорные оценки вероятностей, чтои пропагация исходного свидетельства в объемлющий фрагмент знаний.В случае, если алфавит, над которым построено детерминированноесвидетельство, не входит полностью ни в один из алфавитов фрагментовзнаний, принадлежащих рассматриваемой алгебраической байесовской сети, то такое свидетельство следует разбить на несколько не пересекающихсядетерминированных свидетельств, каждое из которых будет поступать60только в один фрагмент знаний, а затем последовательно пропагироватьих.
Стоит отметить, что конечное распределение апостериорных вероятностей не зависит от последовательности пропагации свидетельств.Кроме того, интерес представляет также и выбор фрагмента знаний,в который стоит пропагировать свидетельство, в том случае, если подходящих фрагментов оказывается несколько. Здесь важен тот факт, чтовсе операции производятся с ациклической алгебраической байесовскойсетью, представимой в виде дерева.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
