每日算法 — 使用java实现成语接龙：Trie前缀树与有向图最长路径搜索

可莉爸爸 AI算法

引言

成语接龙是中国传统的文字游戏，规则简单而富有挑战性：参与者依次说出一个成语，后一个成语的第一个字必须与前一个成语的最后一个字相同（允许同音字或同字）。例如”一马当先 → 先声夺人 → 人山人海 → 海阔天空”。表面上看这是一个语言游戏，但从算法角度分析，成语接龙本质上是一个有向图上的最长路径问题——每个成语是图中的一个节点，若成语A的尾字与成语B的首字匹配，则存在一条从A到B的有向边。本文将用Java实现一个智能成语接龙系统，深入讲解Trie前缀树高效检索、有向图构建与深度优先搜索最长路径三大核心算法。

一、成语接龙的数学建模

1.1 有向图表示

设成语集合为 $V = {c_1, c_2, …, c_n}$，其中每个成语 $c_i$ 有首字 $first(c_i)$ 和尾字 $last(c_i)$。

定义有向图 $G = (V, E)$，其中边集 $E$ 满足：

$$E = {(c_i, c_j) \mid last(c_i) = first(c_j)}$$

成语接龙的目标是在图 $G$ 中找到一条最长简单路径（不重复经过节点的路径）。这是一个经典的NP-hard问题（哈密顿路径的特例），因此对于大规模图，需要使用启发式策略或近似算法。

1.2 约束扩展

在实际游戏中，还可以增加以下约束：

  • 长度约束：接龙长度达到 $K$ 条成语时获胜
  • 难度约束：只能使用特定难度的成语（如常用成语）
  • 禁用约束：某些成语不允许使用
  • 时间约束：每步有时间限制

本文的实现支持长度约束和禁用约束。

二、核心算法详解

2.1 Trie前缀树检索

为了快速查找以某个字开头的所有成语，我们使用Trie前缀树。Trie树的核心思想是：

  • 每个节点代表一个汉字
  • 从根节点到某个节点的路径上的字符序列构成一个前缀
  • 在节点上标记是否存在以该前缀为开头的成语

Trie树的插入和查找时间复杂度均为 $O(L)$，其中 $L$ 为成语长度。相比哈希表的 $O(1)$ 查找，Trie树的优势在于前缀检索——可以快速找到所有以某个字开头的成语。

2.2 有向图构建与邻接表

基于Trie树的检索结果，我们可以高效构建有向图：

  1. 遍历所有成语，对每个成语 $c_i$，查询Trie树中所有以 $last(c_i)$ 开头的成语
  2. 为每对匹配的成语建立有向边
  3. 使用邻接表存储图结构，空间复杂度 $O(|V| + |E|)$

2.3 最长路径搜索

由于最长简单路径是NP-hard问题，我们采用以下策略组合：

  1. 记忆化DFS：对每个成语，记录以它为起点的最长路径长度和路径本身
  2. 拓扑启发式：优先扩展出度较小的节点（类似拓扑排序的思想）
  3. 双向剪枝：若当前路径长度加上剩余可能的最大长度仍小于已找到的最优解，则剪枝

对于无环图（DAG），可以使用动态规划在 $O(|V| + |E|)$ 时间内求解最长路径。但成语接龙图通常存在环（如”山 → 水 → 山”），因此需要使用DFS+记忆化。

三、Java完整实现

import java.util.*;

/**
 * 智能成语接龙系统
 * 核心算法：Trie前缀树、有向图构建、记忆化DFS最长路径搜索
 */
public class IdiomSolitaire {

    /**
     * Trie树节点，每个节点代表一个汉字
     */
    public static class TrieNode {
        public Map<Character, TrieNode> children;  // 子节点映射
        public List<String> idioms;                // 以当前路径为前缀的成语列表
        public boolean isEndOfWord;                // 是否为一个完整成语的结尾

