Существует ли эффективный алгоритм поиска «максимального связного множества»? - PullRequest
Новая
       15

Существует ли эффективный алгоритм поиска «максимального связного множества»?

1 голос
/ 21 апреля 2019

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

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

enter image description here

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

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

В случае, если это поможет, моя цель - воспроизвести значения M n из таблицы I этой статьи: Sarwate, D.V., и M.B. Пурсли, "Кросскорреляционные свойства псевдослучайных и родственных последовательностей", Proc. IEEE, Vol. 68, No. 5, May 1980, pp. 583-619.

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

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

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

1 Ответ

4 голосов
/ 21 апреля 2019

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

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

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

...