Обобщенный распределительный закон

Обобщены дистрибутивный закон (GDL) является обобщением распределительного свойства , которое приводит к возникновению общего прохождения сообщения алгоритму. ^[1] Это синтез работ многих авторов в области теории информации , цифровых коммуникаций , обработки сигналов , статистики и искусственного интеллекта . Закон и алгоритм были представлены в полуучебном пособии Шриниваса М. Аджи и Роберта Дж. МакЭлиса с тем же названием. ^[1]

Введение [ править ]

«Закон распределения в математике - это закон, связывающий операции умножения и сложения, выраженные символически, то есть мономиальный множитель распределяется или применяется отдельно к каждому члену биномиального множителя , в результате чего получается произведение »${\ Displaystyle а * (Ь + с) = а * Ь + а * с}$${\ displaystyle a}$${\ displaystyle b + c}$${\ displaystyle a * b + a * c}$ - Britannica ^{[ 2]}

Как видно из определения, применение закона распределения к арифметическому выражению сокращает количество операций в нем. В предыдущем примере общее количество операций уменьшилось с трех (два умножения и сложение в ) до двух (одно умножение и одно сложение ). Обобщение закона распределения приводит к большому семейству быстрых алгоритмов . Это включает в себя алгоритм БПФ и Витерби .${\ displaystyle a * b + a * c}$${\ Displaystyle а * (Ь + с)}$

Более формально это объясняется в следующем примере:

${\ displaystyle \ alpha (a, \, b) {\ stackrel {\ mathrm {def}} {=}} \ displaystyle \ sum \ limits _ {c, d, e \ in A} f (a, \, c , \, b) \, g (a, \, d, \, e)}$где и - действительные функции, и (скажем)${\ Displaystyle е (\ cdot)}$${\ Displaystyle г (\ cdot)}$${\ displaystyle a, b, c, d, e \ in A}$${\ displaystyle | A | = q}$

Здесь мы «маргинализация из» независимых переменных ( , и ) , чтобы получить результат. Когда мы вычисляем вычислительную сложность, мы видим, что для каждой пары есть члены, связанные с триплетом, который должен принимать участие в оценке с каждым шагом, имеющим одно сложение и одно умножение. Следовательно, общее количество необходимых вычислений равно . Следовательно, асимптотическая сложность указанной функции равна .${\ displaystyle c}$${\ displaystyle d}$${\ displaystyle e}$${\ displaystyle q ^ {2}}$${\ Displaystyle (а, б)}$${\ displaystyle q ^ {3}}$${\ displaystyle (c, d, e)}$${\ Displaystyle \ альфа (а, \, Ь)}$${\ Displaystyle 2 \ cdot q ^ {2} \ cdot q ^ {3} = 2q ^ {5}}$${\ Displaystyle О (п ^ {5})}$

Если мы применим закон распределения к правой части уравнения, мы получим следующее:

${\ Displaystyle \ альфа (a, \, b) {\ stackrel {\ mathrm {def}} {=}} \ displaystyle \ sum \ limits _ {c \ in A} f (a, \, c, \, b ) \ cdot \ sum _ {d, \, e \ in A} g (a, \, d, \, e)}$

Это означает, что его можно описать как продукт, в котором и${\ Displaystyle \ альфа (а, \, Ь)}$${\ Displaystyle \ альфа _ {1} (а, \, Ь) \ CDOT \ альфа _ {2} (а)}$${\displaystyle \alpha _{1}(a,b){\stackrel {\mathrm {def} }{=}}\displaystyle \sum \limits _{c\in A}f(a,\,c,\,b)}$${\displaystyle \alpha _{2}(a){\stackrel {\mathrm {def} }{=}}\displaystyle \sum \limits _{d,\,e\in A}g(a,\,d,\,e)}$

Теперь, когда мы вычисляем вычислительную сложность, мы можем видеть, что есть сложение и каждое, и есть умножения, когда мы используем произведение для оценки . Следовательно, общее количество необходимых вычислений равно . Следовательно, асимптотическая сложность вычислений сводится к от . Это показывает на примере, что применение закона распределения снижает вычислительную сложность, что является одной из хороших черт «быстрого алгоритма».${\displaystyle q^{3}}$${\displaystyle \alpha _{1}(a,\,b)}$${\displaystyle \alpha _{2}(a)}$${\displaystyle q^{2}}$${\displaystyle \alpha _{1}(a,\,b)\cdot \alpha _{2}(a)}$${\displaystyle \alpha (a,\,b)}$${\displaystyle q^{3}+q^{3}+q^{2}=2q^{3}+q^{2}}$${\displaystyle \alpha (a,b)}$${\displaystyle O(n^{3})}$${\displaystyle O(n^{5})}$

