Алгоритм/приближение для комбинированного независимого расстояния/расстояния хамминга

Question

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

С тех пор, как здесь было вызвано разъяснение, еще одна рефразальная:

Разделите заданный график на наборы, чтобы

1. Я могу рассказать узел от всех других по его членству в наборах, например, если узел I присутствует только в наборе, не должен присутствовать ни один другой узел.

   Если узел J присутствует в Set A и B, то другой узел не должен присутствовать только в наборе A и B. Если членство в узлах кодируется бит -шаблоном, то эти битовые паттерны имеют расстояние хамминга, по крайней мере, один

2. Если на графике прилегают два узла, они не должны присутствовать в одном и том же наборе, поэтому быть независимым набором

Пример: B не имеет соседних узлов d => a, a => d

Решение:

1. АБ /
2. / Bd

A имеет бит -шаблон 10 и нет соседнего узла в его наборе. B имеет бит -шаблон 11, и нет смежного узла, D имеет 01, поэтому все узлы имеют расстояние хамминга, по крайней мере, 1 А и соседние узлы => правильно

Неправильно, потому что D и A связаны:

1. Адвокат
2. / ДБ

A имеет бит -шаблон 10 и D в его наборе, они смежные. B имеет бит -шаблон 11, и нет смежного узла, D имеет 11 как есть B, поэтому в этом решении есть две ошибки, и поэтому он не принимается.

Конечно, это должно быть расширено до большего количества наборов по мере увеличения количества узлов на графике, поскольку вам нужно, по крайней мере, log(n) наборы.

Я уже написал преобразование в Max-Sat, чтобы использовать для этого SAT-Solver. Но количество положений просто для больших. Более прямой подход был бы неплохо. До сих пор у меня есть приближение, но мне бы хотелось точное решение или, по крайней мере, лучшее приближение.

Я попробовал подход, когда я использовал рой частицы, чтобы оптимизировать произвольное решение для лучшего. Однако время бега довольно ужасно, и результаты далеко не велики. Я ищу динамический алгоритм или что -то в этом роде, однако я не могу понять, как разделить и победить эту проблему.

Answer 1

Не полный ответ, и я не знаю, насколько это будет полезно для вас. Но вот идет:

Расстояние Хэминга поражает меня как красную сельдь. В вашем заявлении о проблеме говорится, что это должно быть не менее 1, но это может быть 1000. Достаточно сказать, что битовое кодирование для набора членов каждого узла является уникальным.

Ваше заявление о проблеме не соблюдает это, но ваше решение выше предполагает, что каждый узел должен быть членом как минимум 1 набора. т.е. Немного кодирования всех 0 не разрешено для набора узлов.

Игнорируя подключенные узлы на мгновение, непересеченные узлы просты: просто примечайте их последовательно с помощью неиспользованного битового кодирования. Сохраните их на последнее время.

В вашем примере выше используются направленные края, но опять же, это поражает меня как красную сельдь. Если A не может быть в том же наборе, что и D, потому что a => d, D не может быть в том же наборе, что и D => a.

Вы упомянули, что нужно, по крайней мере, наборы log (n). У вас также будет больше n наборов. Полностью подключенный график (с (n^2-n)/2 неопределенные ребра) потребует n наборов, которые содержат один узел.

Фактически, если ваш график содержит полностью подключенное простое простое измерения M (M в 1..N-1) с вершинами M+1 и (M^2+M)/2 Недоверенные ребра, вам потребуется как минимум M+1 наборы.

В вашем примере выше у вас есть один такой Simplex (m = 1) с 2 вершинами {a, d} и 1 (неправомерный) Edge {(a, d)}.

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

Первый большой Simplex найден легко. Каждый узел вершины получает новый набор со своим битом.

Несоответствующие узлы просты. После того, как подключенные узлы справляются, просто числите непересекающиеся узлы последовательно пропустить любые ранее используемые битовые шаблоны. Из вашего примера выше, поскольку A и D принимают 01 и 10, следующий доступный бит для B составляет 11.

Тогда сложной частью становится как можно больше сложить оставшиеся только простоты в существующий диапазон, прежде чем создавать какие -либо новые наборы с новыми битами. При складывании необходимо использовать 2 или более битов (наборов) для каждого узла, а биты (наборы) не должны пересекаться с битами (наборы) для любого смежного узла.

