每日算法 — 使用java实现Connections：单词关联图聚类与连通分量检测

Connections是《纽约时报》推出的一款风靡全球的单词联想益智游戏。每局给出16个单词，玩家需要将它们分成4组，每组4个单词共享一个隐藏的共同主题。本文用Java实现Connections自动求解器，核心算法包括：基于语义相似度构建单词关联图、运用连通分量检测识别潜在主题簇，以及回溯搜索验证分组方案的正确性。

一、游戏规则与建模

1.1 游戏规则

• 给定16个互不相同的目标单词
• 玩家需将这16个单词分为4组，每组恰好4个单词
• 每组单词共享一个共同主题（如”都是水果”、”都可以跟’ball’组成复合词”）
• 主题难度分为4个等级（黄色最简单，紫色最难）
• 选错4次后游戏结束

1.2 图论建模

将Connections建模为加权无向图：

• 顶点：16个单词
• 边权重：两个单词之间的”主题关联强度”，由语义相似度、共现统计和构词法规则综合计算

目标是将图划分为4个大小为4的团（clique），每个团内部边权之和最大，且团之间边权之和最小。

1.3 关联强度计算

本文采用三层特征融合计算单词关联度：

1. 语义相似度：基于WordNet或预训练词向量的余弦相似度
2. 构词法规则：检测共同前缀/后缀、能否与同一词组合成新词
3. 类别共现：统计两个单词在已知分类数据集中共同出现的频率

二、核心算法设计

2.1 关联图构建与连通分量分析

构建16×16的关联矩阵后，通过阈值化得到二值邻接矩阵。运用并查集（Union-Find）或DFS/BFS检测连通分量，可快速识别明显聚在一起的单词组。由于真实游戏中4组之间通常界限分明，低阈值下即可分离出大致簇结构。

2.2 基于最大权团的分组搜索

将问题精确建模为带权图划分：寻找4个不相交的4元子集，使得子集内部边权之和最大化。这是NP-hard问题，本文采用分支限界法结合启发式剪枝进行求解：

1. 先找出权重最高的边作为种子对
2. 逐步扩展为4元组，维护当前团的总权重
3. 若剩余单词无法达到当前最优解，剪枝
4. 找到一组后移除对应顶点，递归求解剩余12个单词

2.3 主题验证与难度评估

对找到的每组4个单词，通过规则库验证其主题合理性：

• 检查是否都包含同一子串
• 检查是否都是同一超类的实例
• 检查是否都能与同一词搭配

同时根据规则的”隐蔽性”评估难度等级。

三、完整Java实现

import java.util.*;

/**
 * Connections单词联想求解器
 * 运用图聚类、连通分量检测与分支限界搜索
 */
public class ConnectionsSolver {

    private final int N = 16;           // 总单词数
    private final int GROUP_SIZE = 4;   // 每组大小
    private final String[] words;       // 单词列表
    private final double[][] simMatrix; // 关联强度矩阵

    public ConnectionsSolver(String[] words) {
        if (words.length != N) {
            throw new IllegalArgumentException("必须提供16个单词");
        }
        this.words = words.clone();
        this.simMatrix = new double[N][N];
        buildSimilarityMatrix();
    }

    /**
     * 构建关联强度矩阵
     * 融合语义相似度、构词法规则和类别共现
     */
    private void buildSimilarityMatrix() {
        for (int i = 0; i < N; i++) {
            for (int j = i + 1; j < N; j++) {
                double score = computeSimilarity(words[i], words[j]);
                simMatrix[i][j] = score;
                simMatrix[j][i] = score;
            }
        }
    }

    /**
     * 综合计算两个单词的关联强度
     */
    private double computeSimilarity(String a, String b) {
        double score = 0;

        // 1. 共同子串（前缀/后缀匹配）
        score += commonSubstringScore(a, b) * 0.35;

        // 2. 语义类别相似度（基于内置规则库）
        score += semanticCategoryScore(a, b) * 0.40;

        // 3. 构词搭配规则（能否与同一词组合）
        score += compoundWordScore(a, b) * 0.25;

        return Math.min(1.0, score);
    }