История [ править ]

Некоторые из проблем, для решения которых использовался закон распределения, можно сгруппировать следующим образом.

1. Алгоритмы декодирования
. GDL-подобный алгоритм использовался Галлагером для декодирования кодов с низкой плотностью проверки на четность. Основываясь на работе Галлагера, Таннер представил граф Таннера и выразил работу Галлагера в форме передачи сообщений. График Таннерса также помог объяснить алгоритм Витерби .

Форни заметил, что при декодировании сверточных кодов методом максимального правдоподобия Витерби также использовались алгоритмы общности, подобные GDL.

2. Алгоритм
"вперед -назад". Алгоритм "вперед-назад" помогал как алгоритм отслеживания состояний в цепи Маркова . И для этого также использовался алгоритм GDL типа общности

3. Искусственный интеллект
. Понятие деревьев соединений использовалось для решения многих задач в области ИИ. Также концепция исключения ведра использовала многие концепции.

Проблема MPF [ править ]

МПФ или изолировать функцию продукта является общей вычислительной проблемой , которая , как частный случай включает в себя множество классических задач , такие как вычисление дискретного преобразования Адамар , максимальное правдоподобие декодирования из линейного кода над памятью менее каналом , и матрица цепи умножение . Сила GDL заключается в том, что он применяется к ситуациям, в которых сложение и умножение являются обобщенными. Коммутативное полукольцо является хорошей основой для объяснения такого поведения. Он определен над множеством с операторами " " и " " где и - коммутативные моноиды${\displaystyle K}$${\displaystyle +}$${\displaystyle .}$${\displaystyle (K,\,+)}$${\displaystyle (K,\,.)}$ и закон распределения сохраняется.

Позвольте быть переменные такие, что где конечное множество и . Вот . Если и , пусть , , , , и${\displaystyle p_{1},\ldots ,p_{n}}$${\displaystyle p_{1}\in A_{1},\ldots ,p_{n}\in A_{n}}$${\displaystyle A}$${\displaystyle |A_{i}|=q_{i}}$${\displaystyle i=1,\ldots ,n}$${\displaystyle S=\{i_{1},\ldots ,i_{r}\}}$${\displaystyle S\,\subset \{1,\ldots ,n\}}$${\displaystyle A_{S}=A_{i_{1}}\times \cdots \times A_{i_{r}}}$${\displaystyle p_{S}=(p_{i_{1}},\ldots ,p_{i_{r}})}$${\displaystyle q_{S}=|A_{S}|}$${\displaystyle \mathbf {A} =A_{1}\times \cdots \times A_{n}}$${\displaystyle \mathbf {p} =\{p_{1},\ldots ,p_{n}\}}$

Пусть где . Предположим, что функция определена как , где - коммутативное полукольцо . Кроме того , будут названы локальные домены и как локальных ядер .${\displaystyle S=\{S_{j}\}_{j=1}^{M}}$${\displaystyle S_{j}\subset \{1,...\,,n\}}$${\displaystyle \alpha _{i}:A_{S_{i}}\rightarrow R}$${\displaystyle R}$${\displaystyle p_{S_{i}}}$${\displaystyle \alpha _{i}}$

Теперь глобальное ядро определяется как:${\displaystyle \beta :\mathbf {A} \rightarrow R}$${\displaystyle \beta (p_{1},...\,,p_{n})=\prod _{i=1}^{M}\alpha (p_{S_{i}})}$

Определение проблемы MPF : для одного или нескольких индексов вычислите таблицу значений - маргинализации глобального ядра , которая является функцией, определенной как${\displaystyle i=1,...\,,M}$${\displaystyle S_{i}}$${\displaystyle \beta }$${\displaystyle \beta _{i}:A_{S_{i}}\rightarrow R}$${\displaystyle \beta _{i}(p_{S_{i}})\,=\displaystyle \sum \limits _{p_{S_{i}^{c}}\in A_{S_{i}^{c}}}\beta (p)}$

Вот дополнение по отношению к, и называется целевой функцией , или целевой функцией в . Можно заметить, что вычисление целевой функции очевидным образом требует операций. Это связано с тем, что при вычислении целевой функции необходимы сложения и умножения . Алгоритм GDL, который объясняется в следующем разделе, может уменьшить эту вычислительную сложность.${\displaystyle S_{i}^{c}}$${\displaystyle S_{i}}$${\displaystyle \mathbf {\{} 1,...\,,n\}}$${\displaystyle \beta _{i}(p_{S_{i}})}$${\displaystyle i^{th}}$ ${\displaystyle S_{i}}$${\displaystyle i^{th}}$${\displaystyle Mq_{1}q_{2}q_{3}\cdots q_{n}}$${\displaystyle q_{1}q_{2}\cdots q_{n}}$${\displaystyle (M-1)q_{1}q_{2}...q_{n}}$${\displaystyle i^{\text{th}}}$

