Модификация алгоритма определения клик графа с параметрической адаптацией

Кликой графа называется максимальный полный подграф, который не входит ни в один полный подграф более высокого порядка /1/ .

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

Рассматривается класс нериентированных графов без петель и кратных ребер.

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

Основными факторами, влияющими на качество выполнения алгоритмов проектных операций, являются:

требуемая точность решения;

ресурс времени, отведенный на выполнение проектной операции;

размерность конкретной задачи.

Из указанных факторов известные приближенные методы позволяют учитывать только ограничение на время выполнения алгоритма - ресурс времени путем прерывания решения в момент его истечения /2/ .

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

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

2. Базовый алгоритм

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

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