вычисление «закрытия узла» графа с удалением

Question

Учитывая ориентированный граф, цель состоит в том, чтобы объединить узел с узлами, на которые он указывает, и придумать минимум число из них [дает имя] супер узлы.

Уловка, когда вы объединяете узлы, вы не можете снова использовать эти узлы. [первый узел, а также все объединенные узлы - все члены одного суперузел]

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

Жадный - это O (V), но это не обязательно выводит минимальное число супер узлов. Так какой лучший алгоритм для этого?

Answer 1

20! довольно большой, больше 2^61. К счастью, есть лучший способ решить небольшие экземпляры: (EDIT) динамическое программирование. Сохраняя оптимальные решения для каждой подзадачи, мы платим некоторую память, чтобы получить очень большую экономию времени.

Вот пример кода в Python. При реализации кода ниже на другом языке вы, вероятно, захотите присвоить вершинам 0, ..., n-1 и реализовать наборы как битовые векторы.

# find a smallest node closure of G 
# G is a graph in adjacency-list format: G[v] is the set of neighbors of v 
def node_closure(G): 
    # maps subsets of vertices to their smallest node closure 
    smallest = {frozenset(): []} 
    def find_smallest(S): 
     if S in smallest: 
      return smallest[S] 
     else: 
      candidates = [[v] + find_smallest(S - frozenset([v]) - G[v]) for v in S] 
      return min(candidates, key=len) 
    return find_smallest(frozenset(G)) 

---

Эта проблема имеет сокращение к NP-твердость от множества крышки , который сохраняет значение целевой. Это означает, что если P = NP, лучшей гарантией, которую вы можете получить для алгоритма с полиномиальным временем, является то, что он всегда выводит решение, которое не более O(log n) раз больше оптимального.

Если x1, ..., xm являются элементы, которые будут покрыты и S1, ..., Sn являются множествами, то цель набора крышки выбрать минимальное число множеств, объединение которых является {x1, ..., xm}. Если предположить, что каждый элемент появляется, по крайней мере, один набор, сделать граф с узлами x1, ..., xm, S1, ..., Sn, R где есть дуги от R ко всему Si и для всех i, j, дуга от Si к xj тогда и только тогда, когда xj принадлежит Si. Существует прямая связь между закрытием узлов и наборами обложек: для получения закрытия узла из набора обложки удалите вершины, соответствующие выбранным наборам, а затем R; для получения набора обложки из удержания узла, возьмем все множества, вершины которых были выбраны плюс множества, содержащие каждый xj, вершина которого выбрана.

(Примечание для набора крышки, жадный алгоритм достигает оптимальное соотношение приближения! Нечто подобное может быть верно для вашей проблемы.)

Answer 2

Я попытаюсь охарактеризовать проблему по-другому. Вы хотите разделить вершины на две группы. Первая группа состоит из «корневых узлов», а вторая из «зависимых узлов», то есть узлов, напрямую связанных с корневыми узлами.

  root  dependent 
        B 
      A < 
        C 

        E 
      D < 
        F 

^{Рис. 0: Возможный граф результатов.}

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

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

Если мы рассматриваем каждое ребро как имеющее возможный статус «неизвестно», «берем» или «удаляем», взятие ребра удаляет все ребра, исходящие из его конечного узла, а также все ребра, оканчивающиеся на него (см. Рис. 1). Тем не менее, мы можем сохранить не более одного края, заканчивающегося на определенном узле.

 A B C 
    \|/ 
     D 
    /|\ 
    E F G

^{Рис 1: Взятие край A-D удаляет все остальные ребра отображаемых здесь.}

Есть целый ряд «жадной» эвристика:

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

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

• Put узла с наиболее исходящими соединениями в корень установить и пометить все связанные узлы как «достижимые». Затем цикл, но только подсчет соединений с узлами, которые не достижимы в каждой точке. Остановитесь, когда все узлы находятся в корневом наборе или «достижимы».Наконец, поместите все «достижимые» узлы, которые не входят в набор корней в зависимый набор, и произвольно распределяют их между корневыми узлами, к которым они могут быть подключены.

Это выглядит вполне нормально, но все же не обязательно оптимально. Возможно, вы можете начать с другой стороны:

• Поместите узел с наименьшим количеством исходящих соединений в зависимый набор. «Удалить» все его исходящие края. «Возьмите» свой входящий фронт, который исходит от узла с наибольшим количеством исходящих соединений и поместите этот узел в корневой набор. Петля, пока все узлы не будут в корневом или зависимом множестве.

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