Ниже приведен пример проблемы MPF. Позвольте и быть такими переменными, что и . Вот и . Данные функции, использующие эти переменные, есть и, и нам нужно вычислить и определить как:${\displaystyle p_{1},\,p_{2},\,p_{3},\,p_{4},}$${\displaystyle p_{5}}$${\displaystyle p_{1}\in A_{1},p_{2}\in A_{2},p_{3}\in A_{3},p_{4}\in A_{4},}$${\displaystyle p_{5}\in A_{5}}$${\displaystyle M=4}$${\displaystyle S=\{\{1,2,5\},\{2,4\},\{1,4\},\{2\}\}}$${\displaystyle f(p_{1},p_{2},p_{5})}$${\displaystyle g(p_{3},p_{4})}$${\displaystyle \alpha (p_{1},\,p_{4})}$${\displaystyle \beta (p_{2})}$

${\displaystyle \alpha (p_{1},\,p_{4})=\displaystyle \sum \limits _{p_{2}\in A_{2},\,p_{3}\in A_{3},\,p_{5}\in A_{5}}f(p_{1},\,p_{2},\,p_{5})\cdot g(p_{2},\,p_{4})}$

${\displaystyle \beta (p_{2})=\sum \limits _{p_{1}\in A_{1},\,p_{3}\in A_{3},\,p_{4}\in A_{4},\,p_{5}\in A_{5}}f(p_{1},\,p_{2},\,p_{5})\cdot g(p_{2},\,p_{4})}$

Здесь локальные домены и локальные ядра определяются следующим образом:

локальные домены	локальные ядра
${\displaystyle \{p_{1},p_{2},p_{5}\}}$	${\displaystyle (f(p_{1},p_{2},p_{5})}$
${\displaystyle \{p_{2},p_{4}\}}$	${\displaystyle g(p_{2},p_{4})}$
${\displaystyle \{p_{1},p_{4}\}}$	${\displaystyle 1}$
${\displaystyle \{p_{2}\}}$	${\displaystyle 1}$

где - целевая функция, а - целевая функция.${\displaystyle \alpha (p_{1},p_{4})}$${\displaystyle 3^{rd}}$${\displaystyle \beta (p_{2})}$${\displaystyle 4^{th}}$

Рассмотрим другой пример, где и - функция с действительным знаком. Теперь мы рассмотрим задачу MPF, в которой коммутативное полукольцо определяется как множество действительных чисел с обычным сложением и умножением, а локальные области и локальные ядра определяются следующим образом:${\displaystyle p_{1},p_{2},p_{3},p_{4},r_{1},r_{2},r_{3},r_{4}\in \{0,1\}}$${\displaystyle f(r_{1},r_{2},r_{3},r_{4})}$

локальные домены	локальные ядра
${\displaystyle \{r_{1},r_{2},r_{3},r_{4}\}}$	${\displaystyle f(r_{1},r_{2},r_{3},r_{4})}$
${\displaystyle \{p_{1},r_{1}\}}$	${\displaystyle (-1)^{p_{1}r_{1}}}$
${\displaystyle \{p_{2},r_{2}\}}$	${\displaystyle (-1)^{p_{2}r_{2}}}$
${\displaystyle \{p_{3},r_{3}\}}$	${\displaystyle (-1)^{p_{3}r_{3}}}$
${\displaystyle \{p_{4},r_{4}\}}$	${\displaystyle (-1)^{p_{4}r_{4}}}$
${\displaystyle \{p_{1},p_{2},p_{3},p_{4}\}}$	${\displaystyle 1}$

Теперь, поскольку глобальное ядро ​​определяется как произведение локальных ядер, оно

${\displaystyle F(p_{1},p_{2},p_{3},p_{4},r_{1},r_{2},r_{3},r_{4})=f(p_{1},p_{2},p_{3},p_{4})\cdot (-1)^{p_{1}r_{1}+p_{2}r_{2}+p_{3}r_{3}+p_{4}r_{4}}}$

а целевая функция в локальной области равна${\displaystyle p_{1},p_{2},p_{3},p_{4}}$

${\displaystyle F(p_{1},p_{2},p_{3},p_{4})=\displaystyle \sum \limits _{r_{1},r_{2},r_{3},r_{4}}f(r_{1},r_{2},r_{3},r_{4})\cdot (-1)^{p_{1}r_{1}+p_{2}r_{2}+p_{3}r_{3}+p_{4}r_{4}}.}$

Это преобразование Адамара функции . Следовательно, мы можем видеть, что вычисление преобразования Адамара является частным случаем задачи MPF. Можно продемонстрировать больше примеров, чтобы доказать, что проблема MPF образует частные случаи многих классических задач, как объяснено выше, детали которых можно найти в ^[1]${\displaystyle f(\cdot )}$

GDL: алгоритм решения проблемы MPF [ править ]

Если можно найти взаимосвязь между элементами данного набора , то можно решить проблему MPF, основываясь на понятии распространения убеждений, которое является особым использованием техники «передачи сообщений». Требуемая взаимосвязь состоит в том, что данный набор локальных доменов может быть организован в дерево соединений . Другими словами, мы создаем теоретико-графовое дерево с элементами в качестве вершин дерева , так что для любых двух произвольных вершин говорят и где и существует ребро между этими двумя вершинами, то пересечение соответствующих меток, а именно , - это подмножество метки на каждой вершине уникального пути от до .${\displaystyle S}$${\displaystyle S}$ ${\displaystyle T}$${\displaystyle v_{i}}$${\displaystyle v_{j}}$${\displaystyle i\neq j}$${\displaystyle S_{i}\cap S_{j}}$${\displaystyle v_{i}}$${\displaystyle v_{j}}$

Например,

Пример 1. Рассмотрим следующие девять локальных доменов:

1. ${\displaystyle \{p_{2}\}}$
2. ${\displaystyle \{p_{3},p_{2}\}}$
3. ${\displaystyle \{p_{2},p_{1}\}}$
4. ${\displaystyle \{p_{3},p_{4}\}}$
5. ${\displaystyle \{p_{3}\}}$
6. ${\displaystyle \{p_{1},p_{4}\}}$
7. ${\displaystyle \{p_{1}\}}$
8. ${\displaystyle \{p_{4}\}}$
9. ${\displaystyle \{p_{2},p_{4}\}}$

Для указанного выше набора локальных доменов их можно организовать в дерево соединений, как показано ниже:

Аналогично, если дан другой набор, подобный следующему

Пример 2: Рассмотрим следующие четыре локальных домена:

1. ${\displaystyle \{p_{1},p_{2}\}}$
2. ${\displaystyle \{p_{2},p_{3}\}}$
3. ${\displaystyle \{p_{3},p_{4}\}}$
4. ${\displaystyle \{p_{1},p_{4}\}}$

Тогда построение дерева только с этими локальными доменами невозможно, так как этот набор значений не имеет общих доменов, которые можно разместить между любыми двумя значениями указанного выше набора. Но, однако, если добавить два фиктивных домена, как показано ниже, то организация обновленного набора в дерево соединений станет возможной и простой.

5. , 6. ,${\displaystyle \{p_{1},p_{2}}$${\displaystyle p_{4}\}}$
${\displaystyle \{p_{2},p_{3}}$${\displaystyle p_{4}\}}$

Аналогично для этого набора доменов дерево соединений выглядит так, как показано ниже:

Алгоритм обобщенного закона распределения (GDL) [ править ]

Вход: набор локальных доменов.
Выход: для данного набора доменов вычисляется возможное минимальное количество операций, необходимых для решения задачи.
Таким образом, если и связаны ребром в дереве соединений, то сообщение от до представляет собой набор / таблицу значений, заданных функцией :: . Для начала все функции, т.е. для всех комбинаций и в данном дереве, определены как идентичные, и когда конкретное сообщение обновляется, оно следует уравнению, приведенному ниже.${\displaystyle v_{i}}$${\displaystyle v_{j}}$${\displaystyle v_{i}}$${\displaystyle v_{j}}$${\displaystyle \mu _{i,j}}$${\displaystyle A_{S_{i}\cap S_{j}}\rightarrow R}$${\displaystyle i}$${\displaystyle j}$${\displaystyle \mu _{i,j}}$${\displaystyle 1}$

${\displaystyle \mu _{i,j}(p_{S_{i}\cap S_{j}})}$ знак равно ${\displaystyle \sum _{p_{S_{i}\setminus S_{j}}\in A_{S_{i}\setminus S_{j}}}\alpha _{i}(p_{S_{i}})\prod _{{v_{k}\operatorname {adj} v_{i}},{k\neq j}}\mu _{k,j}(p_{S_{k}\cap S_{i}})(1)}$

где означает, что это смежная вершина в дереве.${\displaystyle v_{k}\operatorname {adj} v_{i}}$${\displaystyle v_{k}}$${\displaystyle v_{i}}$

Точно так же каждая вершина имеет состояние, которое определяется как таблица, содержащая значения из функции. Точно так же, как сообщения инициализируются значением 1 идентично, состояние определяется как локальное ядро , но при каждом обновлении оно следует следующему уравнению:${\displaystyle \sigma _{i}:A_{S_{i}}\rightarrow R}$${\displaystyle v_{i}}$${\displaystyle \alpha (p_{S_{i}})}$${\displaystyle \sigma _{i}}$

${\displaystyle \sigma (p_{S_{i}})=\alpha _{i}(p_{S_{i}})\prod _{v_{k}\operatorname {adj} v_{i}}\mu _{k,j}(p_{S_{k}\cap S_{i}})(2).}$

Основы работы алгоритма [ править ]

Для данного набора локальных доменов в качестве входных данных мы выясняем, можем ли мы создать дерево соединений, либо напрямую используя набор, либо добавляя сначала фиктивные домены в набор, а затем создавая дерево соединений, если построение соединения невозможно, тогда вывод алгоритма, что нет способа уменьшить количество шагов для вычисления данной задачи уравнения, но как только у нас есть дерево соединений, алгоритм должен будет запланировать сообщения и вычислить состояния, делая это, мы можем знать, где шаги могут быть уменьшены, следовательно будет обсуждаться это ниже.

Планирование передачи сообщений и вычисления состояния [ править ]

Здесь мы собираемся поговорить о двух особых случаях, а именно о задаче с одной вершиной, в которой целевая функция вычисляется только в одной вершине, а во втором - задаче со всеми вершинами, цель которой состоит в том, чтобы вычислить целевую функцию во всех вершинах.${\displaystyle v_{0}}$

Давайте начнем с проблемы с одной вершиной , GDL начнет с направления каждого ребра к целевой вершине . Здесь сообщения отправляются только в направлении целевой вершины. Обратите внимание, что все направленные сообщения отправляются только один раз. Сообщения начинаются с конечных узлов (где степень равна 1) и идут вверх к целевой вершине . Сообщение передается от листьев к своим родителям, а затем оттуда к их родителям и так далее, пока не достигнет целевой вершины . Целевая вершина вычислит свое состояние только тогда, когда она получит все сообщения от всех своих соседей. Когда у нас есть состояние, мы получили ответ, и, следовательно, алгоритм завершается.${\displaystyle v_{0}}$${\displaystyle v_{0}}$${\displaystyle v_{0}}$${\displaystyle v_{0}}$

Например, давайте рассмотрим дерево соединений, построенное из набора локальных доменов, приведенного выше, т.е. набора из примера 1.
Теперь таблица планирования для этих доменов (где находится целевая вершина ).${\displaystyle p_{2}}$

${\displaystyle {\text{Round Message or State Computation}}}$
${\displaystyle 1.\mu _{8,4}(p_{4})=\alpha _{8}(p_{4})}$
${\displaystyle 2.\mu _{8,4}(p_{4})=\Sigma _{p_{2}}\alpha _{9}(p_{2},p_{4})}$
${\displaystyle 3.\mu _{5,2}(p_{3})=\alpha _{5}(p_{3})}$
${\displaystyle 4.\mu _{6,3}(p_{1})=\Sigma _{p_{4}}\alpha _{6}(p_{1},p_{4})}$
${\displaystyle 5.\mu _{7,3}(p_{1})=\alpha _{7}(p_{1})}$
${\displaystyle 6.\mu _{4,2}(p_{3})=\Sigma _{p_{4}}\alpha _{4}(p_{3},p_{4}).\mu _{8,4}(p_{4}).\mu _{9,4}(p_{4})}$
${\displaystyle 7.\mu _{3,1}(p_{2})=\Sigma _{p_{1}}\alpha _{3}(p_{2},p_{1}).\mu _{6,3}(p_{1}).\mu _{7,3}(p_{1})}$
${\displaystyle 8.\mu _{2,1}(p_{2})=\Sigma _{p_{3}}\alpha _{2}(p_{3},p_{2}).\mu _{4,2}(p_{3}).\mu _{5,2}(p_{3})}$
${\displaystyle 9.\sigma _{1}(p_{2})=\alpha _{1}(p_{2}).\mu _{2,1}(p_{2}).\mu _{3,1}(p_{2})}$

Таким образом, сложность GDL с одной вершиной может быть представлена ​​как

${\displaystyle \Sigma _{v}d(v)|A_{S_{(v)}}|}$ арифметические операции
Где (Примечание: объяснение приведенного выше уравнения объясняется позже в статье) - это метка . является степень от (то есть число вершин , смежных с v).
${\displaystyle S(v)}$${\displaystyle v}$
${\displaystyle d(v)}$${\displaystyle v}$

Чтобы решить проблему всех вершин , мы можем запланировать GDL несколькими способами, некоторые из них являются параллельной реализацией, когда в каждом раунде обновляется каждое состояние и каждое сообщение вычисляется и передается одновременно. В этом типе реализации состояния и сообщения будут стабилизироваться после количества раундов, которое не больше диаметра дерева. В этот момент все состояния вершин будут равны желаемой целевой функции.

Другой способ запланировать GDL для этой проблемы - последовательная реализация, аналогичная задаче с одной вершиной, за исключением того, что мы не останавливаем алгоритм до тех пор, пока все вершины требуемого набора не получат все сообщения от всех своих соседей и не вычислим их государственный.
Таким образом, количество арифметических операций, необходимых для этой реализации, составляет не более арифметических операций.${\displaystyle \Sigma _{v\in V}d(v)|A_{S_{(v)}}|}$

Построение дерева соединений [ править ]

Ключ к построению дерева соединений лежит в графе локальной области , который является взвешенным полным графом с вершинами, то есть по одной для каждой локальной области, имеющей вес ребра, определенный как . если , то мы говорим, что содержится в . Обозначается (вес остовного дерева максимального веса ), который определяется как${\displaystyle G_{LD}}$${\displaystyle M}$${\displaystyle v_{1},v_{2},v_{3},\ldots ,v_{M}}$${\displaystyle e_{i,j}:v_{i}\leftrightarrow v_{j}}$
${\displaystyle \omega _{i,j}=|S_{i}\cap S_{j}|}$
${\displaystyle x_{k}\in S_{i}\cap S_{j}}$${\displaystyle x_{k}}$${\displaystyle e_{i,j}}$${\displaystyle \omega _{max}}$${\displaystyle G_{LD}}$

${\displaystyle \omega ^{*}=\Sigma _{i=1}^{M}|S_{i}|-n}$

где n - количество элементов в этом наборе. Для большей ясности и подробностей обратитесь к ним. ^{[3] [4]}

Теорема расписания [ править ]

Позвольте быть деревом соединений с множеством вершин и множеством ребер . В этом алгоритме сообщения отправляются в обоих направлениях на любом ребре, поэтому мы можем сказать / рассматривать набор ребер E как набор упорядоченных пар вершин. Например, из рисунка 1 можно определить следующее${\displaystyle 'T'}$${\displaystyle 'V'}$${\displaystyle 'E'}$${\displaystyle 'E'}$

${\displaystyle E=\{(1,2),(2,1),(1,3),(3,1),(4,2),(2,4),(5,2),(2,5),(6,3),(3,6),(7,3),(3,7),(8,4),(4,8),(9,4),(4,9)\}}$

ПРИМЕЧАНИЕ: выше приведены все возможные направления, по которым сообщение может перемещаться в дереве.${\displaystyle E}$

Расписание для GDL определяется как конечная последовательность подмножеств . Что обычно обозначается как { }, где - набор сообщений, обновляемых во время цикла выполнения алгоритма.${\displaystyle E}$${\displaystyle {\mathcal {E}}=}$${\displaystyle E_{1},E_{2},E_{3},\ldots ,E_{N}}$${\displaystyle E_{N}}$${\displaystyle N^{th}}$

Определив / увидев некоторые обозначения, мы увидим, что в теореме говорится: когда нам дается расписание , соответствующая решетка сообщений представляет собой конечный ориентированный граф с множеством вершин , в котором типичный элемент обозначается как for , Затем после завершения передача сообщения, состояние в вершине будет целью, определенной в${\displaystyle {\mathcal {E}}=\{E_{1},E_{2},E_{3},\ldots ,E_{N}\}}$${\displaystyle V\times \{0,1,2,3,\ldots ,N\}}$${\displaystyle v_{i}(t)}$${\displaystyle t\in \{0,1,2,3,\ldots ,N\}}$${\displaystyle v_{j}}$${\displaystyle j^{\text{th}}}$

${\displaystyle \sigma (p_{S_{i}})=\alpha _{i}(p_{S_{i}})\prod _{v_{k}\operatorname {adj} v_{i}}\mu _{k,j}(p_{S_{k}\cap S_{i}})}$

и если есть путь от до${\displaystyle v_{i}(0)}$${\displaystyle v_{j}(N)}$

Вычислительная сложность [ править ]

Здесь мы пытаемся объяснить сложность решения задачи MPF с точки зрения количества математических операций, необходимых для расчета. т.е. мы сравниваем количество операций, требуемых при вычислении с использованием обычного метода (здесь под обычным методом мы подразумеваем методы, которые не используют передачу сообщений или деревья соединений в коротких методах, которые не используют концепции GDL) и количество операций, использующих обобщенный распределительный закон.

Пример: рассмотрим простейший случай, когда нам нужно вычислить следующее выражение .${\displaystyle ab+ac}$

Для наивной оценки этого выражения требуется два умножения и одно сложение. Выражение, выраженное с использованием закона распределения, может быть записано как простая оптимизация, которая сокращает количество операций до одного сложения и одного умножения.${\displaystyle a(b+c)}$

Подобно объясненному выше примеру, мы будем выражать уравнения в различных формах, чтобы выполнить как можно меньше операций с помощью GDL.

Как объяснялось в предыдущих разделах, мы решаем проблему, используя концепцию деревьев соединений. Оптимизация, полученная с помощью этих деревьев, сравнима с оптимизацией, полученной путем решения полугрупповой задачи на деревьях. Например, чтобы найти минимум группы чисел, мы можем заметить, что если у нас есть дерево и все элементы находятся в нижней части дерева, то мы можем сравнить минимум два элемента параллельно, и результирующий минимум будет написано родителю. Когда этот процесс распространяется вверх по дереву, минимум группы элементов будет находиться в корне.

Ниже приводится сложность решения дерева соединений с использованием передачи сообщений.

Перепишем использованную ранее формулу к следующему виду. Это уравнение для сообщения, которое должно быть отправлено из вершины v в w

${\displaystyle \mu _{v,w}(p_{v\cap w})=\sum _{p_{v\setminus w}\in A_{S(v)\setminus S(w)}}\alpha _{v}(p_{v})\prod _{uadjv_{u\neq v}}\mu _{u,v}(p_{u\cap v})}$ ---- уравнение сообщения

Аналогично перепишем уравнение для вычисления состояния вершины v следующим образом

${\displaystyle \sigma _{v}(p_{v})=\alpha _{v}(p_{v})\prod _{u\operatorname {adj} v}\mu _{v,w}(p_{v\cap w})}$

Сначала мы проанализируем проблему с одной вершиной и предположим, что целевая вершина есть, и, следовательно, у нас есть одно ребро от до . Предположим, у нас есть край, мы вычисляем сообщение, используя уравнение сообщения. Для расчета требуется${\displaystyle v_{0}}$${\displaystyle v}$${\displaystyle v_{0}}$${\displaystyle (v,w)}$${\displaystyle p_{u\cap v}}$

${\displaystyle q_{v\setminus w}-1}$

дополнения и

${\displaystyle q_{v\setminus w}(d(v)-1)}$

умножения.

(Мы представляем как .)${\displaystyle |A_{S(v)\ S(w)}|}$${\displaystyle q_{v\setminus w}}$

Но будет много возможностей для следовательно , возможностей . Таким образом, для всего сообщения потребуется${\displaystyle x_{v\cap w}}$
${\displaystyle q_{v\cap w}{\stackrel {\mathrm {def} }{=}}|A_{S(v)\cap S(w)}|}$${\displaystyle p_{v\cap w}}$

${\displaystyle (q_{v\cap w})(q_{v\setminus w}-1)=q_{v}-q_{v\cap w}}$

дополнения и

${\displaystyle (q_{v\cap w})q_{v\setminus w}.(d(v)-1)=(d(v)-1)q_{v}}$

умножения

Общее количество арифметических операций, необходимых для отправки сообщения по краям дерева, будет${\displaystyle v_{0}}$

${\displaystyle \sum _{v\neq v0}(q_{v}-q_{v\cap w})}$

дополнения и

${\displaystyle \sum _{v\neq v0}(d(v)-1)q_{v}}$

умножения.

После того, как все сообщения были переданы, алгоритм завершается вычислением состояния на этапе. Для вычисления состояния требуется больше умножений. Таким образом, количество вычислений, необходимых для расчета состояния, указано ниже.${\displaystyle v_{0}}$${\displaystyle d(v_{0})q_{0}}$

${\displaystyle \sum _{v\neq v_{0}}(q_{v}-q_{v\cap w})}$

дополнения и

${\displaystyle \sum _{v\neq v_{0}}(d(v)-1)q_{v}+d(v_{0})q_{v_{0}}}$

умножения

Таким образом, общее количество вычислений равно

${\displaystyle \chi (T)=\sum _{v\in V}d(v)q_{v}-\sum _{e\in E}q_{e}}$ ----${\displaystyle (1)}$

где - край и его размер определяется${\displaystyle e=(v,w)}$${\displaystyle q_{v\cap w}}$

Приведенная выше формула дает нам верхнюю границу.

Если мы определим сложность ребра как${\displaystyle e=(v,w)}$

${\displaystyle \chi (e)=q_{v}+q_{w}-q_{v\cap w}}$

Следовательно, можно записать как${\displaystyle (1)}$

${\displaystyle \chi (T)=\sum _{e\in E}\chi (e)}$

Теперь мы вычислим сложность ребра для задачи, определенной на рисунке 1, следующим образом

${\displaystyle \chi (1,2)=q_{2}+q_{2}q_{3}-q_{2}}$

${\displaystyle \chi (2,4)=q_{3}q_{4}+q_{2}q_{3}-q_{3}}$

${\displaystyle \chi (2,5)=q_{3}+q_{2}q_{3}-q_{3}}$

${\displaystyle \chi (4,8)=q_{4}+q_{3}q_{4}-q_{4}}$

${\displaystyle \chi (4,9)=q_{2}q_{4}+q_{3}q_{4}-q_{4}}$

${\displaystyle \chi (1,3)=q_{2}+q_{2}q_{1}-q_{2}}$

${\displaystyle \chi (3,7)=q_{1}+q_{1}q_{2}-q_{1}}$

${\displaystyle \chi (3,6)=q_{1}q_{4}+q_{1}q_{2}-q_{1}}$

Общая сложность будет значительно ниже по сравнению с прямым методом. (Здесь под прямым методом мы подразумеваем методы, которые не используют передачу сообщений. Время, затрачиваемое на использование прямого метода, будет эквивалентно вычислению сообщения в каждом узле и времени для вычисления состояния каждого из узлов.)${\displaystyle 3q_{2}q_{3}+3q_{3}q_{4}+3q_{1}q_{2}+q_{2}q_{4}+q_{1}q_{4}-q_{1}-q_{3}-q_{4}}$

Теперь мы рассмотрим задачу для всех вершин, где сообщение должно быть отправлено в обоих направлениях, а состояние должно быть вычислено в обеих вершинах. Это потребует, но с помощью предварительных вычислений мы можем уменьшить количество умножений до . Вот степень вершины. Пример: Если есть набор с числами. Можно вычислить все d продуктов из с в большинстве умножений , а не очевидный . Мы делаем это, предварительно вычисляя количества, и это требует умножения. Тогда если обозначает произведение всех, кроме того, что у нас есть, и так далее, потребуется еще одно умножение, дающее общее${\displaystyle O(\sum _{v}d(v)d(v)q_{v})}$${\displaystyle 3(d-2)}$${\displaystyle d}$${\displaystyle (a_{1},\ldots ,a_{d})}$${\displaystyle d}$${\displaystyle d-1}$${\displaystyle a_{i}}$${\displaystyle 3(d-2)}$${\displaystyle d(d-2)}$${\displaystyle b_{1}=a_{1},b_{2}=b_{1}\cdot a_{2}=a_{1}\cdot a_{2},b_{d-1}=b_{d-2}\cdot a_{d-1}=a_{1}a_{2}\cdots a_{d-1}}$${\displaystyle c_{d}=a_{d},c_{d-1}=a_{d-1}c_{d}=a_{d-1}\cdot a_{d},\ldots ,c_{2}=a_{2}\cdot c_{3}=a_{2}a_{3}\cdots a_{d}}$${\displaystyle 2(d-2)}$${\displaystyle m_{j}}$${\displaystyle a_{i}}$${\displaystyle a_{j}}$${\displaystyle m_{1}=c_{2},m_{2}=b_{1}\cdot c_{3}}$${\displaystyle d-2}$${\displaystyle 3(d-2)}$

Когда дело доходит до построения дерева соединений, мы мало что можем сделать, за исключением того, что у нас может быть много остовных деревьев с максимальным весом, и мы должны выбирать остовное дерево с наименьшими затратами, и иногда это может означать добавление локального домена для понижения соединения. сложность дерева.${\displaystyle \chi (T)}$

Может показаться, что GDL верен только тогда, когда локальные домены могут быть представлены в виде дерева соединений. Но даже в случаях, когда есть циклы и количество итераций, сообщения будут примерно равны целевой функции. Эксперименты с алгоритмом Галлагера – Таннера – Виберга для кодов с низкой плотностью проверки на четность подтвердили это утверждение.

Эта статья включает в себя список общих ссылок , но он остается в основном непроверенным, поскольку в нем отсутствуют соответствующие встроенные ссылки . Пожалуйста, помогите улучшить эту статью, добавив более точные цитаты. ( Июнь 2012 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

Ссылки [ править ]