    /** 共同子串得分 */
    private double commonSubstringScore(String a, String b) {
        String la = a.toLowerCase(), lb = b.toLowerCase();
        int maxLen = 0;
        for (int i = 0; i < la.length(); i++) {
            for (int j = 0; j < lb.length(); j++) {
                int len = 0;
                while (i + len < la.length() && j + len < lb.length()
                       && la.charAt(i + len) == lb.charAt(j + len)) {
                    len++;
                }
                maxLen = Math.max(maxLen, len);
            }
        }
        // 至少3个字符的共同子串才有意义
        return maxLen >= 3 ? Math.min(1.0, maxLen / 4.0) : 0;
    }

    /** 语义类别得分（简化规则库） */
    private double semanticCategoryScore(String a, String b) {
        String la = a.toLowerCase(), lb = b.toLowerCase();

        // 预定义类别词表
        String[][] categories = {
            {"apple", "banana", "cherry", "grape", "orange", "peach", "pear", "plum"},
            {"dog", "cat", "bird", "fish", "bear", "wolf", "lion", "tiger"},
            {"red", "blue", "green", "yellow", "purple", "orange", "black", "white"},
            {"run", "jump", "walk", "swim", "fly", "crawl", "climb", "dance"},
            {"car", "bus", "train", "plane", "boat", "bike", "truck", "ship"},
            {"monday", "tuesday", "wednesday", "thursday", "friday", "saturday", "sunday"},
            {"january", "february", "march", "april", "may", "june", "july"},
            {"one", "two", "three", "four", "five", "six", "seven", "eight"},
            {"heart", "diamond", "club", "spade"},
            {"spring", "summer", "autumn", "fall", "winter"},
            {"north", "south", "east", "west"},
            {" Mercury", "venus", "earth", "mars", "jupiter", "saturn"},
        };

        for (String[] cat : categories) {
            boolean hasA = false, hasB = false;
            for (String w : cat) {
                if (la.equals(w)) hasA = true;
                if (lb.equals(w)) hasB = true;
            }
            if (hasA && hasB) return 1.0;
        }
        return 0;
    }

    /** 构词搭配得分（共同可搭配的词根） */
    private double compoundWordScore(String a, String b) {
        String la = a.toLowerCase(), lb = b.toLowerCase();
        String[] prefixes = {"snow", "water", "fire", "foot", "ball", "base", "over", "under",
                             "sun", "moon", "star", "light", "day", "night", "head", "hand"};
        String[] suffixes = {"ball", "man", "board", "light", "way", "work", "time", "room"};

        for (String p : prefixes) {
            if ((la.startsWith(p) || la.endsWith(p)) && (lb.startsWith(p) || lb.endsWith(p))) {
                return 0.8;
            }
        }
        for (String s : suffixes) {
            if (la.endsWith(s) && lb.endsWith(s)) return 0.8;
        }
        return 0;
    }

    /**
     * 使用并查集检测连通分量（阈值化后）
     */
    public List<Set<Integer>> findConnectedComponents(double threshold) {
        UnionFind uf = new UnionFind(N);
        for (int i = 0; i < N; i++) {
            for (int j = i + 1; j < N; j++) {
                if (simMatrix[i][j] >= threshold) {
                    uf.union(i, j);
                }
            }
        }
        Map<Integer, Set<Integer>> comps = new HashMap<>();
        for (int i = 0; i < N; i++) {
            int root = uf.find(i);
            comps.computeIfAbsent(root, k -> new HashSet<>()).add(i);
        }
        return new ArrayList<>(comps.values());
    }

    /** 并查集数据结构 */
    static class UnionFind {
        int[] parent, rank;
        UnionFind(int n) {
            parent = new int[n];
            rank = new int[n];
            for (int i = 0; i < n; i++) parent[i] = i;
        }
        int find(int x) {
            if (parent[x] != x) parent[x] = find(parent[x]);
            return parent[x];
        }
        void union(int a, int b) {
            int ra = find(a), rb = find(b);
            if (ra == rb) return;
            if (rank[ra] < rank[rb]) { int t = ra; ra = rb; rb = t; }
            parent[rb] = ra;
            if (rank[ra] == rank[rb]) rank[ra]++;
        }
    }

