ЗМК - задача о максимальной клике, относится к классу NP-сложных задач. Предлагается отличный от имеющихся способ её решения.
Данный алгоритм использует большое число связанных между собой по каналу связи микропроцессоров (МП). Идея в том, что «каждый узел (вершина) сам кузнец своей клики», а затем микропроцессор-арбитр выбирает максимальную(ые) клику(и).
Задачу параллельно решают N микропроцессоров вершин и один микропроцессор-арбитр.
Задачу можно рассматривать в двух формулировках:
- когда известны связи каждой вершины графа;
- когда связи каждой вершины графа надо установить.
Второй вариант задачи сводится к первому введением дополнительного этапа решения: вершины графа обмениваются сообщениями с целью определения наличия связующих рёбер. Время, затрачиваемое на эту работу, равно:
Т0 = tо (N - 1), где tо – время обмена между двумя вершинами «запрос-ответ».
На этом этапе время, затрачиваемое i-ой вершиной, равно
ti = tв* (N-i)+(i – 1)* tс, tв – время, необходимое для определения того, связаны ли 2 вершины, i-ой вершиной, tс – время на обработку сообщения от вершины с меньшим номером. Общее время i-го этапа:
Т0 = tв* (N - 1) + tс (N - 1) = (tв + tс) (N - 1).
После окончания дополнительного этапа (или, если он отсутствует, в начале решения задачи) у каждой вершины имеется битовая шкала, в которой каждой из оставшихся вершин соответствует 1 бит (0 – связи между вершинами нет, 1 – связь есть).
Затем, на первом/втором этапе, каждая вершина обменивается битовыми шкалами с теми вершинами, смежными с ней, номера которых больше, чем её номер, то есть i-я вершина обменивается с вершинами j={i+1, ..., N|j-я вершина смежная с i-й}, и, получив их битовые шкалы, по логическому «И» складывает со своей (если 2 вершины входят в одну и ту же клику, у них части шкал должны совпадать. Подсчитывается число единиц в результате, и по их числу результат распределяется в элемент массива [k,m], k – предполагаемое число элементов в клике, m - № клики с числом элементов k, обнаруженной - iй вершиной. Время выполнения этого этапа (tо – время обмена шкалами с одной вершиной, tсл.ш – время сложения шкал с каждым из абонентов, tкл. – время сравнения результатов сложения шкал для выявления различных клик, , tрез. – время отправки результата арбитру, tвст. – время вставки полученного арбитром результата в список клик, формула для полносвязного графа):
T1 <= (tо+ tсл.ш) *(N - 1) + tкл.*( N - 1) = (tо+ tсл.ш + tкл.) *(N - 1)+ (tрез. + tвст.)* N
Получив результат от очередной вершины, микропроцессор-арбитр просматривает полученные сведения о кликах с целью выявления различных клик, возможно, равной величины(мощности). Арбитр осуществляет вставку результата в список клик и сравнение новой клики с имеющимися (список формируется, если требуется найти все клики, а не только максимальную).
При наличии k различных клик равной величины результатом являются все они.
При определении клики в случае ненаправленного графа вершины посылают сообщения только вершинам с бОльшими номерами.
Объём памяти данных, содержащих сведения о связности графа, равен N/8*N байтов для каждого МП (N/8 – число байтов на битовую шкалу задачи, N – число шкал в памяти МП) В случае разреженных матриц возможно отображение множества реально существующих вершин на множество теоретически возможных.
Таким образом, общее время решения задачи составляет О(N).
Особенностью данного алгоритма является использование концепции активных данных (патент РФ № 2477884). При этом требуется большое количество МП с соответствующей периферией. В качестве таких МП предлагается использовать:
- смартфоны пользователей мобильной сети по технологии smartgrid.
- суперкомпьютер в режиме ОКМД.