Cтраница 4
Итак, надо построить дерево, которое содержит кратчайшие цепи из узла Ns во все остальные узлы сети. Дуги сети, принадлежащие этому дереву, будем называть дугами дерева, а дуги, не принадлежащие ему - дугами вне дерева. После того как дерево будет построено, каждая кратчайшая цепь будет состоять из дуг дерева. В начале алгоритма все дуги сети считаются дугами вне дерева. В процессе работы алгоритма количество дуг дерева постепенно увеличивается от 0 до п - 1, где п - число узлов данной сети. [46]
Идея приближенного алгоритма основана на объединении для подачи в один порт ввода тех переменных, которые являются аргументами большого количества булевых функций. Он основан на использовании частотной матрицы отношений. Матрица инцидентности Q задает систему булевых функций следующим образом: каждой строке соответствует логическая функция, а каждому столбцу - объединенное множество X. Первоначально Xi xi, т.е. столбцу соответствует переменная из множества X всех аргументов функций. В процессе работы алгоритма происходит постепенное объединение столбцов на основе эвристической оценки и образование нового объединенного множества X для сформированного столбца. При получении мощности объединенного множества, равного N, или невозможности объединения с другими столбец удаляется из рассмотрения. Процесс повторяется до тех пор, пока не останется только один столбец матрицы инцидентности. [47]