Подумайте, что происходит с вашим примером выше, когда один добавляет другой узел, C, к примеру:

Если C подключается непосредственно как к A, так и к D, то начальная проблема становится нахождением 2-симплекса с 3 вершинами {a, c, d} и 3 края {(a, c), (a, d), (c, d )}. После того, как A, C и D возьмут битовые узоры 001, 010 и 100, самый низкий доступный бит -шаблон для Dis -Necoint B - 011.

Если, с другой стороны, C подключает непосредственно A или D, но не оба, график имеет два 1-симплекса. Предположим, что мы находим 1-симплекс с вершинами {a, D}, сначала давая им битовые шаблоны 01 и 10, то проблема становится, как сложить C в этот диапазон. Единственный бит -шаблон, по крайней мере, с 2 битами, составляет 11, но он пересекается с тем, к каким узлу C подключается, поэтому мы должны создать новый набор и поместить в него C. На этом этапе решение похоже на приведенное выше.

Если C не смешан, либо B или C получит бит -шаблон 11, а оставшуюся часть понадобится новый набор и получит бит -шаблон 100.

Предположим, что C подключается к B, но не к или D., опять же, график имеет два 1-симплекса, но на этот раз не смешан. Предположим, что {a, d} найдено сначала, как указано выше, давая и D битовые шаблоны 10 и 01. Мы можем сложить B или C в существующий диапазон. Единственный доступный битовой рисунок в диапазоне - 11, и B или C могут получить этот шаблон, так как ни один из них не находится рядом с или D. после использования 11, не остается ни одного бита с 2 или более битами, и нам придется создать Новый набор для оставшегося узла, придающего ему битовый шаблон 100.

Предположим, что C соединяется со всеми 3 A, B и D. В этом случае график имеет 2-симплекс с 3 вершинами {A, C, D} и 1-Simplex с 2 вершинами {B, C}. Работа, как указано выше, после обработки самого большого Simplex, A, C и D будут иметь битовые шаблоны 001, 010, 100. Для складывания B в этот диапазон доступные битовые шаблоны с 2 или более набора битов: 011, 101, 110 и 111. Все это, кроме 101 пересечения с C, поэтому B получит бит -шаблон 101.

Тогда возникает вопрос: Насколько эффективно вы можете найти самые большие полностью подключенные простоты?

Если найти самый большой полностью подключенный Simplex слишком дорого, можно было бы установить приблизительную верхнюю границу на потенциальных полностью подключенных символах, обнаружив максимальные минимумы с точки зрения соединений:

1. Проверьте края, обновляя вершины с подсчетом соединительных краев.

2. Для каждого подключенного узла создайте массив CN -количества счетов изначально нулевым, где CN - это количество краев, подключенных к узлу N.

3. Снова разверните края, для подключенных узлов n1 и n2 увеличивает счет в N1, соответствующем CN2 и наоборот. Если CN2> CN1, обновите последний счет в массиве N1 и наоборот.

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

5. Работайте через массив голубей с наибольшим до самых маленьких извлечения и складных узлов в уникальные наборы.

Если ваши узлы находятся в наборе n и ваших краях в наборе E, сложность будет: O (| n |+| e |+O (шаг 5))

Если вышеупомянутое приближение достаточно, вопрос становится: Насколько эффективно вы можете сложить узлы в существующие диапазоны, учитывая требования?

Answer 2

Возможно, это не тот ответ, который вы можете ожидать, но я не могу найти место, чтобы добавить комментарий. Поэтому я набираю его прямо здесь. Я не могу полностью понять ваш вопрос. Или для понимания нужны конкретные знания? Что это за независимый набор? Как я знаю, узел в независимом наборе с направленного графика имеет двухсторонний путь к любому другому узлу в этом наборе. Ваше понятие такое же?

Если эта проблема похожа на то, что я предполагаю, независимые наборы могут быть найдены с помощью этого алгоритма: 1. Поиск по глубине на направленном графике записывает время дерева, корняющегося этим узлом, проходит. 2. Затем поверните все ребра на этом графике 3. Снова выполните поиск по глубине на модифицированном графике. Алгорихтм точно объясняется книгой "Введение в алогрим"