Детальная проработка алгоритма. Способы снижения вычислительной сложности алгоритмов. (Проиллюстрировать примерами)

Детальное описание алгоритма – это основные исходные данные для составления программы.

Детальное описание алгоритма:

• должно включать все операции – так как трудно рассчитывать, что программист в такой же степени, как и Вы, владеет аппаратом математической логики и теории графов, так же хорошо ориентируется в содержательной и формальной постановке Вашей задачи и сможет восстановить опущенные Вами операции;

• должно содержать подробные комментарии – для облегчения понимания формального описания алгоритма на языке теории множеств, математической логики и теории графов;

• может быть представлено в виде схемы – для наглядности представления структуры алгоритма;

• представлять операции над графами в максимально возможном приближении к конструкциям (операторам) выбранного языка программирования;

• должно строиться в соответствии с принципами структурного программирования.

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

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

Выч. сложность алгоритма зависит от: корректности формальной постановки задачи; метода решения задачи; операций преобразования модели исходного описания объекта проектирования; формы представления графа множествами; способа задания множества (подмножества); структур данных для представления множеств и графов.

Выбор операции преобразования. Способ декларирует выбор эффективных операций при формировании решений.

Так, задачу построения минимального остовного дерева можно решать удалением ребер максимальной длины из заданного графа G исх. или добавлением ребер минимальной длины в граф G 0(X, Æ).

• удаление ребра допустимо, если граф сохраняет связность, проверка связности графа выполняется алгоритмом свертки со сложностью O (n). С учетом того, что количество удаляемых ребер k = m - n +1, где m = n (n -1)/2, асимптотическая оценка вычислительной сложности алгоритма O (n ³).

• добавление ребра допустимо, если при этом не образуется цикл, что для ребра u (xi, xj), в котором xi Î X′;, где X′; – множество вершин строящегося дерева до присоединения к нему ребра u (xi, xj), требует проверки условия xj Ï X′;. С учетом того, что количество добавляемых ребер равно n -1, в итоге получаем оценку O (n 2), а при представлении X′; характеристическим вектором – O (n).

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

2) применение рекуррентных формул для расчета критериев и/или оценочных функций; 3) исключение повторного расчета критериев и/или оценочных функций в тех случаях, когда они в результате выполненного преобразования модели не меняются; 4) исключение подсчета критериев и/или оценочных функций для тех компонентов графов, для которых предикат определяющего отношения принимает значение «ложь» (алгоритм свертки и итерационный алгоритм компоновки);

5) замена объединения множеств конкатенацией, если объединяемые множества не пересекаются. Способ базируется на том, что при объединении непересекающихся подмножеств нет необходимости проверять совпадают ли их элементы. Т. е. A Ç B = Æ® A È B = A. B, что позволяет снизить вычислительную сложность этой операции с O(n 2) до O(n) при представлении множеств векторами и до O(1) при представлении списками с указателями их начала и конца. Следует однако помнить, что во втором случае множество B не сохраняется; 6) использование предикатов или соответствующих им отношений для формального задания таких связей между множествами и / или их элементами, которые позволяют снизить вычислительную сложность операций над ними. Например, вектора специальных признаков для определения принадлежности элементов множества тому или иному подмножеству его разбиения (алгоритм Краскала [Ахо]. Вычислительная сложность слияния n компонент, каждая из которых содержала по одному элементу, равна O(n 2). При использовании данного способа она снижается до O(n ´ logn);

7) замена операции определения X 2 как дополнения подмножества X 1 до X операцией дополнения подмножества Xi (элемента xi) до подмножества X 2:

X 2 = X \ X 1 ~ X 2 = X 2 \ Xi или в частном случае X 2 = X \ X 1 ~ X 2 = X 2 \ xi,

если до выполнения операции X 2 = X \ X 1 множество X 1 определялось как X 1 = X 1 · Xi (X 1 = X 1 · xi). Вычислительная сложность снижается с ½ X ½´½ X 1½ до ½ X 2½´½ Xi ½. Так как ½ X ½>½ X 2½ и ½ X 1½ > ½ Xi ½, данное преобразование целесообразно при любых условиях. Оно легко может быть сформулировано в виде формального правила.

8) удаление элемента несортированного множества при представлении его вектором посредством замещения этого элемента последним или первым. 9) Замена выражений алгебры подмножеств логически эквивалентными и требующим меньшего количества операций для их реализации. В этом способе целесообразно выделить две группы:

– заменяемые и заменяющие выражения состоят из одних и тех же подмножеств;

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

К первой группе относиться, например:

– замена выражения вида A à B · C, где C Í A (C Ì A) на конструкцию вида A \ C à B, где à – операция строгого или не строгого включения;

– использование для определения состава некоторого подмножества вместо выражения A \ { B È C } или A \ { B · C } выражения A \ B \ C, где A, B, C Ì U, в частном случае B, C Ì A. В качестве примера преобразований второй группы можно привести замену выражений xi Î X 1 на xi Ï X 2, Xi Ì X 1 на Xi Ë X 2(Xi Ç X 2 = Æ) и Xi Ç X 1 = Æ на xi Î X 2, если X 2 = X \ X 1, | X 1| > | X 2|, xi Î X или Xi Ì X.;

Эффективность преобразования первой группы рассмотрим на примере операции строгого включения.. Эквивалентность выражения A Ì B · C, где C Í A (C Ì A), выражению A \ C Ì B очевидна. Количество сравнений элементов множеств A, B, и C равно kop 1 = ï A ï ´ (ï B ï + ï C ï). Для выражения A \ C Í B количество операций сравнения kop 2 = ï A ï ´ ï C ï + (ï A ï – ï C ï) ´ ï B ï. Т. е. kop 1– kop 2 = ï B ï ´ ï C ï.