    /**
     * 计算一个组的内部关联强度
     */
    private double groupScore(int[] group) {
        double sum = 0;
        for (int i = 0; i < group.length; i++) {
            for (int j = i + 1; j < group.length; j++) {
                sum += simMatrix[group[i]][group[j]];
            }
        }
        return sum;
    }

    /**
     * 分支限界搜索最优4组划分
     */
    public int[][] solve() {
        boolean[] used = new boolean[N];
        int[][] bestSolution = new int[4][GROUP_SIZE];
        double[] bestScores = new double[4];
        Arrays.fill(bestScores, -1);

        List<Integer> remaining = new ArrayList<>();
        for (int i = 0; i < N; i++) remaining.add(i);

        search(0, used, remaining, new ArrayList<>(), bestSolution, bestScores);
        return bestSolution;
    }

    private void search(int groupIdx, boolean[] used, List<Integer> remaining,
                        List<int[]> current, int[][] best, double[] bestScores) {
        if (groupIdx == 4) {
            // 找到完整解，评估
            double total = 0;
            for (int[] g : current) total += groupScore(g);
            if (total > Arrays.stream(bestScores).sum()) {
                for (int i = 0; i < 4; i++) {
                    System.arraycopy(current.get(i), 0, best[i], 0, GROUP_SIZE);
                    bestScores[i] = groupScore(current.get(i));
                }
            }
            return;
        }

        // 生成候选组：从剩余顶点中选4个
        List<int[]> candidates = generateCandidates(remaining);
        // 按组内关联强度降序排序（分支限界启发式）
        candidates.sort((a, b) -> Double.compare(groupScore(b), groupScore(a)));

        for (int[] cand : candidates) {
            // 剪枝：如果当前组得分太低，跳过
            if (groupScore(cand) < 0.3 && remaining.size() > 4) continue;

            // 应用选择
            boolean[] newUsed = used.clone();
            List<Integer> newRemaining = new ArrayList<>(remaining);
            for (int v : cand) {
                newUsed[v] = true;
                newRemaining.remove(Integer.valueOf(v));
            }
            current.add(cand);

            search(groupIdx + 1, newUsed, newRemaining, current, best, bestScores);

            current.remove(current.size() - 1);
        }
    }

    /**
     * 从剩余顶点中生成所有4元组候选
     * 为控制搜索空间，优先选择关联度高的种子对扩展
     */
    private List<int[]> generateCandidates(List<Integer> remaining) {
        List<int[]> result = new ArrayList<>();
        int m = remaining.size();
        if (m < 4) return result;

        // 如果数量不多，直接枚举
        if (m <= 8) {
            for (int i = 0; i < m; i++)
                for (int j = i + 1; j < m; j++)
                    for (int k = j + 1; k < m; k++)
                        for (int l = k + 1; l < m; l++)
                            result.add(new int[]{remaining.get(i), remaining.get(j),
                                                 remaining.get(k), remaining.get(l)});
            return result;
        }

        // 大量剩余时，用启发式：从最强边开始扩展
        List<int[]> edges = new ArrayList<>();
        for (int i = 0; i < m; i++)
            for (int j = i + 1; j < m; j++)
                edges.add(new int[]{remaining.get(i), remaining.get(j),
                    (int)(simMatrix[remaining.get(i)][remaining.get(j)] * 1000)});

        edges.sort((a, b) -> b[2] - a[2]);

        // 取前20条最强边作为种子
        Set<String> seen = new HashSet<>();
        for (int e = 0; e < Math.min(20, edges.size()); e++) {
            int seedA = edges.get(e)[0], seedB = edges.get(e)[1];
            // 找能与种子配对的另外两点
            for (int i = 0; i < m; i++) {
                int c = remaining.get(i);
                if (c == seedA || c == seedB) continue;
                for (int j = i + 1; j < m; j++) {
                    int d = remaining.get(j);
                    if (d == seedA || d == seedB) continue;
                    int[] group = new int[]{seedA, seedB, c, d};
                    Arrays.sort(group);
                    String key = Arrays.toString(group);
                    if (!seen.contains(key)) {
                        seen.add(key);
                        result.add(group);
                    }
                }
            }
        }
        return result;
    }

