Brute-force Enumaration OR Abstract Conv

官方信息技术老师·17 页·深入(追求细节与边界)·0 次浏览·2 天前
组合计数暴力枚举卷积

暴力枚举还是抽象化?

看清枚举与卷积的适用边界、复杂度差异与组合优化策略

按 空格/→ 演示下一步

1 / 17 页

全部页面点击任意一页,跳回舞台从这页播放

组合计数暴力枚举卷积

暴力枚举还是抽象化?

看清枚举与卷积的适用边界、复杂度差异与组合优化策略

1第 1 页 · 暴力枚举还是抽象化?

什么是抽象化

上一页我们看到,把所有情况硬列出来既笨拙又难维护。有没有办法让一段代码应对「一类问题」,而不是只解决一个?

剥离非本质
把具体数值、形态、场景中与目标无关的部分丢掉
保留共性结构
提取一类事物背后反复出现的模式或关系
形成可复用模型
用更通用的符号、接口或公式重新表达这套结构
地图对应 →抽象化

地图扔掉等高线、植被、材质,只留道路、比例、方位——本质是按需丢掉细节

2第 2 页 · 什么是抽象化

抽象化三步法

三步从混沌问题走到普遍解。读图方向:从上往下三排,每排一个主阶段向下分叉出子动作后汇入下一阶段。

图解渲染中…
b1识别要素:从原问题里拆出驱动变量c1建立映射:要素间建立对应,决定取与舍d1构建模型:用统一抽象表示承载并求解
3第 3 页 · 抽象化三步法

七桥问题的原始场景

抽象化三步法听起来很抽象?让我们回到 1736 年哥尼斯堡镇,看看一个真实的散步难题是如何催生这套方法的。

普雷格尔河与四块陆地
普雷格尔河穿城,把陆地分成四块:北岸、南岸、Kneiphof 岛、小岛
七桥配置
Kneiphof 岛 5 条(向北 2、向南 2、向小岛 1),小岛 3 条(向北 1、向南 1、向 Kneiphof 1)
散步挑战
从任一块陆地出发,每座桥恰好走一次,能不重复地走完所有七桥吗?
枚举为何失败
路径组合随桥数指数增长,凭手算无法证明「不存在这样的路线」
小区几栋楼之间的步道对应 →哥尼斯堡四块陆地与七桥

楼栋=陆地块,步道=桥;「每条步道恰好走一次」就是同款难题

4第 4 页 · 七桥问题的原始场景

要素抽象:陆地和桥

将半岛和岛屿抽象为顶点,桥抽象为边

要素抽象:陆地和桥
将半岛和岛屿抽象为顶点,桥抽象为边
5第 5 页 · 要素抽象:陆地和桥

七桥问题的图论模型

左框是地理地图,右框是图模型,中间箭头表示抽象过程。

图解渲染中…
A1原地图中的4块陆地(候选顶点)A2抽象后的4个顶点(已忽略形状)b1原地图中的桥梁,在图中变成边或重边
6第 6 页 · 七桥问题的图论模型

顶点的度数与欧拉路径

上页我们把七桥问题抽象成了图:陆地为顶点,桥为边。但图只是骨架,能不能找到一条走遍所有边的路径,还要看每个顶点连着几条边——也就是'度数'。

度数的定义
一个顶点上连接的边的数量,记作 deg(v)
进出配对原则
中间顶点每次进出一一对应,因此度数必须为偶数
欧拉定理
奇度顶点为 0 个 ⟺ 欧拉回路;恰好 2 个 ⟺ 欧拉路径
回到七桥
哥尼斯堡 4 个顶点全是奇数度,违反定理,故无解
快递员走遍每条街对应 →欧拉路径的存在条件

每进一条街必出一条,中间路口成对进出;起终点可多一次出入

{vdeg(v) 为奇数}{0,2}|\{v \mid \deg(v) \text{ 为奇数}\}| \in \{0, 2\}
7第 7 页 · 顶点的度数与欧拉路径

结论:为什么无解

上一页数出七桥图有四个奇数度顶点——这不只是一个统计结果,它直接判了七桥问题「死刑」。为什么?

中间顶点度数必为偶数
路径每经过一个非起终点顶点,必须一进一出,消耗偶数条边
仅起点或终点可奇数
多出的那一次进入或离开,只能发生在路径的两端
至多2个奇数度顶点
由前两点推出:存在欧拉路径时,奇数度顶点数 ≤ 2
七桥有4个奇数度顶点
突破上限2,无论怎么走都不可能让每条桥恰好经过一次
穿行一串相连的房间对应 →路径经过中间顶点

中间每间房一进一出,用掉偶数扇门;只有头尾两间能多一扇

8第 8 页 · 结论:为什么无解

什么是对应关系

七桥问题的结论已经给出:那条欧拉路径不存在。回头看整条抽象路径——陆地对顶点、桥对边——每一步都贴着同一种关系走,那就是对应。下面把这件事拆开讲清楚。

两个集合
抽象前后各有独立集合,例如「真实陆地」与「抽象顶点」
匹配规则
明确每个元素指向对方集合里的哪个元素,不是凭感觉
一一对应
通常无重复无遗漏,每个原像有且只有一个像
保持结构
必须保留关键关系,如「桥连着哪些陆地」映射到「边连着哪些顶点」
影厅座位号与观众对应 →两集合的对应关系

