3

特定の頂点を介して 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);
    }
}
4

1 に答える 1

1

再帰呼び出しの後、組み合わせて表示されるノードが connectedSoFar にも表示される可能性があるため、アルゴリズムにバグがあるようです。ノードを 2 回カウントする場合があります。

とにかく、そうでなければアルゴリズムを分析するには、パワーセットに 2 d要素があります。「elase」ブランチのすべての操作には O(n) 時間がかかります。これは、connectedSoFar とその組み合わせに n 個を超えるノードを含めることができないためです。|combination| であるため、connectedSoFar に要素を追加するには O(n log n) の時間がかかります。≤n。組み合わせノードの反復は O(n) 回発生します。その中には、ハッシュセット k を構築するための O(d) 操作と、再帰呼び出しがあります。

次に、手順の複雑さを X(n) で示します。ここで、n はパラメーターです。あなたが持っている

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

再帰呼び出しではグラフに少なくとも 1 つの頂点を追加したため、実際には再帰呼び出しのパラメーター n は実質的に少なくとも 1 減少します。

これを単純化して

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 + ログ n)

あなたのアルゴリズムが本当に時間を浪費していることを示しています:)

于 2011-05-29T20:37:42.180 に答える