0

我写了一个算法来解决图中的最小集团数。我已经测试了我的回溯算法，但我无法计算最坏情况的时间复杂度，我尝试了很多次。

我知道这个问题是一个 NP 难题，但我认为是否有可能根据代码给出最差的时间复杂度。这段代码最差的时间复杂度是多少？任何想法？你如何形式化递归方程？

我试图编写可理解的代码。如果您有任何问题，请写评论。我会很高兴获得提示、参考和答案。谢谢提醒伙计：）。

编辑 正如 MC 评论的那样，我基本上已经尝试解决这个问题Clique 封面问题

伪代码：

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)。第一个 clique 必须包含 4，将未使用的顶点数减少到 4。然后在 4 个元素中的 1 个之间进行选择，未使用的顶点现在是 3。第二个 clique 的 1 个元素是已知的，因此 2 个未使用的顶点。因此，必须在 2 个元素中选择 1 个来决定第二个集团中的最终顶点。这只会为最后一个团留下一个顶点。对于这个组合，有 8 种可能的方法，由 (1*C(4,1)*1*C(2,1)*1) 给出。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。我认为这仍然是 O(N!) 即使它实际上是 (N-1) (N-3) (N-5) ... (1) 或 (N-1) (N-3) (N -5）...（2）。然而，这是不可能的，因为它需要一个完整的图，它会立即被捕获，并将图限制为一个单一的集团，其中只有一个解决方案。

鉴于组合的变化，可能组合的数量可能是 O(2^N) 上限的一个公平起点。存在 O(3^(N/3)) 个最大团是另一个有用的信息，因为该算法理论上可以找到所有这些团。虽然这还不够好，因为一些最大的集团被多次发现，而另一些则根本没有。

一个更严格的上限是困难的，主要有两个原因。首先，该算法逐渐限制了最大团数，我想您可以将其称为组合的大小，这对每个团花费的计算时间设置了上限。其次，缺失边会导致大量可能的变化被忽略，这几乎可以确保绝大多数 O(N!) 变化被忽略。结合上面的段落，使得设置上限变得困难。如果这还不足以得到答案，您可能希望将问题带到堆栈交换的数学领域，因为更好的答案将需要相当多的数学分析。

于 2013-04-21T10:17:04.403 回答