        public TrieNode() {
            this.children = new HashMap<>();
            this.idioms = new ArrayList<>();
            this.isEndOfWord = false;
        }
    }

    /**
     * Trie前缀树：支持快速前缀检索和精确匹配
     */
    public static class Trie {
        private TrieNode root;

        public Trie() {
            this.root = new TrieNode();
        }

        /**
         * 插入一个成语到Trie树
         */
        public void insert(String idiom) {
            TrieNode node = root;
            for (char ch : idiom.toCharArray()) {
                node.children.putIfAbsent(ch, new TrieNode());
                node = node.children.get(ch);
                node.idioms.add(idiom);
            }
            node.isEndOfWord = true;
        }

        /**
         * 查找所有以指定字开头的成语
         */
        public List<String> searchByFirstChar(char firstChar) {
            TrieNode node = root.children.get(firstChar);
            if (node == null) return new ArrayList<>();
            return new ArrayList<>(node.idioms);
        }

        /**
         * 检查是否存在以指定字开头的成语
         */
        public boolean hasPrefix(char firstChar) {
            return root.children.containsKey(firstChar);
        }
    }

    /**
     * 成语数据类，封装成语的元信息
     */
    public static class Idiom {
        public String text;        // 成语文本
        public char firstChar;     // 首字
        public char lastChar;      // 尾字
        public int length;         // 长度（字数）
        public int difficulty;     // 难度等级 1-5

        public Idiom(String text, int difficulty) {
            this.text = text;
            this.firstChar = text.charAt(0);
            this.lastChar = text.charAt(text.length() - 1);
            this.length = text.length();
            this.difficulty = difficulty;
        }

        @Override
        public String toString() {
            return text;
        }
    }

    /**
     * 有向图节点，用于接龙路径搜索
     */
    public static class GraphNode {
        public Idiom idiom;
        public List<GraphNode> neighbors;  // 出边邻居（尾字匹配的成语）
        public int outDegree;              // 出度
        public int inDegree;               // 入度

        public GraphNode(Idiom idiom) {
            this.idiom = idiom;
            this.neighbors = new ArrayList<>();
            this.outDegree = 0;
            this.inDegree = 0;
        }
    }

    /**
     * 成语接龙图，包含完整的图结构和搜索算法
     */
    public static class SolitaireGraph {
        private Map<String, GraphNode> nodeMap;  // 成语文本到图节点的映射
        private List<GraphNode> allNodes;
        private Trie trie;

        public SolitaireGraph() {
            this.nodeMap = new HashMap<>();
            this.allNodes = new ArrayList<>();
            this.trie = new Trie();
        }

        /**
         * 添加成语到系统中
         */
        public void addIdiom(Idiom idiom) {
            GraphNode node = new GraphNode(idiom);
            nodeMap.put(idiom.text, node);
            allNodes.add(node);
            trie.insert(idiom.text);
        }

        /**
         * 构建有向图：为每个成语建立到尾字匹配成语的边
         */
        public void buildGraph() {
            for (GraphNode node : allNodes) {
                char lastChar = node.idiom.lastChar;
                List<String> candidates = trie.searchByFirstChar(lastChar);

                for (String candidate : candidates) {
                    GraphNode neighbor = nodeMap.get(candidate);
                    if (neighbor != null && neighbor != node) {
                        node.neighbors.add(neighbor);
                        node.outDegree++;
                        neighbor.inDegree++;
                    }
                }
            }

            System.out.println("图构建完成：" + allNodes.size() + " 个节点");
            int totalEdges = allNodes.stream().mapToInt(n -> n.outDegree).sum();
            System.out.println("总边数：" + totalEdges);
        }

        /**
         * 使用记忆化DFS搜索从指定成语出发的最长接龙路径
         */
        public List<Idiom> findLongestPath(String startIdiom) {
            GraphNode start = nodeMap.get(startIdiom);
            if (start == null) return new ArrayList<>();

            Set<String> visited = new HashSet<>();
            Map<String, PathResult> memo = new HashMap<>();

            PathResult result = dfsLongestPath(start, visited, memo);
            return result.path;
        }

