作业三：Huffman、搜索、动态规划与博弈

Views: --
#作业

本次作业跨度很大：从真实文件压缩，到网格可达与区间覆盖、分层树形动态规划，再到 Nim 异或。共同点是先把题意压缩成一个结构清楚的数学模型。

1. Huffman 文件压缩实验

作业压缩程序的核心流程是：

  1. 统计每种符号出现频率；
  2. 用小根堆反复合并频率最小的两个结点；
  3. 从 Huffman 树生成前缀编码；
  4. 把编码位流打包成字节；
  5. 在压缩文件中保存解码所需的树或频率信息；
  6. 解压时逐位沿树行走，到叶子输出符号。

提交报告记录的示例从约 700 KB 压缩到约 420 KB，约为原大小的 60%。这个数字只能说明该样本的效果，不能当成 Huffman 对所有文件的固定压缩率。

压缩率为什么因文件而异

符号分布越不均匀，高频符号越能获得短码，收益越明显。若各字节频率接近，Huffman 码接近定长码；再加上码表头部，压缩文件甚至可能更大。

工程实现要补齐的边界

  • 统计的是原始字节还是 Unicode 字符，编码端和解码端必须一致；
  • 末字节的补零不能被误解为正文，要保存有效位数或原文长度；
  • 空文件和只有一种符号的文件需要专门处理；
  • 必须把码表、树或规范码信息写入文件，否则换一个进程无法解码；
  • 计算压缩率要把头部也算进去。

Huffman 的理论最优性针对给定符号频率下的二进制前缀码，不代表它优于字典压缩、算术编码或针对图片音频的专用编码。

2. 引水入域：可达性加区间覆盖

题目给出 N×MN\times M 高度网格，水只能从高处流向相邻的严格低处。需要从第一行选择若干蓄水站，让最后一行全部可达；若做不到，输出不可达位置数量。

第一步：判断是否全可达

从第一行所有格子同时 DFS/BFS，沿严格下降边移动。统计最后一行未访问的格子。若有不可达点，直接输出失败和数量。

一次多源搜索复杂度为 O(NM)O(NM)。

第二步：每个源点对应底部区间

若底行全部可达，再分别从每个顶行位置搜索，得到它能到达的底行最左列 LiL_i 与最右列 RiR_i。在该地形条件下，可达底部位置形成连续区间，于是问题变成：用最少区间覆盖 [1,M][1,M]。

第三步：贪心覆盖

按左端点排序，设下一个待覆盖位置为 pos。在所有 Li≤posL_i\le pos 的区间中，选择右端点最大的一个，把 pos 推到 Ri+1R_i+1。这是标准的最少区间覆盖贪心。

原程序为每个顶行格子单独 DFS，最坏约 O(NM2)O(NM^2)。若数据更大，可以用动态规划直接计算每个格子的底部可达区间，避免重复搜索。

3. 树上选点：按深度分层的 DP

从提交程序可确定的约束是：每一层至多选择一个顶点，而且相邻两层所选顶点不能是父子；每个顶点有价值，目标最大化总价值。

先 BFS 求每个顶点深度并按层分组。处理到深度 dd 时，状态有：

  • none[d]：第 dd 层不选点的最大价值；
  • choose[d][v]：第 dd 层选择顶点 vv 的最大价值。

转移为：

none[d]=max⁡(none[d−1],max⁡uchoose[d−1][u]),none[d]=\max\left(none[d-1],\max_u choose[d-1][u]\right), choose[d][v]=value[v]+max⁡(none[d−1],max⁡u≠parent[v]choose[d−1][u]).choose[d][v]=value[v]+\max\left( none[d-1], \max_{u\ne parent[v]}choose[d-1][u] \right).

若对每个 vv 都扫描上一层会平方级。程序维护上一层状态的最大值、次大值及最大值对应顶点：若最大值正好来自 parent[v]parent[v]，改用次大值；否则直接用最大值。于是每个顶点只处理常数次，总时间 O(n)O(n)。

这个技巧适用于“从全集最大值中排除至多一个禁用候选”的转移。

4. 永夜的报应：Nim 异或

提交程序把所有输入数做按位异或：

a1⊕a2⊕⋯⊕an.a_1\oplus a_2\oplus\cdots\oplus a_n.

这对应经典 Nim 博弈。若每个数表示一堆石子，玩家每次从一堆取走任意正数，最后无法行动者输，则：

  • 异或和为 0：当前局面必败；
  • 异或和非 0：当前局面必胜，并能一步把异或和变成 0。

证明关键是两点：从异或和 0 的状态走一步一定变成非 0；从非 0 状态总能找到一堆，把其最高差异位消掉并变成 0。

程序输出异或和本身，说明原题可能直接要求计算 Nim 和或以它作为答案，而不一定只输出胜负。这里保留源码能确认的算法，不猜测缺失题面中的输出文案。

5. 本次作业的共性

  • Huffman：把频率变成加权树路径长度；
  • 引水入域：把网格搜索结果变成区间覆盖；
  • 树上选点：把树按深度压成相邻层状态；
  • Nim：把整局博弈压成一个异或不变量。

算法设计的核心往往不是把代码写快，而是找到足以代表原问题的更小结构。

评论