    /**
     * 打印求解结果
     */
    public void printSolution(int[][] groups) {
        String[] colors = {"🟨 黄色", "🟩 绿色", "🟦 蓝色", "🟪 紫色"};
        System.out.println("\n求解结果：");
        for (int g = 0; g < 4; g++) {
            System.out.print(colors[g] + ": ");
            for (int i = 0; i < GROUP_SIZE; i++) {
                System.out.print(words[groups[g][i]]);
                if (i < GROUP_SIZE - 1) System.out.print(", ");
            }
            System.out.println(" (关联强度=" + String.format("%.3f", groupScore(groups[g])) + ")");
        }
    }

    /**
     * 打印关联矩阵（调试用）
     */
    public void printMatrix() {
        System.out.println("\n关联强度矩阵：");
        System.out.print("      ");
        for (int i = 0; i < N; i++) System.out.printf("%6s", words[i].substring(0, Math.min(4, words[i].length())));
        System.out.println();
        for (int i = 0; i < N; i++) {
            System.out.printf("%-6s", words[i].substring(0, Math.min(4, words[i].length())));
            for (int j = 0; j < N; j++) {
                System.out.printf("%6.2f", simMatrix[i][j]);
            }
            System.out.println();
        }
    }

    // ==================== 主程序 ====================
    public static void main(String[] args) {
        System.out.println("===== Connections单词联想求解器 =====\n");

        // 示例谜题：16个单词
        String[] puzzle = {
            // 组1: 水果
            "apple", "grape", "peach", "plum",
            // 组2: 动作
            "run", "jump", "walk", "swim",
            // 组3: 颜色
            "black", "white", "green", "brown",
            // 组4: 交通工具
            "train", "plane", "boat", "truck"
        };

        ConnectionsSolver solver = new ConnectionsSolver(puzzle);
        solver.printMatrix();

        // 连通分量分析
        System.out.println("\n连通分量分析（阈值=0.3）：");
        List<Set<Integer>> comps = solver.findConnectedComponents(0.3);
        for (int i = 0; i < comps.size(); i++) {
            System.out.print("  分量 " + (i + 1) + ": ");
            for (int idx : comps.get(i)) System.out.print(puzzle[idx] + " ");
            System.out.println("(" + comps.get(i).size() + "个)");
        }

        // 精确求解
        System.out.println("\n开始分支限界搜索...");
        long start = System.currentTimeMillis();
        int[][] solution = solver.solve();
        long elapsed = System.currentTimeMillis() - start;
        System.out.println("搜索完成，耗时 " + elapsed + "ms");
        solver.printSolution(solution);

        // 验证：检查是否有重复单词
        Set<String> used = new HashSet<>();
        boolean valid = true;
        for (int[] g : solution) {
            for (int idx : g) {
                if (!used.add(puzzle[idx])) {
                    valid = false;
                    System.out.println("错误：单词 " + puzzle[idx] + " 被重复使用！");
                }
            }
        }
        System.out.println("\n验证结果：" + (valid && used.size() == 16 ? "✓ 合法解" : "✗ 非法解"));
    }
}

四、复杂度分析

由于16个单词划分为4组的总方案数为 (\frac{16!}{(4!)^4 \cdot 4!} \approx 2.6 \times 10^6)，结合启发式剪枝，实际搜索空间通常在数万级别，可在毫秒级完成。

五、扩展思考

1. 预训练词向量升级：将内置规则库替换为GloVe或Word2Vec词向量，通过余弦相似度计算语义关联，大幅提升对罕见主题（如”都是披头士歌曲名”）的识别能力。
2. 概率图模型：将关联强度视为概率，运用信念传播（Belief Propagation）在因子图上推理最可能的分组方案。
3. 交互式提示系统：当玩家卡住时，根据当前已选单词和剩余可能性，计算信息增益最大的提示（如”有两个单词属于’都是金属’这一组”）。

Connections求解器将自然语言处理、图论与组合搜索相结合，是理解”如何将模糊语义问题转化为精确计算问题”的优秀案例。图聚类与连通分量检测作为核心工具，在社交网络分析、生物信息学等领域有着广泛的应用。