Диссертация (Исследование и разработка методов автоматического вывода геометрических ограничений с использованием декларативного программирования и формальных методов), страница 12

Второй вариант является задачей оптимизации —в заданном графе требуется найти клику максимального размера. Задача поискаклик является N P -полной и, таким образом, эффективно алгоритма решения этойзадачи пока не обнаружено. Полный перебор всех подграфов с проверкой наполноту не может быть использован на практике — число клик размером k дляграфа с v вершинами равняется биномиальному коэффициенту:( )vv!=kk!(v − k)!В работе [87] рассмотрен метод ветвей–и–границ для поиска максимальнойклики или, что вычислительно эквивалентно, для поиска наибольшегонезависимого множества. В основе метода лежит стратегия удаления лишнихрешений через процедуру раскраски вершин графа.

Эффективность алгоритмаподтверждена при решении задач для случайных графов и на DIMACS набореграфов.Метод ветвей–и–границ используется и в работе [88] для поискамаксимальных клик. Предложенный алгоритм также использует в качествеоптимизации процедуру расскраски вершин графа, в данном случаеприближенную. Раскраска позволяет оценить верхнюю границу на размермаксимальной клики. Также используется сортировка вершин графа дляускроения процедуры поиска. Эспериментальные результаты показывают, чтопредложенный алгоритм обеспечивает наилучшую производительность поотношению к другим известным алгоритмам. Метод был применен к решениюпрактических задач в областях обработки изображений, проектировании СБИС,а также в молекулярной биологии.Первым алгоритмом перечисления максимальных клик считается алгоритмБрона-Кербоша [89].

Его особенностью является то, что время, требуемоеалгоритмом для поиска максимальных клик, зависит от их числа. Таким образом,вычислительные ресурсы, требуемые данному алгоритму, определяются нетолько размером входных данных, но и объемом выходных данных. В основеалгоритма лежит использование рекурсивного поиска с возвратами.Эквивалентной задаче перечисления максимальных клик графа являетсязадача поиска наибольших независимых множеств вершин графа. В работе [90]54предложен алгоритм перечисления максимальных независимых множеств,требующий O(nmµ) шагов и O(n + m) памяти, где n, m и µ число вершин, ребери число максимальных независимых множеств, соответственно.В работе [91] предлагается метод перечисления максимальных клик, воснове которого лежит модифицированный алгоритм Брона–Кербоша.

На первомэтапе рассматриваются ребра между вершинами, которые являются кликамиразмера 2. Затем подклики объединяются в максимальные клики при помощиалгоритма ветвления-и-границ. Немакисмальные клики при этом опускаются,что позволяет ускорить процедуру поиска. В статье разбираются как сходства салгоритмом Брона–Кербоша, так и различия. Приводится пример практическогоиспользования алгоритма в решении задач биохимии, а имеено в задачах анализаи визуализации метаболических процессов.Проблема перечисления максимальных клик возникает при решениипрактических задач теории графов, интеллектуального анализа данных ибиоинформатике. Экспоненциально растущие требования к вычислительнымресурсам известных алгоритмов перечисления ограничивают их применимостьпри решении актуальных задач разработки. Вместе с тем, современные проблемынередко могут быть описаны большими графами, включающими миллионывершин и ребер.

В работе [92] предлагается параллельный алгоритм перечислениямаксимальных клик графа, использующий ряд новых эвристик и оптимизаций.Эксперименты с использованием графа, содержащего 2423807 вершин и 5317183ребра демонстрируют, что данный алгоритм обладает высокой эффективностьюи хорошо масштабируется для задач высокой размерности.В работе [93] рассматривается метод перечисления всех максимальных кликграфа G, который содержит n вершин и m ребер.

