Временная сложность перечисления n-вершинного подграфа - PullRequest
Новая
       30

Временная сложность перечисления n-вершинного подграфа

3 голосов
/ 29 мая 2011

У меня есть алгоритм для создания списка всех возможных подграфов в P вершинах через данную вершину. Это не идеально но я думаю, что это должно работать хорошо. Проблема в том, что я теряюсь, когда пытаюсь вычислить сложность его времени.

Я придумал что-то вроде T(p) = 2^d + 2^d * (n * T(p-1) ), где d=Δ(G), p=#vertices required, n=|V|. Это действительно просто предположение. Кто-нибудь может мне помочь с этим?

Используемый алгоритм powerSet () должен быть O(2^d) или O(d*2^d). 

private void connectedGraphsOnNVertices(int n, Set<Node> connectedSoFar, Set<Node> neighbours, List<Set<Node>> graphList) {
    if (n==1) return;

    for (Set<Node> combination : powerSet(neighbours)) {
        if (connectedSoFar.size() + combination.size() > n || combination.size() == 0) {
            continue;
        } else if (connectedSoFar.size() + combination.size() == n) {
            Set<Node> newGraph = new HashSet<Node>();
            newGraph.addAll(connectedSoFar);
            newGraph.addAll(combination);
            graphList.add(newGraph);
            continue;
        }

        connectedSoFar.addAll(combination);
        for (Node node: combination) {
            Set<Node> k = new HashSet<Node>(node.getNeighbours());
            connectedGraphsOnNVertices(n, connectedSoFar, k, graphList);
        }
        connectedSoFar.removeAll(combination);
    }
}

1 Ответ

1 голос
/ 30 мая 2011

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

В любом случае, для анализа алгоритма у вас есть 2 d элементов в powerset; каждая операция в ветви «elase» занимает O (n) времени, потому что connectedSoFar и комбинация вместе не могут содержать более n узлов. Добавление элементов в connectedSoFar тогда занимает O (n log n) времени, потому что | комбинация | & Leq; п. Итерация по узлам комбинации происходит O (n) раз; внутри него есть операция O (d) для построения хэш-множества k, а затем рекурсивный вызов.

Обозначим тогда сложность процедуры через X (n), где n - параметр. У вас есть

X (n) ~ 2 d (n + n log n + n (d + X (n - 1)))

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

Упростите это до

X (n) ~ 2 d (n (1 + d + log n + X (n - 1)))

, поскольку d является постоянной величиной, отметьте D = 2 d , исключите постоянную 1, и вы получите

X (n) ~ D n (d + log n + X (n - 1))

, который вы можете проанализировать как

X (n) ~ (2 d ) n n! (d + log n)

, показывающий, что ваш алгоритм действительно является временным боровом:)

...