凭票对号入座,座位号唯一指向某位观众;反过来也能查到谁坐过,是典型的一一对应

f:AB,aA, !bB:b=f(a)f: A \to B,\quad \forall a \in A,\ \exists!\, b \in B: b = f(a)
9第 9 页 · 什么是对应关系

双射 vs 单射 vs 满射

单射管源头不撞车,满射管终点无遗漏;少看任一维度,对应关系就只剩半张图。

单射:源头不撞车
  • 不同 x 必须映到不同 y(防合并)
  • 反例:f(x)=x²,f(2)=f(-2)=4
  • 集合约束:|定义域| ≤ |值域|
  • 排列比喻:禁止两人挤一位
满射:终点无遗漏
  • 每个 y 都至少有一个 x 命中(防遗漏)
  • 反例:f(x)=x²,负数永远打不到
  • 集合约束:|定义域| ≥ |值域|
  • 排列比喻:禁止留空座位
双射 = 单射 ∧ 满射:两条件必须同时成立,才是真正的完美一一对应,缺一不可。
10第 10 页 · 双射 vs 单射 vs 满射

对应思想简化枚举

上页说清了双射是什么,这页看它能干什么——它的核心能力是「绕过难算的那一边」。当 A 难数、B 易数时,只要它们一一对应,数完 B 答案自然回到 A。

核心招式:换集合计数
A 与 B 一一对应时,数 B 就等于数 A
挑容易的那一边
把难数的集合 A 换成易数的集合 B 来处理
构造一一对应
显式定义映射规则 f,确保既不漏也不重
把答案搬回来
通过 f 的逆映射,把 B 的计数结果还原回 A
查英文词典对应 →对应计数

中文生词难查对应页码,但通过中英一一对应,英文词典(易查)的结果就是中文意思

11第 11 页 · 对应思想简化枚举

世界杯的分组约束

七桥问的是"有没有解",世界杯则是"必须解"。32 支球队塞进 8 个小组、每组 4 队,听上去自由,其实每一条"恰好""不能"都是组合约束——把枚举空间从天文级压缩到"有意义"的解。

分档抽签
按 FIFA 排名把 32 队分 4 档,每组强制"每档一队",避免强队扎堆
同大洲回避
欧足联球队同组≤2 支、其余大洲≤1 支,强制地域平衡
小组定容
32 队必须组成 8 组×4 队,多一支不可、少一支也不可
赛程嵌套
小组内循环 6 场 → 前 2 出线 → 16 强单败淘汰,分阶段压缩
班级/项目分组对应 →世界杯抽签

都要凑齐约束:能力均衡、好友不撞、性别配比,把任意排列筛成有结构的组合

32!(4!)88!2.6×1027\dfrac{32!}{(4!)^{8}\cdot 8!}\approx 2.6\times 10^{27}
12第 12 页 · 世界杯的分组约束

约束条件的数学抽象

把分组规则逐条翻译成数学约束,让计算机能验证。

1
设定变量
用 x[i,j]=1 表示 i 队进入 j 组
2
回避约束
同组两队不能同组:x[i,j]·x[k,j]=0
3
公平约束
各组强队数差不超过 1
4
完整约束
每队恰入一组,每组人数相同
13第 13 页 · 约束条件的数学抽象

枚举方法 vs 抽象方法的对比

两条路径得到同一结论,代价天差地别。

图解渲染中…
Q起点:判断这类问题是否有解L37!=5040种走法都要逐一回溯R2只算4个顶点的度数即够End殊途同归,但成本天差地别
14第 14 页 · 枚举方法 vs 抽象方法的对比

枚举法与抽象法的适用场景

两种思路不互斥,但适用场景截然不同——混用往往事倍功半。

枚举法
  • 适用问题:有限集合内的具体实例
  • 问题规模:组合空间小、可穷举
  • 思维路径:列出所有候选 → 逐一筛选
  • 输出结果:具体的解或方案列表
抽象化法
  • 适用问题:具有共性、可提炼结构的类问题
  • 问题规模:大规模或无限集合
  • 思维路径:抽取本质 → 建立模型 → 求解
  • 输出结果:通用方法或结构性结论
规模小选枚举,结构清晰选抽象;先抽框架再用枚举细化——这是混合策略的核心。
15第 15 页 · 枚举法与抽象法的适用场景

核心概念自测

验证对抽象化方法与图论基础的理解

核心概念自测
验证对抽象化方法与图论基础的理解
16第 16 页 · 核心概念自测

课后思考

先独立想一分钟,再对照参考答案——三条思路可以放一起讨论。

1为什么说「对应关系」是抽象化的核心?没有它会出什么问题?

参考答案对应关系把同类对象压成同一符号,让组合数从指数级坍缩到多项式级;缺了它,就只能逐一枚举。

2世界杯分组里,哪些约束适合直接枚举?哪些必须先抽象?

参考答案队伍少(≤4 队)时枚举足够;国家数到 8 个以上组合爆炸,就要靠互斥约束和对称性约简。

3抽象是不是总比枚举好?什么场景下枚举反而更合适?

参考答案不是。搜索空间小、不需要洞察规律时,枚举代码简单、结果完整;只有结构浮现且需复用规律时才转抽象。

17第 17 页 · 课后思考