12.2 综合项目：建模并优化智慧城市网络

最后一节是一项有引导的设计项目。这里不会毫无铺垫地引入新的数学主题，而是把整门课的思想连接起来：集合描述对象，逻辑表达规则，函数与关系连接数据，证明支撑结论，算法执行决策，计数衡量可能性，概率表示不确定性，树组织选择，图表示路线，布尔电路作出即时判断，有限状态机控制随时间展开的行为。

我们的场景是一座小型智慧城市。救护车与消防车需要迅速到达事故地点，路口必须安全地切换信号灯阶段，而有限预算要投入真正能提升韧性的升级项目。

1. 把现实叙述翻译成数学模型

在优化之前，先找出对象和问题。

城市里有六个重要地点：

V=\{H,F,C,N,S,P\},

其中 $H$ 是医院， $F$ 是消防站， $C$ 是中心路口， $N$ 和 $S$ 分别是北区与南区， $P$ 是电力站。

道路连接地点。用 $E$ 表示道路集合。以分钟计的通行时间是一个权函数

w:E\to\mathbb{R}_{>0},

其中 $\mathbb{R}_{>0}$ 表示正实数集合。三者合在一起得到加权图

G=(V,E,w).

道路	正常时间	道路	正常时间
$HC$	$4$	$FC$	$3$
$HN$	$6$	$FS$	$5$
$CN$	$2$	$CS$	$4$
$CP$	$5$	$NP$	$3$
$SP$	$4$

字母 $HC$ 表示边 $\{H,C\}$ ，不是乘法。如果道路允许以相同时间双向通行，就用无向图。道路封闭会暂时删除一条边；道路拥堵则会改变边权，而不是删边。

问题决定使用哪种结构

同一个真实系统往往需要多个模型：

问题	数学结构
有哪些地点和道路？	集合与图
最快的应急路线是哪条？	加权最短路
是否应发出优先请求？	布尔函数
信号灯下一步进入哪个阶段？	有限状态机
预算内有多少种升级组合？	系统计数
不确定事故下的平均延迟是多少？	概率与期望
为什么两个冲突方向不会同时绿灯？	不变式与证明

只选择“图”并不等于完成建模。好模型必须说明每个顶点、边、权重、比特、状态和事件在现实中分别代表什么。

2. 分开即时判断与时序控制

假设中心路口观察三个输入比特：

$e=1$ 表示应急车辆请求优先通行；
$r=1$ 表示普通道路传感器检测到排队；
$p=1$ 表示人行横道正在通行。

定义布尔请求信号

u=e\lor(r\land\neg p).

它表示：应急请求会令 $u=1$ ；普通请求只有在人行横道未启用时才会令 $u=1$ 。特别要注意， $u=1$ 不等于“立刻亮绿灯”，而是请求状态机启动一个安全的切换过程。

信号控制器有四个状态：

Q=\{\text{Normal},\text{Clear},\text{Priority},\text{Recover}\}.

Normal：运行普通信号周期；
Clear：所有机动车方向暂时停止，让路口清空；
Priority：为应急路线提供绿灯；
Recover：再次清空路口，再回到普通周期。

简化的转移流程为

\text{Normal}\xrightarrow{u=1}\text{Clear} \xrightarrow{\text{清空计时结束}}\text{Priority} \xrightarrow{e=0}\text{Recover} \xrightarrow{\text{清空计时结束}}\text{Normal}.

这里体现了一条设计原则：

\text{传感器} \longrightarrow\text{布尔请求} \longrightarrow\text{状态转移} \longrightarrow\text{安全输出}.

电路回答当前的“是或否”问题；状态机则保证系统按安全顺序随时间运行。

3. 调度必须依靠算法，而不是猜测

当 $N$ 区发生事故时，城市要比较从医院和消防站出发的路线。所有道路权重都是正数，所以可以使用第 11 章的 Dijkstra 算法计算最短通行时间。

从 $H$ 出发，Dijkstra 算法先得到暂定标签 $d(C)=4$ 与 $d(N)=6$ 。因为 $4<6$ ，下一步确定 $C$ ；松弛边 $CN$ 会提出候选值 $4+2=6$ ，所以 $N$ 的标签仍为 $6$ 。此时其他未确定标签都更大，下一步即可确定 $N$ 。因此：

\operatorname{dist}(H,N) =\min\{w(HN),w(HC)+w(CN)\} =\min\{6,4+2\}=6.

这里有两条不同的最短路线 $H\!-\!N$ 与 $H\!-\!C\!-\!N$ ，总时间都是 $6$ 。这提醒我们：最短距离的数值可以唯一，但达到它的最短路径不一定唯一。

如果道路 $HN$ 封闭，剩余路线 $H\!-\!C\!-\!N$ 仍需 $6$ 分钟，因此网络对这次故障具有冗余。如果 $CN$ 也封闭，或许仍可通过 $P$ 到达 $N$ ，但通行时间会改变。连通性回答“服务是否仍然可用”；最短距离回答“保留下来的服务代价有多大”。

正在加载交互实验...

在实时城市地图上封闭道路或增加拥堵，比较调度路线，计算优先请求电路，再推进信号控制器，直到所选车辆获得受保护的通行阶段。

正在加载概念检查...

正在加载本节练习...

4. 先写需求，再选择升级

只有相对于明确需求，才能说某次升级是否“更好”。本项目采用四项需求：

1. 可达性：任意一条道路失效后，每个城区仍必须连通至少一个应急站点。 2. 响应时间：期望应急通行时间应尽量小。 3. 安全性：互相冲突的车辆方向永远不能同时亮绿灯。 4. 预算：安装总成本不能超过 $B$ 。

假设有 $m$ 个候选升级项目。定义决策比特

x_i= \begin{cases} 1, & \text{安装第 }i\text{ 项升级},\\ 0, & \text{不安装第 }i\text{ 项升级}. \end{cases}

如果第 $i$ 项升级的成本为 $c_i$ ，预算约束就是

\sum_{i=1}^{m}c_i x_i\le B.

求和式会加总所有被选升级的成本，因为 $x_i=0$ 的项目对总和没有贡献。

不同升级项目可能产生不同作用：

升级类型	对模型的改变
备用道路	向 $E$ 中加入一条边
交通传感器	检测成功时降低拥堵边的权重
备用控制器	降低信号控制器失效的概率

如果只比较购买成本，就会忽略这些不同收益。

5. 用场景描述不确定性

一个场景是事故日可能出现的一种情况，包括事故地点、拥堵模式、道路故障和控制器状态。令有限场景集合为

\Omega=\{\omega_1,\omega_2,\ldots,\omega_n\}.

为场景 $\omega_j$ 指定概率 $\Pr(\omega_j)$ ，并满足

\Pr(\omega_j)\ge 0 \quad\text{且}\quad \sum_{j=1}^{n}\Pr(\omega_j)=1.

对升级方案 $x$ ，令 $T(x,\omega_j)$ 表示场景 $\omega_j$ 中的最短应急响应时间。它的期望值是

\mathbb{E}[T\mid x] =\sum_{j=1}^{n}\Pr(\omega_j)\,T(x,\omega_j).

这就是第 9 章的加权平均。发生概率虽低但后果严重的断连不应悄悄消失，因此定义：如果场景 $\omega_j$ 中应急服务中断，则 $L(x,\omega_j)=1$ ，否则为 $0$ 。于是

\Pr(\text{服务中断}\mid x) =\sum_{j=1}^{n}\Pr(\omega_j)L(x,\omega_j).

6. 明确表达取舍

目标函数把一个候选设计转换为要最小化的分数。例如

J(x)= \alpha\,\mathbb{E}[T\mid x] +\beta\sum_{i=1}^{m}c_i x_i +\gamma\,\Pr(\text{服务中断}\mid x),

其中 $\alpha,\beta,\gamma\ge 0$ 是政策权重：

$\alpha$ 表示对响应时间的重视程度；
$\beta$ 表示对安装成本的重视程度；
$\gamma$ 表示对避免服务中断的重视程度。

这些权重不是概率。它们表达优先级，并让不同单位的量可以放在一起比较。改变权重可能改变最优方案，因此负责任的报告应写明权重，并检验在其他合理权重下建议是否稳定。

有些时候，安全和预算应当成为不可交换的硬约束：

\begin{aligned} \text{最小化 }&\mathbb{E}[T\mid x]\\ \text{满足 }& \sum_{i=1}^{m}c_i x_i\le B,\\ &\text{单条道路故障后的可达性要求成立},\\ &\text{信号安全不变式成立}. \end{aligned}