        /**
         * 深度优先搜索，带记忆化
         */
        private PathResult dfsLongestPath(GraphNode node, Set<String> visited,
                                          Map<String, PathResult> memo) {
            // 记忆化检查
            if (memo.containsKey(node.idiom.text)) {
                return memo.get(node.idiom.text);
            }

            visited.add(node.idiom.text);

            PathResult best = new PathResult();
            best.path.add(node.idiom);
            best.length = 1;

            // 按出度升序排序邻居，优先尝试"死胡同"节点（剪枝效率更高）
            List<GraphNode> sortedNeighbors = new ArrayList<>(node.neighbors);
            sortedNeighbors.sort(Comparator.comparingInt(n -> n.outDegree));

            for (GraphNode neighbor : sortedNeighbors) {
                if (!visited.contains(neighbor.idiom.text)) {
                    PathResult subResult = dfsLongestPath(neighbor, visited, memo);
                    if (subResult.length + 1 > best.length) {
                        best = new PathResult();
                        best.path.add(node.idiom);
                        best.path.addAll(subResult.path);
                        best.length = best.path.size();
                    }
                }
            }

            visited.remove(node.idiom.text);

            // 存储记忆化结果（注意：需要复制路径，避免引用问题）
            PathResult memoResult = new PathResult();
            memoResult.path = new ArrayList<>(best.path);
            memoResult.length = best.length;
            memo.put(node.idiom.text, memoResult);

            return best;
        }

        /**
         * 全局最长路径搜索：从每个节点出发搜索，取最大值
         */
        public List<Idiom> findGlobalLongestPath() {
            List<Idiom> bestPath = new ArrayList<>();

            for (GraphNode node : allNodes) {
                List<Idiom> path = findLongestPath(node.idiom.text);
                if (path.size() > bestPath.size()) {
                    bestPath = path;
                }
            }

            return bestPath;
        }

        /**
         * AI决策：给定当前尾字，选择最优的下一个成语
         * 策略：选择出度最小的邻居（保留更多后续选择）
         */
        public Idiom chooseNextMove(char lastChar, Set<String> used) {
            List<String> candidates = trie.searchByFirstChar(lastChar);
            Idiom bestChoice = null;
            int minOutDegree = Integer.MAX_VALUE;

            for (String candidate : candidates) {
                if (used.contains(candidate)) continue;

                GraphNode node = nodeMap.get(candidate);
                if (node != null) {
                    // 计算可用出度（排除已使用的成语）
                    int availableOut = 0;
                    for (GraphNode neighbor : node.neighbors) {
                        if (!used.contains(neighbor.idiom.text)) {
                            availableOut++;
                        }
                    }

                    // 优先选择可用出度最小的（保留后路策略）
                    if (availableOut < minOutDegree) {
                        minOutDegree = availableOut;
                        bestChoice = node.idiom;
                    }
                }
            }

            return bestChoice;
        }
    }

    public static class PathResult {
        public List<Idiom> path;
        public int length;

        public PathResult() {
            this.path = new ArrayList<>();
            this.length = 0;
        }
    }

    /**
     * 游戏模拟器：模拟人机对战
     */
    public static class GameSimulator {
        private SolitaireGraph graph;
        private Set<String> usedIdioms;
        private List<String> history;

        public GameSimulator(SolitaireGraph graph) {
            this.graph = graph;
            this.usedIdioms = new HashSet<>();
            this.history = new ArrayList<>();
        }

        /**
         * 执行一步接龙
         */
        public boolean makeMove(String idiomText) {
            if (usedIdioms.contains(idiomText)) {
                System.out.println("成语已被使用：" + idiomText);
                return false;
            }

            if (!history.isEmpty()) {
                String last = history.get(history.size() - 1);
                char lastChar = last.charAt(last.length() - 1);
                char firstChar = idiomText.charAt(0);
                if (lastChar != firstChar) {
                    System.out.println("接龙不匹配：" + last + " -> " + idiomText);
                    return false;
                }
            }

            usedIdioms.add(idiomText);
            history.add(idiomText);
            return true;
        }

