Сущность алгоритма решения задачи на графах

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

Т.к. теория графов оперирует с множествами (следует из определения графа: «Графом называется объект, состоящий из двух множеств, между элементами которых задан набор отношений»), то при формализации используются основные операции теории множеств, такие как:

· операции отношения (принадлежность, равенство, объединение …),

· двуместные отношения множеств (бинарное отношение, однозначное отображение, многозначное отображение, взаимнооднозначное соответствие, отношение эквивалентности, образ многозначного отображения элемента, упорядочивание множеств),

· основные операции математической логики,

· элементарные операции над графами:

- удаление вершины

- удаление ребра

- добавление вершины и инцендентного ему ребра

- добавление вершины в гиперграф

- добавление ребра

- свертка вершин

- свертка ребра инцендентного вершинам

- подразбиение ребра инцендентного вершинам

 

 

23. Разработка алгоритмической модели процесса решения задачи. Пример модели для решения задачи декомпозиции схемы по методу неуравновешенной двоичной свёртки.

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

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

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

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

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

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

Пример модели для решения задачи декомпозиции схемы по методу неуравновешенной двоичной свёртки

Общая электрическая схема ЭВМ состоит из функционально законченных блоков разной степени сложности. Т. е вся схема делится на ряд иерархических уровней, которые определяются отношением R функционального вхождения схем некоторого уровня иерархии в схемы следующего (в этом смысле схемы более низкого уровня иногда называют подсхемами). Критерием, в соответствии с которым определяют принадлежность подсхемы к некоторому уровню иерархии, является ее назначение и функциональная законченность: устройства выработки сигналов управления, преобразование информации, хранение данных и т. п. Первый уровень иерархии, например, при разработке матричных БИС, составляют элементы библиотеки функциональных ячеек: селекторы, мультиплексоры, схемы сложения по модулю 2, шифраторы, дешифраторы, триггера и т.д.

Графовая модель обобщенной структуры некоторого устройства ЭВТ(см рис.)

 

Моделью схемы (ЭВМ) является гиперграф H(X,Y), в котором множествам элементов Э и цепей С схемы поставлены во взаимно-однозначное соответствия множества вершин X и ребер U: Э ↔X C↔U.

 

 

Гиперграф задан множествами вершин Х и {x_i /i=1,n}, ребер U={u_j /j=1,m} и многозначными отображениями X в U-ГХ={Гx_i /i=1,n}и U в Х-ГU= {Гu_j /j=1,m}. Здесь Гx_i= U_i U – множество ребер, инцидентных вершине x_i (в схеме – множество цепей подходящих к элементу э_i), Гu_j= X_j X – множество вершин, инцидентных ребру u_j (в схеме – множество элементов, соединенных цепью с_j).

Идея свободной декомпозиции схемы соединения элементов заключается в следующем: начиная с первого уровня (количество элементов, подлежащих свертке, равно n), определяем показатели связности всех пар вершин гиперграфа, имеющих общие ребра, и объединяем максимально связанные вершины. Корректируем массивы Х, U, ГХ, ГU. При следующем повторении (количество вершин n-1) вновь подсчитываем показатели связности и ищем новую пару. Процесс заканчивается когда будут объединены две последние вершины.

Получим оценку вычислительной сложности в худшем. Для этого будем считать, что каждая вершина гиперграфа связана с каждой, а |Гx_i| = ρ-максимальному количеству выводов элемента схемы. Доминирующей операцией при оценке вычислительной сложности примем операцию сравнения. Подсчет показателя связности s(x_i,х_j) вершин x_i и х_j Х выполняется по формуле: s(x_i,х_j)=| U_i ∩ U_j|, где U_i = Гx_i, U_j = Гx_j, и требует ρ² операций сравнения элементов множеств U_i U и U_j U. Так как каждая вершина гиперграфа по предположению связана с каждой, то количество таких показателей для текущего шага t равно L=t(t-1)/2.

Тогда алгоритмическая модель процесса декомпозиции схемы по методу неуравновешенной свертки без учета коррекции массивов Х, U, ГХ и ГU будет иметь следующий вид:

Выполнить пп. 1-3 t= n,3.

1. i= 1,t-1, j= i+1,t подсчитываем S={ s_l /l= 1,L }, где s_l(x_i,х_j) =| U_i ∩ U_j|, L=t(t-1)/2

2. Находим s_p(x_k,х_r) = max{ s_l /l= 1,L }, такой, что s_p>0.

3. Объединяем в одну вершины x_k,х_r.

Количество операций сравнения для п.1=t(t-1)ρ²/2.

Выбор пары вершин с макс связностью для п2 потребует t(t-1)/2-1 сравнений.

Суммируя по t= 3,n получим f(n)= [ t(t-1)ρ²/2+ t(t-1)/2-1] пренебрегая константами с преобразуя получим f(n)=[ ρ²(n³-n)+(n³-7n)]/6 учитывая, что ρ-конечно (ρ ≤200), f(n)=О(n³). Для редакторов: оценка вычислительной сложности двоичной свертки возможно и не нужна.