这种写法绝不会因为某个方案速度快，就接受一个不安全的设计。

7. 系统搜索所有可行设计

有 $m$ 个“选或不选”的升级项目，在应用预算之前共有 $2^m$ 个子集。对于规模较小的综合项目，可以使用穷举搜索：

1. 生成每个比特向量 $(x_1,\ldots,x_m)\in\{0,1\}^m$ ； 2. 如果成本超过 $B$ ，立即淘汰； 3. 检查图约束与控制器约束； 4. 模拟每一个场景； 5. 计算目标函数； 6. 保留得分最好的可行设计。

这个过程连接了多个章节：

\text{计数候选方案} \to\text{用逻辑筛选} \to\text{运行图算法} \to\text{按概率加权} \to\text{比较结果}.

当 $m$ 较大时， $2^m$ 会像第 5 章所述那样迅速增长，这时需要更聪明的优化方法。不过，在本项目中穷举非常有价值：它过程透明，还能给出一份完整证书——每一个可行方案都确实被比较过。

8. 验证、压力测试与证明

模拟提供的是“已经测试过的场景”的证据；证明覆盖的是“假设范围内的所有情况”。可靠设计需要两者配合。

图模型验证

对每条允许失效的边 $f\in E$ ：

1. 构造剩余图 $G-f$ ； 2. 分别从 $H$ 和 $F$ 运行 BFS； 3. 验证每个城区至少属于其中一个已访问集合。

控制器安全不变式

令 $n=1$ 表示南北方向绿灯， $s=1$ 表示东西方向绿灯。安全要求为

\neg(n\land s).

证明时，要检查每个可达控制器状态的输出，说明不存在任何状态输出 $n=s=1$ ；然后再检查每条转移始终留在这些安全状态中。

边界测试与对抗测试

不要只测试普通的一天，还要覆盖：

没有应急请求；
道路传感器与行人请求同时到达；
应急事件在 Clear 状态中结束；
每一种单条道路故障；
模型允许的最大拥堵；
预算恰好等于所选升级总成本。

这些测试集中攻击定义发生变化的边界，而实现错误常常藏在那里。

正在加载交互实验...

把不断变化的预算分配给备用道路、传感器和控制器；重放固定的一组事故日，检查每个场景对结果的贡献，再与穷举搜索给出的最佳可行方案证书竞争。

正在加载概念检查...

正在加载本节练习...

9. 最终设计论证

完整的综合项目成果不只是一张地图或一个分数，而应是一条由数学证据支撑的主张链：

\boxed{ \text{需求} \to\text{模型} \to\text{算法} \to\text{结果} \to\text{验证} }

请按以下清单检查：

1. 定义：说明每个集合、图元素、权重、随机变量、比特、状态和输入的含义。 2. 假设：说明哪些道路双向通行、考虑哪些故障、场景概率如何确定。 3. 方法正确：解释算法为什么适用，例如 Dijkstra 算法要求非负权重。 4. 计算可复现：展示路线总权重、状态转移轨迹、场景表和预算求和。 5. 证明义务：证明安全不变式和所要求的故障韧性。 6. 取舍：说明改善了什么、付出了什么成本、还有哪些不确定性。

10. 全课程综合

城市模型揭示了离散数学的统一思想：只要识别有限的对象，精确定义关系与规则，并从定义出发推理，复杂系统就会变得可以理解。

课程思想	在综合项目中的作用
集合与函数	定义地点、道路、权重与输出
逻辑与证明	表达需求并证明安全性
关系	描述连通性与可达性
算法与复杂度	执行计算并判断搜索是否可扩展
计数	枚举升级方案与场景
递推与树	组织递归搜索和决策
数论	在需要时支持安全通信
概率	量化不确定的拥堵与故障
图	建模路线与网络韧性
布尔电路	组合当前传感器信号
有限状态机	保证系统随时间安全运行

课程一开始，我们提出了“如何把现实情境变成离散模型”这个问题。现在可以用一套严谨流程回答：定义对象，选择能保留关键关系的结构，用明确算法计算，再用证明与测试论证结果。这套工作方式——而不是某一个孤立公式——才是离散数学留给你的长久工具。

12.2 综合项目：建模并优化智慧城市网络

1. 把现实叙述翻译成数学模型