        /**
         * AI自动走一步
         */
        public boolean aiMove() {
            if (history.isEmpty()) {
                // AI先手：随机选择一个成语
                List<GraphNode> nodes = graph.allNodes;
                String choice = nodes.get(new Random().nextInt(nodes.size())).idiom.text;
                return makeMove(choice);
            }

            char lastChar = history.get(history.size() - 1).charAt(
                history.get(history.size() - 1).length() - 1);
            Idiom choice = graph.chooseNextMove(lastChar, usedIdioms);

            if (choice == null) {
                System.out.println("AI无法接龙，认输！");
                return false;
            }

            System.out.println("AI选择：" + choice.text);
            return makeMove(choice.text);
        }

        public void printHistory() {
            System.out.println("接龙历史：");
            for (int i = 0; i < history.size(); i++) {
                System.out.print(history.get(i));
                if (i < history.size() - 1) System.out.print(" → ");
            }
            System.out.println("\n总计：" + history.size() + " 条成语");
        }
    }

    /**
     * 初始化成语库
     */
    public static SolitaireGraph initIdiomDatabase() {
        SolitaireGraph graph = new SolitaireGraph();

        // 常用成语库（简化版，实际应用中应从数据库加载）
        String[][] idiomData = {
            {"一马当先", "3"}, {"先声夺人", "3"}, {"人山人海", "2"}, {"海阔天空", "3"},
            {"空前绝后", "4"}, {"后继有人", "2"}, {"人云亦云", "3"}, {"云开见日", "3"},
            {"日积月累", "2"}, {"累卵之危", "5"}, {"危在旦夕", "3"}, {"夕惕若厉", "5"},
            {"厉兵秣马", "4"}, {"马到成功", "2"}, {"功成名就", "3"}, {"。就事论事", "3"},
            {"事半功倍", "3"}, {"倍道而行", "4"}, {"行云流水", "3"}, {"水落石出", "2"},
            {"出神入化", "3"}, {"化险为夷", "3"}, {"夷为平地", "3"}, {"地平天成", "5"},
            {"成竹在胸", "3"}, {"胸有成竹", "2"}, {"竹报平安", "4"}, {"安居乐业", "2"},
            {"业精于勤", "3"}, {"勤能补拙", "3"}, {"拙口钝腮", "5"}, {"腮帮鼓鼓", "5"},
            {"鼓舞人心", "3"}, {"心旷神怡", "3"}, {"怡然自得", "3"}, {"得心应手", "2"},
            {"手不释卷", "3"}, {"卷土重来", "3"}, {"来日方长", "2"}, {"长治久安", "3"},
            {"安步当车", "4"}, {"车水马龙", "2"}, {"龙飞凤舞", "3"}, {"舞文弄墨", "4"},
            {"墨守成规", "3"}, {"。规行矩步", "4"}, {"步步为营", "3"}, {"营私舞弊", "5"},
            {"弊绝风清", "5"}, {"清风明月", "3"}, {"月明星稀", "4"}, {"稀奇古怪", "4"},
            {"怪力乱神", "5"}, {"神机妙算", "3"}, {"算无遗策", "5"}, {"策马奔腾", "4"},
            {"腾云驾雾", "4"}, {"雾里看花", "3"}, {"花好月圆", "2"}, {"圆满成功", "2"},
            {"功德无量", "3"}, {"量体裁衣", "3"}, {"衣锦还乡", "3"}, {"乡音无改", "4"},
            {"改天换地", "3"}, {"地大物博", "3"}, {"博学多才", "3"}, {"才高八斗", "3"},
            {"斗转星移", "3"}, {"移花接木", "3"}, {"木已成舟", "3"}, {"舟车劳顿", "4"},
            {"顿开茅塞", "5"}, {"塞翁失马", "4"}, {"马首是瞻", "4"}, {"瞻前顾后", "3"},
            {"后来居上", "3"}, {"上行下效", "3"}, {"效颦学步", "5"}, {"步步高升", "3"},
            {"升堂入室", "4"}, {"室如悬磬", "5"}, {"磬竹难书", "5"}, {"。书香门第", "3"},
            {"第次鳞比", "5"}, {"比翼双飞", "3"}, {"飞蛾扑火", "3"}, {"火树银花", "4"},
            {"花言巧语", "2"}, {"语重心长", "3"}, {"长年累月", "3"}, {"月下老人", "3"},
            {"人定胜天", "3"}, {"天经地义", "2"}, {"义不容辞", "3"}, {"辞旧迎新", "3"},
            {"新陈代谢", "3"}, {"谢天谢地", "3"}, {"地久天长", "2"}, {"长驱直入", "3"},
            {"入木三分", "3"}, {"分秒必争", "3"}, {"争分夺秒", "2"}, {"秒不可言", "5"},
        };

        for (String[] data : idiomData) {
            graph.addIdiom(new Idiom(data[0], Integer.parseInt(data[1])));
        }

        return graph;
    }

