1 / 7
车辆行驶路径复杂度：从七巧板到柯西不等式
作者：Xiang Shan
近日，在与某些外部主流机构沟通交流时，发现计算机动车辆“行驶路径离散度”
的主流算法（离散度：计算行驶路径复杂度的一种方法）存在度量域过宽的错误。在指
出其缺陷后，以严谨推导建议其更正。今日形成此文，以对话方式呈现。
Q：如何度量某辆汽车在地图上行驶路径越复杂度？
A：首先，我们可以在地图上绘制过去一段时间内，该车辆每次行程的行驶路径图。
为了让绘制简化，不妨忽略每次行程途径的具体街道，而只是用“直线”连接行程的起
点与终点，即“向量”表示。
那些日常行驶固定通勤路线的上班一族，自然比营运车辆路线更为固定，在视觉上
呈现路径图更“简洁”。如下图：车辆 A 路线简洁；车辆 B 路线复杂。
图 1：车辆行驶路径案例
2 / 7
Q：你这种将行驶路线简化为“向量”的表示方法，让我联想起“哥尼斯堡七
桥”问题。如果借助图论的思考方式，问题可以进一步简化吗？
图 2：哥尼斯堡七桥问题
A：啊哈！你说的没错，欧拉就是将该问题抽象为一笔画问题，开创了图论。我们也
可以效仿，将每次行程的起终点抽象为“点”，用地点名称来描述这些点；对于每次行程
“向量”，进一步简化为“线”，忽略其方向性，甚至我们连“线”的长度都可以忽略。
这些简化，将使得分析行驶路径复杂性问题变得简洁。此时，我们可以将问题重新
表述为如下集合的映射：
Step1：将某车辆观测期内，第?次行程的起终点记为?????? = [??
, ??
]。于是，将观
测期内所有行程合并成数组?，则集合{?} = {?1, ?2, ?3, ⋯ , ??}表示在观测期内车辆共起
终过?个地点，用??表示地点?。例如，某辆车观测期内有 3 次行程，分别为[国贸, 亮
马桥], [亮马桥, 天安门], [天安门, 天坛]，则{?} = {国贸,亮马桥,天安门,天坛}。
Step2：计量经过地点次数{?}，令{?} = ?({?}) = {?1,?2,?3, ⋯ ,??}，其中??表示经过
地点??的次数。例如{?} = {国贸,亮马桥,天安门,天坛}对应{?} = {1,1, 2, 1}。
事实上，即便相邻两次行程是不连续的（如，信息记录缺失），即上一个行程的终点
不是下一个行程的起点，也不会影响上述记录方式。容易知道，集合{?}中元素个数?即
可以是奇数、也可以是偶数，而集合{?}中所有元素的值求和（记为???）一定是偶数。
这是因为每个行程一定有起、终点，每完成一次行程会使得???增加 2。
3 / 7
Q：有趣，通过集合表述的方式，现在确实把问题简化了！下一步，该如何描
述路径复杂度呢？
A：直觉上，固定路径通勤的车辆，途径地点会比较集中，而路径复杂的车辆途径地
点会十分离散，如图 1 所示。因此，我们只需要能在数学上描述途径地点的离散程度，
就能在某种程度上近似刻画路径复杂度。例如，你可以想象用途径地点次数的重数与均
值的差异来描述，两者越是接近，行驶路径可能越离散；也可以使用熵理论（信息熵）
来度量离散度等。
最近在陪家里小朋友玩七巧板，这里想从几何为出发点，讨论一种刻画途径地点离
散程度的方法。
不妨令{?}中所有元素的值求和??? = 20，用边长 20 围成正立方体，表示起终点总
是重合，如图 3 左上图示，其面积记为???2
；若该车辆只途径{?1, ?2
}，则有{?1,?2
} =
{10, 10}，用边长 10 的正方形分别表示?1和?2，面积分别为?1
2和?2
2，如图 3 右上图示；
以此类推，分别绘制途径{?1, ?2, ?3
}和{?1, ?2, ?3, ?4
}情形。从图 3 中看出，随着途径地点
的增加，途径点的正方形面积之和逐渐减小，满足如下公式：
???2 ≥ (?1
2 + ?2
2
) ≥ (?1
2 + ?2
2 + ?3
2
) ≥ (?1
2 + ?2
2 + ?3
2 + ?4
2
), ??? = ∑ ??
?
?=1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
SUM
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
p1
p2
4 / 7
图 3：七巧板之面积切合对比
将上述不等式两边同时除以???2，可以得到：
?({?}) =
∑ ??
? 2
?=1
???2 ≤ 1
其中，?({?})描述行驶路线离散程度，路线约离散，其值越小。
Q：我明白了，而且我能推测“?({?})”的取值在 0 至 1 之间。
A：你说的没错，?({?})分子分母都是大于零的正数，因此比值也是正数。但如果你
仅仅满足于次，那是不够的。事实上，区间(?,?]太宽了，给了过宽的区间。下面这一部
分会用到关于不等式和函数极限的知识，我会给出严格的证明区间上下界。
首先，如果你嗅觉敏锐，你会意识到?({?})的表达式是柯西不等式（Cauchy–
Bunyakovsky–Schwarz inequality）的特例，这一点非常重要。
图 4：柯西不等式的二维形式（图片来源于百度百科）
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
p1
p2
p3
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
p1
p2
p3
p4
5 / 7
根据柯西不等式，不妨令?? = ??，?? = 1。于是有：
?∑ ??
2
?
?=1
≥ (∑ ??
?
?=1
)
2
= ???2
⇒
∑ ??
? 2
?=1
???2 ≥
1
?
因此，?({?})的下界为1
?
，不等号成立的条件为?1 = ?2 = ⋯ = ??，此时该车辆在任意地
点的行驶次数完全相等。图 3 中的右上（取值 1/2）、右下图（取值 1/4）均满足此情形。
另一方面，当?? ≥ 0，有
(∑ ??
?
?=1
)
2
= ∑ ∑ ??
??
?
?=1
?
?=1
= ∑ ??
2
?
?=1
+∑ ∑ ??
??
?
?=1,?≠?
?
?=1
≥ ∑ ??
2
?
?=1
下面，讨论?({?})的上界。当? = 1时，?({?})=1；当? > 1时，∑ ??
? 2
?=1 = ?1
2 + ∑ ??
? 2
?=2 ，
有如下不等式成立：
?1
2 + ∑ ??
2
?
?=2
≤ ?1
2 + (∑ ??
?
?=2
)
2
= ?1
2 + (??? − ?1
)
2
不等式右侧?1
2 + (??? − ?1
)
2是关于?1的二次函数，当?1 = ???⁄2时有极小值???2⁄2，
?1 = 1⁄???或(??? − 1)⁄???时取极大值 1
???2 + (1 −
1
???2
)。当且仅当? = 2时，等号
成立，该车辆仅在两个地点之间通勤。
综上所述，?({?})满足
{
?({?}) = 1, ? = 1
1
?
≤ ?({?}) ≤ ?1
2 + (??? − ?1
)
2
, ? > 1
因此，刻画行驶离散度的函数?({?})的取值在点 1 或[
1
?
,?1
2 + (??? − ?1
)
2
]，在区间
[0,
1
?
)和(?1
2 + (??? − ?1
)
2
, 1)没有取值。
Q：如果只统计车辆在高速公路上的行程呢，这会有什么区别吗？
A：想到这一点，很好。高速公路最大的特点是单向通行，每条行程的起点和终点是
不可能重合的。如果你想回到起点，你不得不离开高速公路，然后再次进入。
这里我们有一个潜在假设，即认为“进出高速出入口”判定为一次行程，即便你中
途没有停车，一旦离开而再次回到高速，都会判定为不同行程。
如此以来，集合{?}中的元素将受到约束，例如高速公路出入地点集合{?}中不可能
只有一个元素，至少应为 2 个；由于每条行程一定会涉及两个地点，因此{?}中任意地
点对应的途径次数，至多不会超过???⁄2，至少应为 1 次。
6 / 7
此时，?({?})满足
{
?({?}) = 1/2, ? = 2
1
?
≤ ?({?}) ≤ ??
2 + (??? − ??
)
2
,∀?, ? > 2
, s.t. 1 ≤ ?? ≤ ???⁄2
对于任意?均成立，只需要保障??
2 + (??? − ??
)
2取最小值???2⁄2仍成立即可，将不等
式进一步放缩得到：
{
?({?}) = 1/2, ? = 2
1
?
≤ ?({?}) < 1/2, ? > 2
, s.t. 1 ≤ ?? ≤ ???⁄2
因此，高速公路情景离散度的函数?({?})的取值在[
1
?
,
1
2
]。当所有地点途径次数相同时取
极小值1
?；当且仅当在两个固定高速路口往返行驶时，取极大值1
2。
如果结合七巧板，可以得到相同结论。如下图所示，无论如何切割正方形，最大面
积的子正方形边长都不会超过???⁄2，而其余正方形的面积都不会超过 ??。因此所有子
正方形之和不超过大正方形面积的一般，即?({?}) ≤ 1/2，如图 4。
图 4：对大正方切割的子正方边长都不会超过???⁄2（易证???必为偶数），子正方的
面积之和不会超过整体的一半。
更为严格的，当? > 2时，从图 5 中易知，当面积最大的正方形边长依次为???⁄2
和???⁄2 − (?-2)，剩余正方形取边长为 1 时，子正方形总面积之和最大，取值为
???2
2
−
(??? + 1 − ?)(?-2)，进一步有：
1 2 3 … SUM/2 … … … … SUM
1
2
3
…
SUM/2
…
…
…
…
SUM
max: pi
7 / 7
{
?({?}) = 1/2, ? = 2
1
?
≤ ?({?}) <
1
2
−
(??? + 1 − ?)(?-2)
???2
, ? > 2
, s.t. 1 ≤ ?? ≤ ???⁄2
图 5：如果停驻地点个数大于等于 3 时，将面积按照从大到小排序，面积最大正方形位
于上方，依次类推。当第一个子正方形边长为???⁄2，第二个边长为???⁄2 −
(?-2)，剩余边长为 1 时，面积求和最大。
1 2 3 … SUM/2 … … … … SUM
1
2
3
…
SUM/2
…
…
…
… …
SUM Length
=1
Length=SUM/2
Length=
SUM/2-(m-2)
