Brute-force Enumaration OR Abstract Conv
暴力枚举还是抽象化?
看清枚举与卷积的适用边界、复杂度差异与组合优化策略
按 空格/→ 演示下一步
全部页面点击任意一页,跳回舞台从这页播放
暴力枚举还是抽象化?
看清枚举与卷积的适用边界、复杂度差异与组合优化策略
什么是抽象化
上一页我们看到,把所有情况硬列出来既笨拙又难维护。有没有办法让一段代码应对「一类问题」,而不是只解决一个?
地图扔掉等高线、植被、材质,只留道路、比例、方位——本质是按需丢掉细节
抽象化三步法
三步从混沌问题走到普遍解。读图方向:从上往下三排,每排一个主阶段向下分叉出子动作后汇入下一阶段。
七桥问题的原始场景
抽象化三步法听起来很抽象?让我们回到 1736 年哥尼斯堡镇,看看一个真实的散步难题是如何催生这套方法的。
楼栋=陆地块,步道=桥;「每条步道恰好走一次」就是同款难题
要素抽象:陆地和桥
将半岛和岛屿抽象为顶点,桥抽象为边
七桥问题的图论模型
左框是地理地图,右框是图模型,中间箭头表示抽象过程。
顶点的度数与欧拉路径
上页我们把七桥问题抽象成了图:陆地为顶点,桥为边。但图只是骨架,能不能找到一条走遍所有边的路径,还要看每个顶点连着几条边——也就是'度数'。
每进一条街必出一条,中间路口成对进出;起终点可多一次出入
结论:为什么无解
上一页数出七桥图有四个奇数度顶点——这不只是一个统计结果,它直接判了七桥问题「死刑」。为什么?
中间每间房一进一出,用掉偶数扇门;只有头尾两间能多一扇
什么是对应关系
七桥问题的结论已经给出:那条欧拉路径不存在。回头看整条抽象路径——陆地对顶点、桥对边——每一步都贴着同一种关系走,那就是对应。下面把这件事拆开讲清楚。
凭票对号入座,座位号唯一指向某位观众;反过来也能查到谁坐过,是典型的一一对应
双射 vs 单射 vs 满射
单射管源头不撞车,满射管终点无遗漏;少看任一维度,对应关系就只剩半张图。
- 不同 x 必须映到不同 y(防合并)
- 反例:f(x)=x²,f(2)=f(-2)=4
- 集合约束:|定义域| ≤ |值域|
- 排列比喻:禁止两人挤一位
- 每个 y 都至少有一个 x 命中(防遗漏)
- 反例:f(x)=x²,负数永远打不到
- 集合约束:|定义域| ≥ |值域|
- 排列比喻:禁止留空座位
对应思想简化枚举
上页说清了双射是什么,这页看它能干什么——它的核心能力是「绕过难算的那一边」。当 A 难数、B 易数时,只要它们一一对应,数完 B 答案自然回到 A。
中文生词难查对应页码,但通过中英一一对应,英文词典(易查)的结果就是中文意思
世界杯的分组约束
七桥问的是"有没有解",世界杯则是"必须解"。32 支球队塞进 8 个小组、每组 4 队,听上去自由,其实每一条"恰好""不能"都是组合约束——把枚举空间从天文级压缩到"有意义"的解。
都要凑齐约束:能力均衡、好友不撞、性别配比,把任意排列筛成有结构的组合
约束条件的数学抽象
把分组规则逐条翻译成数学约束,让计算机能验证。
枚举方法 vs 抽象方法的对比
两条路径得到同一结论,代价天差地别。
枚举法与抽象法的适用场景
两种思路不互斥,但适用场景截然不同——混用往往事倍功半。
- 适用问题:有限集合内的具体实例
- 问题规模:组合空间小、可穷举
- 思维路径:列出所有候选 → 逐一筛选
- 输出结果:具体的解或方案列表
- 适用问题:具有共性、可提炼结构的类问题
- 问题规模:大规模或无限集合
- 思维路径:抽取本质 → 建立模型 → 求解
- 输出结果:通用方法或结构性结论
核心概念自测
验证对抽象化方法与图论基础的理解
课后思考
先独立想一分钟,再对照参考答案——三条思路可以放一起讨论。
参考答案对应关系把同类对象压成同一符号,让组合数从指数级坍缩到多项式级;缺了它,就只能逐一枚举。
参考答案队伍少(≤4 队)时枚举足够;国家数到 8 个以上组合爆炸,就要靠互斥约束和对称性约简。
参考答案不是。搜索空间小、不需要洞察规律时,枚举代码简单、结果完整;只有结构浮现且需复用规律时才转抽象。