    public static void main(String[] args) {
        System.out.println("=== 成语接龙AI系统 ===\n");

        // 初始化成语数据库
        SolitaireGraph graph = initIdiomDatabase();
        graph.buildGraph();

        // 搜索从"一马当先"出发的最长接龙
        System.out.println("\n搜索最长接龙路径...");
        List<Idiom> longestPath = graph.findLongestPath("一马当先");
        System.out.println("从'一马当先'出发的最长接龙（" + longestPath.size() + "条）：");
        for (int i = 0; i < longestPath.size(); i++) {
            System.out.print(longestPath.get(i));
            if (i < longestPath.size() - 1) System.out.print(" → ");
        }
        System.out.println();

        // 模拟一局游戏
        System.out.println("\n=== 模拟AI对战 ===");
        GameSimulator game = new GameSimulator(graph);

        // AI先手
        game.aiMove();

        // AI连续接龙
        for (int i = 0; i < 10; i++) {
            if (!game.aiMove()) break;
        }

        game.printHistory();
    }
}

四、算法复杂度分析

模块 时间复杂度 空间复杂度 说明
Trie插入 $O(L)$ $O(N \cdot L)$ $N$ 为成语数，$L$ 为平均长度
Trie前缀查询 $O(L)$ $O(1)$ 返回所有匹配结果
图构建 $O(N \cdot M)$ $O(N + E)$ $M$ 为平均同首字成语数
记忆化DFS $O(N \cdot E)$ $O(N)$ 最坏情况遍历所有路径
AI决策 $O(M)$ $O(1)$ 选择最优下一步

对于实际规模的成语库（数千条成语），系统可在毫秒级完成路径搜索和AI决策。

五、扩展与优化方向

  1. 同音字支持：使用拼音映射将同音字视为等价，扩大接龙可能性
  2. 成语难度分级：根据难度等级构建分层图，支持不同水平玩家
  3. 并行搜索：使用多线程并行搜索多条路径，提高最长路径发现概率
  4. 对抗策略：引入博弈论思想，选择能最大化对手困难的接龙路径
  5. 图数据库优化：对于大规模成语库，使用Neo4j等图数据库存储和查询

六、总结

本文从成语接龙这一中国传统文字游戏出发，完整实现了基于Java的智能接龙系统。核心算法涵盖了Trie前缀树高效检索、有向图构建与记忆化DFS最长路径搜索。通过这些算法的组合，系统能够自动发现最长的成语接龙链，并在对战中做出最优决策。希望读者能够理解图论与字符串算法在自然语言处理中的巧妙结合，并将其应用到更多中文信息处理的场景中。

Tagged with: