Не полный ответ, и я не знаю, насколько это будет полезно для вас. Но здесь идет:
Расстояние Хэмминга поражает меня как красная сельдь. В вашем заявлении о проблеме говорится, что оно должно быть не меньше 1, но может быть 1000. Достаточно сказать, что битовая кодировка для набора членства каждого узла уникальна.
В вашем заявлении о проблеме это не прописано, но ваше решение выше предполагает, что каждый узел должен быть членом хотя бы одного набора. то есть. битовое кодирование всех 0 недопустимо для любого членства в наборе узлов.
Игнорируя подключенные узлы на мгновение, непересекающиеся узлы легко: просто нумеруйте их последовательно с помощью неиспользуемой битовой кодировки. Сохраните их на последний раз.
В приведенном выше примере используются направленные ребра, но опять же, это выглядит как красная сельдь. Если A не может быть в том же наборе, что и D, потому что A => D, D не может быть в том же наборе, что и A, независимо от того, D => A.
Вы упоминаете, что вам нужно хотя бы log (N) наборов. У вас также будет максимум N комплектов. Для полностью связного графа (с (N ^ 2-N) / 2 ненаправленными ребрами) потребуется N множеств, каждый из которых содержит один узел.
На самом деле, если ваш граф содержит полностью связный симплекс из M измерений (M в 1..N-1) с M + 1 вершинами и (M ^ 2 + M) / 2 ненаправленными ребрами, вам потребуется как минимум М + 1 компл.
В приведенном выше примере у вас есть один такой симплекс (M = 1) с 2 вершинами {A, D} и 1 (ненаправленным) ребром {(A, D)}.
Казалось бы, ваша проблема сводится к поиску самых больших полностью связанных симплексов в вашем графе. Другими словами, у вас есть проблема с маршрутизацией: сколько измерений вам нужно, чтобы выровнять ребра, чтобы они не пересекались? Это не похоже на очень масштабируемую проблему.
Первый найденный большой симплекс прост. Каждый вершинный узел получает новый набор со своим собственным битом.
Несвязные узлы просты. Как только с подключенными узлами разбираются, просто нумеруйте непересекающиеся узлы, последовательно пропуская любые ранее использованные битовые комбинации. Из приведенного выше примера, поскольку A и D берут 01 и 10, следующая доступная битовая комбинация для B равна 11.
Затем возникает сложная задача: как можно сложить как можно больше оставшихся симплексов в существующий диапазон, прежде чем создавать новые наборы с новыми битами. При свертывании необходимо использовать 2 или более битов (наборов) для каждого узла, и биты (наборы) не должны пересекаться с битами (наборами) для любого соседнего узла.
Рассмотрим, что происходит с вашим примером выше, когда вы добавляете другой узел C в пример:
Если C соединяется напрямую как с A, так и с D, то исходной проблемой становится поиск 2-симплекса с 3 вершинами {A, C, D} и 3 ребрами {(A, c), (A, D), ( CD)}. Как только A, C и D принимают битовые комбинации 001, 010 и 100, наименьшая доступная битовая комбинация для непересекающегося B равна 011.
Если, с другой стороны, C соединяет непосредственно A или D, но не оба, граф имеет два 1-симплекса. Предположим, что мы находим 1-симплекс с вершинами {A, D}, сначала дающими им битовые комбинации 01 и 10, затем возникает проблема, как сложить C в этот диапазон. Единственным битовым шаблоном, по крайней мере, с 2 битами, является 11, но он пересекается с любым узлом C, к которому подключается, поэтому мы должны создать новый набор и поместить в него C. На данный момент решение похоже на приведенное выше.
Если C не пересекается, либо B, либо C получат битовую комбинацию 11, а оставшейся потребуется новый набор и битовая комбинация 100.
Предположим, что C соединяется с B, но не с A или D. Снова граф имеет два 1-симплекса, но на этот раз не пересекается. Предположим, что {A, D} находится первым, как указано выше, давая A и D битовые комбинации 10 и 01. Мы можем сложить B или C в существующий диапазон. Единственный доступный битовый шаблон в диапазоне - 11, и B или C может получить этот шаблон, поскольку ни один из них не является смежным с A или D. После использования 11 битовые комбинации с установленным 2 или более битами не останутся, и нам придется создавать новый набор для оставшегося узла, дающий ему битовую комбинацию 100.
Предположим, что C соединяется со всеми 3 A, B и D. В этом случае граф имеет 2-симплекс с 3 вершинами {A, C, D} и 1-симплекс с 2 вершинами {B, C}. Действуя, как описано выше, после обработки наибольшего симплекса, A, C и D будут иметь битовые комбинации 001, 010, 100. Для сворачивания B в этот диапазон доступные битовые комбинации с установленными 2 или более битами: 011, 101, 110 и 111. Все они, кроме 101, пересекаются с C, так что B получит битовую комбинацию 101.
Тогда возникает вопрос: Насколько эффективно вы можете найти самые большие полностью связные симплексы?
Если найти самый большой полностью связный симплекс слишком дорого , можно установить приблизительную верхнюю границу для потенциальных полностью связных симплексов, найдя максимальные минимумы в терминах соединений:
Прокрутите края, обновляя
вершины с подсчетом
соединительные кромки.
Для каждого подключенного узла создайте массив из Cn с начальным нулем
где Cn - количество ребер
подключен к узлу n.
Снова проведите края, для подключенных узлов n1 и n2,
увеличить счетчик в n1
соответствует Cn2 и наоборот.
Если Cn2> Cn1, обновите последний счет
в массиве n1 и наоборот.
Снова проведите через соединенные узлы, рассчитав верхнюю границу
самый большой симплекс каждый узел может
быть частью. Вы можете построить массив голубиных отверстий со списком вершин
для каждой верхней границы при прохождении через узлы.
Пройдите через массив голубиных отверстий от самого большого до самого маленького извлечения и
складывание узлов в уникальные наборы.
Если ваши узлы находятся в наборе N, а ваши ребра в множестве E, сложность будет:
O (| N | + | E | + O (Шаг 5))
Если вышеуказанного приближения достаточно, возникает вопрос: Насколько эффективно вы можете сложить узлы в существующие диапазоны с учетом требований?