寻求图划分的高效枚举策略：搜索空间缩减方法咨询

我正在做一个课程项目，需要把带权/无向图划分为p个类别，目标是最小化不同类别顶点间边的权重总和，同时要保证顶点在p个类别中近似均匀分布。

一开始我用显式枚举（“生成测试法”）找最优划分，但项目要求要给25个顶点的小图找最优解。我写了一个遍历全搜索空间的函数，但效率极低：比如n=16、p=5时，生成所有可能划分要10分钟以上，25个顶点的话耗时根本没法接受。所以必须在评估当前解之前有效缩减搜索空间。

请问怎么有效预缩减枚举过程的搜索空间？有没有已知的策略或准则可以提前排除不可行的划分？

小规模实例 #

基本信息 #

边的权重信息 #

各顶点度数 #

当前实现代码 #

void generate(int n, int p) {
    vector<int> vecteur(n, 1);

    unsigned long long int total_combinations = pow(p, n);
    for (unsigned long long int i = 0; i < total_combinations; i++) {
        //printVector(vecteur);
        for (int j = n - 1; j >= 0; --j) {
            if (vecteur[j] < p) {
                vecteur[j]++;
                break;
            } else {
                vecteur[j] = 1;
            }
        }
    }
}

1. 利用对称性去重 #

枚举时会生成大量等价划分：比如把类别A和类别B的所有顶点互换，得到的划分在目标函数值上完全相同。可以固定前p个顶点的类别（比如第1个顶点归类别1，第2个归类别2…第p个归类别p），或者固定某个顶点的类别为基准，避免重复搜索对称解。这能直接把搜索空间缩小到原来的1/p!（阶乘分之一），对p=5来说就是缩小120倍，效果非常明显。

2. 提前过滤不满足均匀分布的划分 #

既然要求顶点近似均匀分布，那么每个类别的顶点数只能是floor(n/p)或ceil(n/p)。比如n=25、p=5时，每个类别必须是5个顶点；n=16、p=5时，类别大小只能是3或4（3个类别4个顶点，2个类别3个顶点）。在生成划分的过程中，一旦当前已分配的顶点导致某类别大小超出允许范围，就可以直接剪枝，停止后续分支的搜索。

3. 基于下界剪枝 #

在搜索过程中，计算当前部分划分的目标函数下界：比如已经分配了k个顶点，剩下的顶点不管怎么分配，不同类别间的边权总和至少是多少。如果这个下界已经大于当前找到的最优解，就可以直接放弃这个分支，不用继续搜索。

4. 按顶点关联度排序后搜索 #

把顶点按度数从高到低排序，优先分配度数高的顶点。这类顶点对目标函数的影响更大，能更早地发现差的划分并剪枝，减少后续无效搜索。

5. 排除类别数量不足的划分 #

项目要求划分为p个类别，所以可以直接排除所有类别数不足p的划分（比如你的代码生成的[1,1,1,1,1]这种仅1个类别的情况），在生成过程中实时检查是否所有p个类别都被使用，否则跳过评估。

具体实现建议 #

把原来的顺序枚举改成回溯式搜索，而不是生成所有组合。回溯过程中实时检查类别大小是否符合均匀要求、是否满足对称性约束，一旦不满足就剪枝；同时预计算每个顶点的邻接边权总和，在分配顶点时快速估算下界。

内容的提问来源于stack exchange，提问作者Goliaaath