在优化之前，先找出对象和问题。

城市里有六个重要地点：

V=\{H,F,C,N,S,P\},

其中 $H$ 是医院， $F$ 是消防站， $C$ 是中心路口， $N$ 和 $S$ 分别是北区与南区， $P$ 是电力站。

道路连接地点。用 $E$ 表示道路集合。以分钟计的通行时间是一个权函数

w:E\to\mathbb{R}_{>0},

其中 $\mathbb{R}_{>0}$ 表示正实数集合。三者合在一起得到加权图

G=(V,E,w).

道路	正常时间	道路	正常时间
$HC$	$4$	$FC$	$3$
$HN$	$6$	$FS$	$5$
$CN$	$2$	$CS$	$4$
$CP$	$5$	$NP$	$3$
$SP$	$4$

问题决定使用哪种结构

同一个真实系统往往需要多个模型：

问题	数学结构
有哪些地点和道路？	集合与图
最快的应急路线是哪条？	加权最短路
是否应发出优先请求？	布尔函数
信号灯下一步进入哪个阶段？	有限状态机
预算内有多少种升级组合？	系统计数
不确定事故下的平均延迟是多少？	概率与期望
为什么两个冲突方向不会同时绿灯？	不变式与证明

只选择“图”并不等于完成建模。好模型必须说明每个顶点、边、权重、比特、状态和事件在现实中分别代表什么。

2. 分开即时判断与时序控制

假设中心路口观察三个输入比特：

$e=1$ 表示应急车辆请求优先通行；
$r=1$ 表示普通道路传感器检测到排队；
$p=1$ 表示人行横道正在通行。

定义布尔请求信号

u=e\lor(r\land\neg p).

信号控制器有四个状态：

Q=\{\text{Normal},\text{Clear},\text{Priority},\text{Recover}\}.

Normal：运行普通信号周期；
Clear：所有机动车方向暂时停止，让路口清空；
Priority：为应急路线提供绿灯；
Recover：再次清空路口，再回到普通周期。

简化的转移流程为

\text{Normal}\xrightarrow{u=1}\text{Clear} \xrightarrow{\text{清空计时结束}}\text{Priority} \xrightarrow{e=0}\text{Recover} \xrightarrow{\text{清空计时结束}}\text{Normal}.

这里体现了一条设计原则：

\text{传感器} \longrightarrow\text{布尔请求} \longrightarrow\text{状态转移} \longrightarrow\text{安全输出}.

电路回答当前的“是或否”问题；状态机则保证系统按安全顺序随时间运行。

3. 调度必须依靠算法，而不是猜测

当 $N$ 区发生事故时，城市要比较从医院和消防站出发的路线。所有道路权重都是正数，所以可以使用第 11 章的 Dijkstra 算法计算最短通行时间。

\operatorname{dist}(H,N) =\min\{w(HN),w(HC)+w(CN)\} =\min\{6,4+2\}=6.

这里有两条不同的最短路线 $H\!-\!N$ 与 $H\!-\!C\!-\!N$ ，总时间都是 $6$ 。这提醒我们：最短距离的数值可以唯一，但达到它的最短路径不一定唯一。

正在加载交互实验...

在实时城市地图上封闭道路或增加拥堵，比较调度路线，计算优先请求电路，再推进信号控制器，直到所选车辆获得受保护的通行阶段。

正在加载概念检查...

正在加载本节练习...

4. 先写需求，再选择升级

只有相对于明确需求，才能说某次升级是否“更好”。本项目采用四项需求：

假设有 $m$ 个候选升级项目。定义决策比特

x_i= \begin{cases} 1, & \text{安装第 }i\text{ 项升级},\\ 0, & \text{不安装第 }i\text{ 项升级}. \end{cases}

如果第 $i$ 项升级的成本为 $c_i$ ，预算约束就是

\sum_{i=1}^{m}c_i x_i\le B.

求和式会加总所有被选升级的成本，因为 $x_i=0$ 的项目对总和没有贡献。

不同升级项目可能产生不同作用：

升级类型	对模型的改变
备用道路	向 $E$ 中加入一条边
交通传感器	检测成功时降低拥堵边的权重
备用控制器	降低信号控制器失效的概率

如果只比较购买成本，就会忽略这些不同收益。

5. 用场景描述不确定性