В работе предлагается дваалгоритма. Первый из них требует O(M (n)) времени и O(n2 ) памяти, второйтребует O(∆4 ) времени и O(n + m) памяти, где ∆ обозначает максимальнуюстепень графа G, M (n) обозначает время, необходимое для перемножениядвух матриц размером n × n matrices. Последний алгоритм также требуетO(nm) времени для предварительной подготовки. Эксперименты показывают,что предложенные алгоритмы эффективно перечисляют максимальные клики какдля плотных, так и разреженных графов, в том числе для случайных графов играфов, построенных при решении практических задач.55В основе предложенного алгоритма лежит метод обратного поиска [94].Число шагов, требуемое алгоритму, полиномиально зависит от размера входныхданных и от количества найденных в результате объектов. Требуемый объемпамяти полиномиально зависит от размера входных данных. Также этот алгоритмхорошо поддается параллелизации за счет того, что ход выполнения может бытьестественным образом разделен на независимые подзадачи.Рассмотрим граф g, вершины которого соответствуют элементаммножества, которе необходимо перечислить.

Пусть также определена целеваяфункция, параметрами которой являются вершины g, и максимум которойнеобходимо найти. Также задана функция локального поиска, значение которойзависит от вершины графа g, которая движется по вершинам графа в направленииувеличения значения целевой функции. Данная процедура поиска должнабыть детерминированной и завершаться за конечное число шагов. Вершина снаибольшей стоимостью по сравнению со смежными вершинами, назваетсялокальным оптимумом. Примерами такой процедуры поиска может бытьсимплекс метод в линейном программировании, метод обмена ребрами дляпоиска минимального остовного дерева в взвешенных графах, алгоритмпереворота для построения триангуляции Делоне на плоскости. Стоит отметить,что симплекс метод в общем случае не является конечным, только прииспользовании определенных методов перехода к следующим вершинам,например, при рассмотрении метода Бланда.Пусть граф g содержит один локальный экстремум — вершина x∗ .Определим также ориентированный граф T , который содержит те же вершины,что и g, а множество ребер образовано упорядоченными парами вершин (x,x‘ ),которые были полученным при выполнении процедуры локального поиска.T , таким образом, является остовным деревом с единственным стоком x∗ .

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

T являетсядеревом.Описанная процедура может быть использована при решении различныхзадач комбинаторики. Важно отметить, что любая вершина y являющаясяпотомком x в дереве T , имеет меньшее значение целевой функции, чем x. Пусть56стоит задача найти такую вершину в T , которая удовлетворяет дополнительноеограничение (например, целочисленность) с наибольшим значением целевойфункции.

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

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

Пусть A — матрица смежностидля графа g, в которой значение элемента ai,j равно 1, если между вершинамиvi ,vj есть ребро, иначе оно равно 0. Для каждой вершины также определеномножество смежных вершин Γ(vi ) и определена степень δ(vi )— число вершин,смежных с заданной. Множество вершин K ⊆ V называется кликой, есливсе вершины в K попарно смежные; максимальной кликой называется такойполный подграф, который не является частью другого полного подграфа.Пусть K0 — максимальная клика, лексографически наибольшая среди всехмаксимальных клик. Для клики K определим C(K) — максимальную клику,которая лексографически больше всех максимальных клик, включающих K.C(K) не может быть лексографически меньше, чем K.

Для максимальной кликиK (за исключением K0 ) определим предка P (K) как C(K≤i−1 ) таким образом, чтоi является максимальным индексом, удовлетворяющим следующее ограничение:C(K≤i−1 ) ̸= KТакой индекс i называется родительским индексом и обозначается i(K).Так как P (K) лексографически больше, чем K, то такое отношение “родитель–потомок” для максимальных клик является ациклическим и образует дерево с57корнем в K0 .

Такое дерево называется “деревом перечисления”. Методы обходатакого дерева рассматриваются в работах [90; 95]. Для обхода заданного дереваперечисления необходимо найти предка (максимальную клику) и вычислить егопотомков.Предок P (K) может быть вычислен за линейное время при известной кликеK. Обратная задача, поиск потоком для заданной клики K, более трудоемкая.Для максимальной клики K и соответствующего индекса i определим следующееотношение, в котором Γ(vi ) — множество вершин, смежных с вершиной vi :K[i] = C((Ki ∩ Γ(vi )) ∪ {vi })′Максимальная клика K может быть потомком K тогда и только тогда, когдаK ‘ = K[i] является истиной для такого i, что:1. vi ∈/K2.