Блог

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

Пример с 6 узлами:

В этом случае «максимальное связное множество» равно {node1, node4, node5}. Хотя node0 подключен к node2 и node3, node2 и node3 не подключены, поэтому не образуют «связный набор».

Это небольшой пример, но меня интересует общий алгоритм, который в принципе может быть применен к очень большим таблицам.

В случае, если это поможет, моя цель — воспроизвести значения mn из таблицы I этой статьи: Сарвейт, Д.В. и М.Б. Персли, «Свойства взаимной корреляции псевдослучайных и связанных последовательностей», Proc. IEEE, том 68, № 5, май 1980 г., стр. 583-619.

Я буду кодировать это в MATLAB, но также довольно свободно владею C / C .

РЕДАКТИРОВАТЬ: вот таблица, из которой я хочу воспроизвести результаты:

• 1-й и 2-й столбцы здесь не очень важны (просто опишите длины кодов).
• 3-й столбец — это то, что я назвал количеством «узлов».
• 4-й столбец является мерой ошибки, если вы используете все узлы (независимо от того, «подключены» они или нет).
• 6-й столбец является (минимальной) ошибкой, если используется только «максимальный связанный набор».
• 5-й столбец, mn описывает количество узлов в максимальном связном множестве.

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

«Максимальная клика» — это именно то, что вы описали: наибольшее подмножество узлов графа, которые таковы, что каждый узел связан со всеми другими.

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