1 / 7
車輛行駛路徑復(fù)雜度：從七巧板到柯西不等式
作者：Xiang Shan
近日，在與某些外部主流機(jī)構(gòu)溝通交流時，發(fā)現(xiàn)計算機(jī)動車輛“行駛路徑離散度”
的主流算法（離散度：計算行駛路徑復(fù)雜度的一種方法）存在度量域過寬的錯誤。在指
出其缺陷后，以嚴(yán)謹(jǐn)推導(dǎo)建議其更正。今日形成此文，以對話方式呈現(xiàn)。
Q：如何度量某輛汽車在地圖上行駛路徑越復(fù)雜度？
A：首先，我們可以在地圖上繪制過去一段時間內(nèi)，該車輛每次行程的行駛路徑圖。
為了讓繪制簡化，不妨忽略每次行程途徑的具體街道，而只是用“直線”連接行程的起
點與終點，即“向量”表示。
那些日常行駛固定通勤路線的上班一族，自然比營運(yùn)車輛路線更為固定，在視覺上
呈現(xiàn)路徑圖更“簡潔”。如下圖：車輛 A 路線簡潔；車輛 B 路線復(fù)雜。
圖 1：車輛行駛路徑案例
2 / 7
Q：你這種將行駛路線簡化為“向量”的表示方法，讓我聯(lián)想起“哥尼斯堡七
橋”問題。如果借助圖論的思考方式，問題可以進(jìn)一步簡化嗎？
圖 2：哥尼斯堡七橋問題
A：啊哈！你說的沒錯，歐拉就是將該問題抽象為一筆畫問題，開創(chuàng)了圖論。我們也
可以效仿，將每次行程的起終點抽象為“點”，用地點名稱來描述這些點；對于每次行程
“向量”，進(jìn)一步簡化為“線”，忽略其方向性，甚至我們連“線”的長度都可以忽略。
這些簡化，將使得分析行駛路徑復(fù)雜性問題變得簡潔。此時，我們可以將問題重新
表述為如下集合的映射：
Step1：將某車輛觀測期內(nèi)，第?次行程的起終點記為?????? = [??
, ??
]。于是，將觀
測期內(nèi)所有行程合并成數(shù)組?，則集合{?} = {?1, ?2, ?3, ? , ??}表示在觀測期內(nèi)車輛共起
終過?個地點，用??表示地點?。例如，某輛車觀測期內(nèi)有 3 次行程，分別為[國貿(mào), 亮
馬橋], [亮馬橋, 天安門], [天安門, 天壇]，則{?} = {國貿(mào),亮馬橋,天安門,天壇}。
Step2：計量經(jīng)過地點次數(shù){?}，令{?} = ?({?}) = {?1,?2,?3, ? ,??}，其中??表示經(jīng)過
地點??的次數(shù)。例如{?} = {國貿(mào),亮馬橋,天安門,天壇}對應(yīng){?} = {1,1, 2, 1}。
事實上，即便相鄰兩次行程是不連續(xù)的（如，信息記錄缺失），即上一個行程的終點
不是下一個行程的起點，也不會影響上述記錄方式。容易知道，集合{?}中元素個數(shù)?即
可以是奇數(shù)、也可以是偶數(shù)，而集合{?}中所有元素的值求和（記為???）一定是偶數(shù)。
這是因為每個行程一定有起、終點，每完成一次行程會使得???增加 2。
3 / 7
Q：有趣，通過集合表述的方式，現(xiàn)在確實把問題簡化了！下一步，該如何描
述路徑復(fù)雜度呢？
A：直覺上，固定路徑通勤的車輛，途徑地點會比較集中，而路徑復(fù)雜的車輛途徑地
點會十分離散，如圖 1 所示。因此，我們只需要能在數(shù)學(xué)上描述途徑地點的離散程度，
就能在某種程度上近似刻畫路徑復(fù)雜度。例如，你可以想象用途徑地點次數(shù)的重數(shù)與均
值的差異來描述，兩者越是接近，行駛路徑可能越離散；也可以使用熵理論（信息熵）
來度量離散度等。
最近在陪家里小朋友玩七巧板，這里想從幾何為出發(fā)點，討論一種刻畫途徑地點離
散程度的方法。
不妨令{?}中所有元素的值求和??? = 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：你說的沒錯，?({?})分子分母都是大于零的正數(shù)，因此比值也是正數(shù)。但如果你
僅僅滿足于次，那是不夠的。事實上，區(qū)間(?,?]太寬了，給了過寬的區(qū)間。下面這一部
分會用到關(guān)于不等式和函數(shù)極限的知識，我會給出嚴(yán)格的證明區(qū)間上下界。
首先，如果你嗅覺敏銳，你會意識到?({?})的表達(dá)式是柯西不等式（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
根據(jù)柯西不等式，不妨令?? = ??，?? = 1。于是有：
?∑ ??
2
?
?=1
≥ (∑ ??
?
?=1
)
2
= ???2
?
∑ ??
? 2
?=1
???2 ≥
1
?
因此，?({?})的下界為1
?
，不等號成立的條件為?1 = ?2 = ? = ??，此時該車輛在任意地
點的行駛次數(shù)完全相等。圖 3 中的右上（取值 1/2）、右下圖（取值 1/4）均滿足此情形。
另一方面，當(dāng)?? ≥ 0，有
(∑ ??
?
?=1
)
2
= ∑ ∑ ??
??
?
?=1
?
?=1
= ∑ ??
2
?
?=1
+∑ ∑ ??
??
?
?=1,?≠?
?
?=1
≥ ∑ ??
2
?
?=1
下面，討論?({?})的上界。當(dāng)? = 1時，?({?})=1；當(dāng)? > 1時，∑ ??
? 2
?=1 = ?1
2 + ∑ ??
? 2
?=2 ，
有如下不等式成立：
?1
2 + ∑ ??
2
?
?=2
≤ ?1
2 + (∑ ??
?
?=2
)
2
= ?1
2 + (??? ? ?1
)
2
不等式右側(cè)?1
2 + (??? ? ?1
)
2是關(guān)于?1的二次函數(shù)，當(dāng)?1 = ????2時有極小值???2?2，
?1 = 1????或(??? ? 1)????時取極大值 1
???2 + (1 ?
1
???2
)。當(dāng)且僅當(dāng)? = 2時，等號
成立，該車輛僅在兩個地點之間通勤。
綜上所述，?({?})滿足
{
?({?}) = 1, ? = 1
1
?
≤ ?({?}) ≤ ?1
2 + (??? ? ?1
)
2
, ? > 1
因此，刻畫行駛離散度的函數(shù)?({?})的取值在點 1 或[
1
?
,?1
2 + (??? ? ?1
)
2
]，在區(qū)間
[0,
1
?
)和(?1
2 + (??? ? ?1
)
2
, 1)沒有取值。
Q：如果只統(tǒng)計車輛在高速公路上的行程呢，這會有什么區(qū)別嗎？
A：想到這一點，很好。高速公路最大的特點是單向通行，每條行程的起點和終點是
不可能重合的。如果你想回到起點，你不得不離開高速公路，然后再次進(jìn)入。
這里我們有一個潛在假設(shè)，即認(rèn)為“進(jìn)出高速出入口”判定為一次行程，即便你中
途沒有停車，一旦離開而再次回到高速，都會判定為不同行程。
如此以來，集合{?}中的元素將受到約束，例如高速公路出入地點集合{?}中不可能
只有一個元素，至少應(yīng)為 2 個；由于每條行程一定會涉及兩個地點，因此{(lán)?}中任意地
點對應(yīng)的途徑次數(shù)，至多不會超過????2，至少應(yīng)為 1 次。
6 / 7
此時，?({?})滿足
{
?({?}) = 1/2, ? = 2
1
?
≤ ?({?}) ≤ ??
2 + (??? ? ??
)
2
,??, ? > 2
, s.t. 1 ≤ ?? ≤ ????2
對于任意?均成立，只需要保障??
2 + (??? ? ??
)
2取最小值???2?2仍成立即可，將不等
式進(jìn)一步放縮得到：
{
?({?}) = 1/2, ? = 2
1
?
≤ ?({?}) < 1/2, ? > 2
, s.t. 1 ≤ ?? ≤ ????2
因此，高速公路情景離散度的函數(shù)?({?})的取值在[
1
?
,
1
2
]。當(dāng)所有地點途徑次數(shù)相同時取
極小值1
?；當(dāng)且僅當(dāng)在兩個固定高速路口往返行駛時，取極大值1
2。
如果結(jié)合七巧板，可以得到相同結(jié)論。如下圖所示，無論如何切割正方形，最大面
積的子正方形邊長都不會超過????2，而其余正方形的面積都不會超過 ??。因此所有子
正方形之和不超過大正方形面積的一般，即?({?}) ≤ 1/2，如圖 4。
圖 4：對大正方切割的子正方邊長都不會超過????2（易證???必為偶數(shù)），子正方的
面積之和不會超過整體的一半。
更為嚴(yán)格的，當(dāng)? > 2時，從圖 5 中易知，當(dāng)面積最大的正方形邊長依次為????2
和????2 ? (?-2)，剩余正方形取邊長為 1 時，子正方形總面積之和最大，取值為
???2
2
?
(??? + 1 ? ?)(?-2)，進(jìn)一步有：
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：如果停駐地點個數(shù)大于等于 3 時，將面積按照從大到小排序，面積最大正方形位
于上方，依次類推。當(dāng)?shù)谝粋€子正方形邊長為????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)
