算法分析与设计 4次上机实战：渗透/排序/路由/索引问题 Java 源码解析

算法分析与设计四次上机实战从渗透问题到文本索引的Java实现精要1. 课程实验概览与开发环境配置西电《算法分析与设计》课程的四次上机实验涵盖了算法领域的核心问题这些实验不仅是普林斯顿大学的经典练习题更是检验学生算法实现能力的重要标尺。四次实验依次为渗透问题Percolation、排序算法性能比较、地图路由Map Routing和文本索引Text Indexing。每个实验都聚焦不同的算法思想从并查集到图算法再到字符串匹配构成了完整的算法能力训练体系。开发环境建议推荐使用IntelliJ IDEA作为开发环境社区版即可满足需求必须导入algs4.jar标准库这是普林斯顿大学算法课程的官方支持库JDK版本建议使用1.8或以上// algs4.jar导入示例 import edu.princeton.cs.algs4.StdIn; import edu.princeton.cs.algs4.StdOut; import edu.princeton.cs.algs4.Stopwatch;实验通用验收标准程序必须正确编译运行需要展示对算法理论的深入理解优化措施需要量化性能提升代码风格规范注释清晰2. 渗透问题并查集的高级应用渗透问题模拟多孔介质中流体的渗透过程是并查集(Union-Find)数据结构的典型应用场景。该问题要求判断一个N×N的网格是否存在从顶部到底部的渗透路径。关键实现要点采用加权quick-union算法带路径压缩巧妙处理虚拟顶部和底部节点避免backwash回渗问题public class Percolation { private boolean[][] grid; // 网格状态 private int size; // 网格尺寸 private WeightedQuickUnionUF uf; // 并查集实例 private int virtualTop; // 虚拟顶部节点 private int virtualBottom; // 虚拟底部节点 // 初始化N×N网格所有格子初始为阻塞状态 public Percolation(int N) { if (N 0) throw new IllegalArgumentException(); size N; grid new boolean[N][N]; uf new WeightedQuickUnionUF(N*N 2); // 2表示虚拟节点 virtualTop N*N; virtualBottom N*N 1; } // 打开指定位置的格子 public void open(int i, int j) { validateIndices(i, j); if (isOpen(i, j)) return; grid[i-1][j-1] true; int current getIndex(i, j); // 连接相邻的已打开格子 connectToAdjacent(i, j, current); // 如果是首行则连接虚拟顶部 if (i 1) uf.union(current, virtualTop); // 如果是末行则连接虚拟底部 if (i size) uf.union(current, virtualBottom); } // 其他必要方法... }验收常见问题如何证明你的实现能够正确检测渗透为什么需要虚拟节点不使用的替代方案是什么如何计算渗透阈值蒙特卡洛模拟如何实现提示在渗透问题中采用虚拟顶部和底部节点可以显著降低算法复杂度从O(n²)降到接近O(1)的判断时间这是算法设计中的典型空间换时间策略。3. 排序算法性能比较理论与实践的结合排序算法比较实验要求实现多种排序算法并对其性能进行系统测试和分析。重点考察对不同数据特征随机、有序、逆序、重复等的适应性。实现算法对比算法平均时间复杂度最优情况最差情况空间复杂度稳定性插入排序O(n²)O(n)O(n²)O(1)稳定归并排序O(nlogn)O(nlogn)O(nlogn)O(n)稳定快速排序O(nlogn)O(nlogn)O(n²)O(logn)不稳定堆排序O(nlogn)O(nlogn)O(nlogn)O(1)不稳定关键优化技术小数组切换为插入排序通常阈值在5-15之间三取样切分优化快速排序避免对已有序数组的劣化public class SortCompare { public static double time(String alg, Double[] a) { Stopwatch timer new Stopwatch(); switch (alg) { case Insertion: Insertion.sort(a); break; case Merge: Merge.sort(a); break; case Quick: Quick.sort(a); break; case Heap: Heap.sort(a); break; default: throw new IllegalArgumentException(未知算法: alg); } return timer.elapsedTime(); } // 其他辅助方法... } // 快速排序优化示例 public class Quick { private static final int CUTOFF 10; public static void sort(Comparable[] a) { StdRandom.shuffle(a); // 消除对输入的依赖 sort(a, 0, a.length - 1); } private static void sort(Comparable[] a, int lo, int hi) { if (hi lo CUTOFF) { Insertion.sort(a, lo, hi); // 小数组切换为插入排序 return; } int j partition(a, lo, hi); sort(a, lo, j-1); sort(a, j1, hi); } // 三取样切分优化 private static int partition(Comparable[] a, int lo, int hi) { int m medianOf3(a, lo, lo (hi - lo)/2, hi); exch(a, lo, m); // 标准切分过程... } }验收常见问题为什么快速排序在实际应用中通常优于归并排序如何处理含有大量重复元素的数组排序如何证明排序算法的稳定性4. 地图路由Dijkstra算法的工程实践地图路由问题要求实现最短路径算法核心是Dijkstra算法的优化实现。实验重点在于处理大规模图数据时的性能优化。关键优化策略使用索引优先队列IndexMinPQ及早终止条件当目标节点出队时终止欧几里得启发式A*算法public class DijkstraSP { private double[] distTo; // distTo[v] 从s到v的最短距离 private DirectedEdge[] edgeTo; // edgeTo[v] 最短路径上的最后一条边 private IndexMinPQDouble pq; // 优先队列 public DijkstraSP(EdgeWeightedDigraph G, int s) { distTo new double[G.V()]; edgeTo new DirectedEdge[G.V()]; for (int v 0; v G.V(); v) distTo[v] Double.POSITIVE_INFINITY; distTo[s] 0.0; pq new IndexMinPQDouble(G.V()); pq.insert(s, distTo[s]); while (!pq.isEmpty()) { int v pq.delMin(); for (DirectedEdge e : G.adj(v)) relax(e); } } private void relax(DirectedEdge e) { int v e.from(), w e.to(); if (distTo[w] distTo[v] e.weight()) { distTo[w] distTo[v] e.weight(); edgeTo[w] e; if (pq.contains(w)) pq.decreaseKey(w, distTo[w]); else pq.insert(w, distTo[w]); } } // A*算法启发式优化 private void relax(DirectedEdge e, int target) { int v e.from(), w e.to(); double heuristic euclideanDistance(w, target); // 欧几里得距离启发 if (distTo[w] distTo[v] e.weight()) { distTo[w] distTo[v] e.weight(); edgeTo[w] e; double priority distTo[w] heuristic; // A*优先级 if (pq.contains(w)) pq.decreaseKey(w, priority); else pq.insert(w, priority); // 及早终止 if (w target) { while (!pq.isEmpty()) pq.delMin(); } } } }性能优化对比优化技术理论加速比实现复杂度适用场景标准Dijkstra1x简单通用索引优先队列2-5x中等大规模稀疏图A*启发式5-20x较高已知目标节点及早终止2-10x简单单源单目标验收常见问题Dijkstra算法如何处理负权边A*算法中启发式函数的选择如何影响性能如何验证算法找到的路径确实是最短的5. 文本索引字符串匹配算法实战文本索引实验要求实现高效的字符串搜索功能核心是选择合适的字符串匹配算法并优化其实现。Boyer-Moore算法因其在实际应用中的高效性成为常见选择。Boyer-Moore算法关键组件坏字符规则Bad Character Rule好后缀规则Good Suffix RuleGalil规则优化public class BoyerMoore { private final int R; // 字母表大小 private int[] badChar; // 坏字符跳转表 private int[] goodSuffix; // 好后缀跳转表 private String pat; // 模式字符串 public BoyerMoore(String pat) { this.R 256; this.pat pat; // 构建坏字符表 badChar new int[R]; for (int c 0; c R; c) badChar[c] -1; for (int j 0; j pat.length(); j) badChar[pat.charAt(j)] j; // 构建好后缀表 goodSuffix new int[pat.length()]; int[] suffix new int[pat.length()]; // 计算suffix数组 suffix[pat.length() - 1] pat.length(); for (int i pat.length() - 2; i 0; i--) { int j i; while (j 0 pat.charAt(j) pat.charAt(pat.length() - 1 - i j)) j--; suffix[i] i - j; } // 初始化好后缀表 for (int i 0; i pat.length(); i) goodSuffix[i] pat.length(); // 情况1完全匹配好后缀 for (int i pat.length() - 1; i 0; i--) { if (suffix[i] i 1) { for (int j 0; j pat.length() - 1 - i; j) { if (goodSuffix[j] pat.length()) goodSuffix[j] pat.length() - 1 - i; } } } // 情况2部分匹配好后缀 for (int i 0; i pat.length() - 1; i) { goodSuffix[pat.length() - 1 - suffix[i]] pat.length() - 1 - i; } } public int search(String txt) { int m pat.length(); int n txt.length(); int skip; for (int i 0; i n - m; i skip) { skip 0; for (int j m - 1; j 0; j--) { if (pat.charAt(j) ! txt.charAt(i j)) { skip Math.max(1, j - badChar[txt.charAt(i j)]); skip Math.max(skip, goodSuffix[j]); break; } } if (skip 0) return i; // 找到匹配 } return -1; // 未找到匹配 } }字符串匹配算法对比算法预处理时间匹配时间额外空间特点暴力匹配O(1)O(mn)O(1)实现简单KMPO(m)O(n)O(m)最差线性Boyer-MooreO(mR)O(n/m)O(mR)实践中最快Rabin-KarpO(m)O(n)O(1)适合多模式匹配验收常见问题Boyer-Moore算法在最坏情况下为何会退化为O(mn)如何扩展算法支持Unicode字符在实际文本编辑器中为什么通常不直接用Boyer-Moore算法