0

グラフ内のクリークの最小数を解決するアルゴリズムを作成しました。バックトラッキング アルゴリズムをテストしましたが、最悪の場合の時間計算量を計算できませんでした。何度も試しました。

この問題が NP 困難な問題であることはわかっていますが、コードに基づいて最悪の時間計算量を与えることは可能だと思います。このコードの最悪の時間計算量は? 何か案が？再帰方程式をどのように形式化しますか?

わかりやすいコードを書いてみました。ご不明な点がございましたら、コメントをお書きください。ヒント、参考文献、回答をいただければ幸いです。ヒントをありがとう:)。

EDIT MCが基本的にコメントしたように、私はこの問題を解決しようとしましたクリークカバーの問題

擬似コード:

function countCliques(graph, vertice, cliques, numberOfClique, minimumSolution)
    for i = 1 .. number of cliques + 1 new loop
        if i > minimumSolution then 
            return;
        end if
        if (fitToClique(cliques(i), vertice, graph) then
            addVerticeToClique(cliques(i), vertice);
            if (vertice == 0) then //last vertice 
                minimumSolution = numberOfClique
                printResult(result);
            else 
                if (i == number of cliques + 1) then // if we are using a new clique the +1 always a new clique
                    countCliques(graph, vertice - 1, cliques, number of cliques + 1, minimum)
                else 
                    countCliques(graph, vertice - 1, cliques, number of cliques, minimum)
                end if
            end if 
            deleteVerticeFromClique(cliques(i), vertice);
        end if
    end loop
end function


bool fitToClique(clique, vertice, graph) 
    for ( i = 1 .. cliqueSize) loop 
        verticeFromClique = clique(i)
        if (not connected(verticeFromClique, vertice)) then 
            return false
        end if
    end loop
    return true
end function

コード

int countCliques(int** graph, int currentVertice, int** result, int numberOfSubset, int& minimum) {
// if solution
if (currentVertice == -1) {
    // if a better solution
    if (minimum > numberOfSubset) {
        minimum = numberOfSubset;
        printf("New minimum result:\n");
        print(result, numberOfSubset);
    }
    c++;
} else {
    // if not a solution, try to insert to a clique, if not fit then create a new clique (+1 in the loop)
    for (int i = 0; i < numberOfSubset + 1; i++) {
        if (i > minimum) {
            break;
        }
        //if fit
        if (fitToSubset(result[i], currentVertice, graph)) {
            // insert
            result[i][0]++;
            result[i][result[i][0]] = currentVertice;
            // try to insert the next vertice
            countCliques(graph, currentVertice - 1, result, (i == numberOfSubset) ? (i + 1) : numberOfSubset, minimum);
            // delete vertice from the clique
            result[i][0]--;
        }
    }
}
return c;
}


bool fitToSubset(int *subSet, int currentVertice, int **graph) {
    int subsetLength = subSet[0];
    for (int i = 1; i < subsetLength + 1; i++) {
        if (graph[subSet[i]][currentVertice] != 1) {
            return false;
        }
    }
    return true;


  }

void print(int **result, int n) {
    for (int i = 0; i < n; i++) {
        int m = result[i][0];
        printf("[");
        for (int j = 1; j < m; j++) {
            printf("%d, ",result[i][j] + 1);
        }
        printf("%d]\n", result[i][m] + 1);
    }
}

int** readFile(const char* file, int& v, int& e) {
int from, to;
int **graph;
FILE *graphFile;
fopen_s(&graphFile, file, "r");

fscanf_s(graphFile,"%d %d", &v, &e);

graph = (int**)malloc(v * sizeof(int));

for (int i = 0; i < v; i ++) {
    graph[i] = (int*)calloc(v, sizeof(int));
}

while(fscanf_s(graphFile,"%d %d", &from, &to) == 2) {
    graph[from - 1][to - 1] = 1;
    graph[to - 1][from - 1] = 1;
}
fclose(graphFile);
return graph;
}
4

1 に答える 1

1

アルゴリズムの時間の複雑さは、O(2^N) の整数の構成をリストすることに非常に密接に関連しています。

コンビナトリアルな側面もあるので、コンポジションだけでは不十分ですが、ルールもあります。具体的には、クリークには最大番号の未使用頂点が含まれている必要があります。

例は、構成 2-2-1 (N = 5) です。最初のクリークには 4 が含まれている必要があり、未使用の頂点の数は 4 に減ります。その後、4 つの要素のうちの 1 つを選択できます。未使用の頂点は現在 3 です。したがって、2 番目のクリークの最終頂点を決定する 2 つの要素のうちの 1 つを選択する必要があります。これにより、最後のクリークの頂点が 1 つだけ残ります。この合成には、(1*C(4,1)*1*C(2,1)*1) で与えられる 8 つの可能な方法があります。8つの可能な方法は次のとおりです。

(5,4),(3,2),(1)
(5,4),(3,1),(2)
(5,3),(4,2),(1)
(5,3),(4,1),(2)
(5,2),(4,3),(1)
(5,2),(4,1),(3)
(5,1),(4,3),(2)
(5,1),(4,2),(3)

上記の例は、コンポジションに可能な限り多くの 2 が含まれる最悪のケースに必要な形式を示しています。実際には (N-1) (N-3) (N-5) ... (1) または (N-1) (N-3) (N )ですが、これはまだ O(N!) だと思います-5) ... (2). ただし、示されているように完全なグラフが必要であり、すぐにキャッチされ、グラフを単一のクリークに制限し、そのうちのソリューションが 1 つしかないため、不可能です。

組成のバリエーションを考えると、考えられる組成の数は、おそらく O(2^N) としての上限の適切な開始点です。O(3^(N/3)) 個の最大クリークがあるということは、アルゴリズムが理論的にはそれらすべてを見つけることができるため、もう 1 つの有用な情報です。いくつかの最大クリークが複数回検出され、他のクリークはまったく検出されないため、これでも十分ではありません。

主な理由は 2 つあります。まず、アルゴリズムはクリークの最大数を徐々に制限します。これは、構成のサイズと呼ぶことができると思います。これにより、クリークごとに費やされる計算時間の上限が設定されます。第 2 に、エッジが欠落していると、考えられる多数のバリエーションが無視されます。これにより、O(N!) バリエーションの大部分が無視されることがほぼ保証されます。上記の段落と組み合わせると、上限を設定することが難しくなります。これが答えとして不十分な場合は、より良い答えを得るにはかなりの数学的分析が必要になるため、質問をスタック交換の数学領域に持ち込むことをお勧めします。

于 2013-04-21T10:17:04.403 に答える