一个场景是事故日可能出现的一种情况，包括事故地点、拥堵模式、道路故障和控制器状态。令有限场景集合为

\Omega=\{\omega_1,\omega_2,\ldots,\omega_n\}.

为场景 $\omega_j$ 指定概率 $\Pr(\omega_j)$ ，并满足

\Pr(\omega_j)\ge 0 \quad\text{且}\quad \sum_{j=1}^{n}\Pr(\omega_j)=1.

对升级方案 $x$ ，令 $T(x,\omega_j)$ 表示场景 $\omega_j$ 中的最短应急响应时间。它的期望值是

\mathbb{E}[T\mid x] =\sum_{j=1}^{n}\Pr(\omega_j)\,T(x,\omega_j).

\Pr(\text{服务中断}\mid x) =\sum_{j=1}^{n}\Pr(\omega_j)L(x,\omega_j).

6. 明确表达取舍

目标函数把一个候选设计转换为要最小化的分数。例如

J(x)= \alpha\,\mathbb{E}[T\mid x] +\beta\sum_{i=1}^{m}c_i x_i +\gamma\,\Pr(\text{服务中断}\mid x),

其中 $\alpha,\beta,\gamma\ge 0$ 是政策权重：

$\alpha$ 表示对响应时间的重视程度；
$\beta$ 表示对安装成本的重视程度；
$\gamma$ 表示对避免服务中断的重视程度。

有些时候，安全和预算应当成为不可交换的硬约束：

\begin{aligned} \text{最小化 }&\mathbb{E}[T\mid x]\\ \text{满足 }& \sum_{i=1}^{m}c_i x_i\le B,\\ &\text{单条道路故障后的可达性要求成立},\\ &\text{信号安全不变式成立}. \end{aligned}

这种写法绝不会因为某个方案速度快，就接受一个不安全的设计。

7. 系统搜索所有可行设计

有 $m$ 个“选或不选”的升级项目，在应用预算之前共有 $2^m$ 个子集。对于规模较小的综合项目，可以使用穷举搜索：

这个过程连接了多个章节：

\text{计数候选方案} \to\text{用逻辑筛选} \to\text{运行图算法} \to\text{按概率加权} \to\text{比较结果}.

8. 验证、压力测试与证明

模拟提供的是“已经测试过的场景”的证据；证明覆盖的是“假设范围内的所有情况”。可靠设计需要两者配合。

图模型验证

对每条允许失效的边 $f\in E$ ：

1. 构造剩余图 $G-f$ ； 2. 分别从 $H$ 和 $F$ 运行 BFS； 3. 验证每个城区至少属于其中一个已访问集合。

控制器安全不变式

令 $n=1$ 表示南北方向绿灯， $s=1$ 表示东西方向绿灯。安全要求为

\neg(n\land s).

证明时，要检查每个可达控制器状态的输出，说明不存在任何状态输出 $n=s=1$ ；然后再检查每条转移始终留在这些安全状态中。

边界测试与对抗测试

不要只测试普通的一天，还要覆盖：

没有应急请求；
道路传感器与行人请求同时到达；
应急事件在 Clear 状态中结束；
每一种单条道路故障；
模型允许的最大拥堵；
预算恰好等于所选升级总成本。

这些测试集中攻击定义发生变化的边界，而实现错误常常藏在那里。

正在加载交互实验...

正在加载概念检查...

正在加载本节练习...

9. 最终设计论证

完整的综合项目成果不只是一张地图或一个分数，而应是一条由数学证据支撑的主张链：

\boxed{ \text{需求} \to\text{模型} \to\text{算法} \to\text{结果} \to\text{验证} }

请按以下清单检查：

10. 全课程综合

城市模型揭示了离散数学的统一思想：只要识别有限的对象，精确定义关系与规则，并从定义出发推理，复杂系统就会变得可以理解。

课程思想	在综合项目中的作用
集合与函数	定义地点、道路、权重与输出
逻辑与证明	表达需求并证明安全性
关系	描述连通性与可达性
算法与复杂度	执行计算并判断搜索是否可扩展
计数	枚举升级方案与场景
递推与树	组织递归搜索和决策
数论	在需要时支持安全通信
概率	量化不确定的拥堵与故障
图	建模路线与网络韧性
布尔电路	组合当前传感器信号
有限状态机	保证系统随时间安全运行