1 / 7

車輛行駛路徑復(fù)雜度：從七巧板到柯西不等式

作者：Xiang Shan

近日，在與某些外部主流機(jī)構(gòu)溝通交流時(shí)，發(fā)現(xiàn)計(jì)算機(jī)動(dòng)車輛“行駛路徑離散度”

的主流算法（離散度：計(jì)算行駛路徑復(fù)雜度的一種方法）存在度量域過(guò)寬的錯(cuò)誤。在指

出其缺陷后，以嚴(yán)謹(jǐn)推導(dǎo)建議其更正。今日形成此文，以對(duì)話方式呈現(xiàn)。

Q：如何度量某輛汽車在地圖上行駛路徑越復(fù)雜度？

A：首先，我們可以在地圖上繪制過(guò)去一段時(shí)間內(nèi)，該車輛每次行程的行駛路徑圖。

為了讓繪制簡(jiǎn)化，不妨忽略每次行程途徑的具體街道，而只是用“直線”連接行程的起

點(diǎn)與終點(diǎn)，即“向量”表示。

那些日常行駛固定通勤路線的上班一族，自然比營(yíng)運(yùn)車輛路線更為固定，在視覺(jué)上

呈現(xiàn)路徑圖更“簡(jiǎn)潔”。如下圖：車輛 A 路線簡(jiǎn)潔；車輛 B 路線復(fù)雜。

圖 1：車輛行駛路徑案例

2 / 7

Q：你這種將行駛路線簡(jiǎn)化為“向量”的表示方法，讓我聯(lián)想起“哥尼斯堡七

橋”問(wèn)題。如果借助圖論的思考方式，問(wèn)題可以進(jìn)一步簡(jiǎn)化嗎？

圖 2：哥尼斯堡七橋問(wèn)題

A：啊哈！你說(shuō)的沒(méi)錯(cuò)，歐拉就是將該問(wèn)題抽象為一筆畫問(wèn)題，開(kāi)創(chuàng)了圖論。我們也

可以效仿，將每次行程的起終點(diǎn)抽象為“點(diǎn)”，用地點(diǎn)名稱來(lái)描述這些點(diǎn)；對(duì)于每次行程

“向量”，進(jìn)一步簡(jiǎn)化為“線”，忽略其方向性，甚至我們連“線”的長(zhǎng)度都可以忽略。

這些簡(jiǎn)化，將使得分析行駛路徑復(fù)雜性問(wèn)題變得簡(jiǎn)潔。此時(shí)，我們可以將問(wèn)題重新

表述為如下集合的映射：

Step1：將某車輛觀測(cè)期內(nèi)，第?次行程的起終點(diǎn)記為?????? = [??

, ??

]。于是，將觀

測(cè)期內(nèi)所有行程合并成數(shù)組?，則集合{?} = {?1, ?2, ?3, ? , ??}表示在觀測(cè)期內(nèi)車輛共起

終過(guò)?個(gè)地點(diǎn)，用??表示地點(diǎn)?。例如，某輛車觀測(cè)期內(nèi)有 3 次行程，分別為[國(guó)貿(mào), 亮

馬橋], [亮馬橋, 天安門], [天安門, 天壇]，則{?} = {國(guó)貿(mào),亮馬橋,天安門,天壇}。

Step2：計(jì)量經(jīng)過(guò)地點(diǎn)次數(shù){?}，令{?} = ?({?}) = {?1,?2,?3, ? ,??}，其中??表示經(jīng)過(guò)

地點(diǎn)??的次數(shù)。例如{?} = {國(guó)貿(mào),亮馬橋,天安門,天壇}對(duì)應(yīng){?} = {1,1, 2, 1}。

事實(shí)上，即便相鄰兩次行程是不連續(xù)的（如，信息記錄缺失），即上一個(gè)行程的終點(diǎn)

不是下一個(gè)行程的起點(diǎn)，也不會(huì)影響上述記錄方式。容易知道，集合{?}中元素個(gè)數(shù)?即

可以是奇數(shù)、也可以是偶數(shù)，而集合{?}中所有元素的值求和（記為???）一定是偶數(shù)。

這是因?yàn)槊總€(gè)行程一定有起、終點(diǎn)，每完成一次行程會(huì)使得???增加 2。

3 / 7

Q：有趣，通過(guò)集合表述的方式，現(xiàn)在確實(shí)把問(wèn)題簡(jiǎn)化了！下一步，該如何描

述路徑復(fù)雜度呢？

A：直覺(jué)上，固定路徑通勤的車輛，途徑地點(diǎn)會(huì)比較集中，而路徑復(fù)雜的車輛途徑地

點(diǎn)會(huì)十分離散，如圖 1 所示。因此，我們只需要能在數(shù)學(xué)上描述途徑地點(diǎn)的離散程度，

就能在某種程度上近似刻畫路徑復(fù)雜度。例如，你可以想象用途徑地點(diǎn)次數(shù)的重?cái)?shù)與均

值的差異來(lái)描述，兩者越是接近，行駛路徑可能越離散；也可以使用熵理論（信息熵）

來(lái)度量離散度等。

最近在陪家里小朋友玩七巧板，這里想從幾何為出發(fā)點(diǎn)，討論一種刻畫途徑地點(diǎn)離

散程度的方法。

不妨令{?}中所有元素的值求和??? = 20，用邊長(zhǎng) 20 圍成正立方體，表示起終點(diǎn)總

是重合，如圖 3 左上圖示，其面積記為???2

；若該車輛只途徑{?1, ?2

}，則有{?1,?2

} =

{10, 10}，用邊長(zhǎng) 10 的正方形分別表示?1和?2，面積分別為?1

2和?2

2，如圖 3 右上圖示；

以此類推，分別繪制途徑{?1, ?2, ?3

}和{?1, ?2, ?3, ?4

}情形。從圖 3 中看出，隨著途徑地點(diǎn)

的增加，途徑點(diǎn)的正方形面積之和逐漸減小，滿足如下公式：

???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：七巧板之面積切合對(duì)比

將上述不等式兩邊同時(shí)除以???2，可以得到：

?({?}) =

∑ ??

? 2

?=1

???2 ≤ 1

其中，?({?})描述行駛路線離散程度，路線約離散，其值越小。

Q：我明白了，而且我能推測(cè)“?({?})”的取值在 0 至 1 之間。

A：你說(shuō)的沒(méi)錯(cuò)，?({?})分子分母都是大于零的正數(shù)，因此比值也是正數(shù)。但如果你

僅僅滿足于次，那是不夠的。事實(shí)上，區(qū)間(?,?]太寬了，給了過(guò)寬的區(qū)間。下面這一部

分會(huì)用到關(guān)于不等式和函數(shù)極限的知識(shí)，我會(huì)給出嚴(yán)格的證明區(qū)間上下界。

首先，如果你嗅覺(jué)敏銳，你會(huì)意識(shí)到?({?})的表達(dá)式是柯西不等式（Cauchy–

Bunyakovsky–Schwarz inequality）的特例，這一點(diǎn)非常重要。

圖 4：柯西不等式的二維形式（圖片來(lái)源于百度百科）

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

?

，不等號(hào)成立的條件為?1 = ?2 = ? = ??，此時(shí)該車輛在任意地

點(diǎn)的行駛次數(shù)完全相等。圖 3 中的右上（取值 1/2）、右下圖（取值 1/4）均滿足此情形。

另一方面，當(dāng)?? ≥ 0，有

(∑ ??

?

?=1

)

2

= ∑ ∑ ??

??

?

?=1

?

?=1

= ∑ ??

2

?

?=1

+∑ ∑ ??

??

?

?=1,?≠?

?

?=1

≥ ∑ ??

2

?

?=1

下面，討論?({?})的上界。當(dāng)? = 1時(shí)，?({?})=1；當(dāng)? > 1時(shí)，∑ ??

? 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時(shí)有極小值???2?2，

?1 = 1????或(??? ? 1)????時(shí)取極大值 1

???2 + (1 ?

1

???2

)。當(dāng)且僅當(dāng)? = 2時(shí)，等號(hào)

成立，該車輛僅在兩個(gè)地點(diǎn)之間通勤。

綜上所述，?({?})滿足

{

?({?}) = 1, ? = 1

1

?

≤ ?({?}) ≤ ?1

2 + (??? ? ?1

)

2

, ? > 1

因此，刻畫行駛離散度的函數(shù)?({?})的取值在點(diǎn) 1 或[

1

?

,?1

2 + (??? ? ?1

)

2

]，在區(qū)間

[0,

1

?

)和(?1

2 + (??? ? ?1

)

2

, 1)沒(méi)有取值。

Q：如果只統(tǒng)計(jì)車輛在高速公路上的行程呢，這會(huì)有什么區(qū)別嗎？

A：想到這一點(diǎn)，很好。高速公路最大的特點(diǎn)是單向通行，每條行程的起點(diǎn)和終點(diǎn)是

不可能重合的。如果你想回到起點(diǎn)，你不得不離開(kāi)高速公路，然后再次進(jìn)入。

這里我們有一個(gè)潛在假設(shè)，即認(rèn)為“進(jìn)出高速出入口”判定為一次行程，即便你中

途沒(méi)有停車，一旦離開(kāi)而再次回到高速，都會(huì)判定為不同行程。

如此以來(lái)，集合{?}中的元素將受到約束，例如高速公路出入地點(diǎn)集合{?}中不可能

只有一個(gè)元素，至少應(yīng)為 2 個(gè)；由于每條行程一定會(huì)涉及兩個(gè)地點(diǎn)，因此{(lán)?}中任意地

點(diǎn)對(duì)應(yīng)的途徑次數(shù)，至多不會(huì)超過(guò)????2，至少應(yīng)為 1 次。

6 / 7

此時(shí)，?({?})滿足

{

?({?}) = 1/2, ? = 2

1

?

≤ ?({?}) ≤ ??

2 + (??? ? ??

)

2

,??, ? > 2

, s.t. 1 ≤ ?? ≤ ????2

對(duì)于任意?均成立，只需要保障??

2 + (??? ? ??

)

2取最小值???2?2仍成立即可，將不等

式進(jìn)一步放縮得到：

{

?({?}) = 1/2, ? = 2

1

?

≤ ?({?}) < 1/2, ? > 2

, s.t. 1 ≤ ?? ≤ ????2

因此，高速公路情景離散度的函數(shù)?({?})的取值在[

1

?

,

1

2

]。當(dāng)所有地點(diǎn)途徑次數(shù)相同時(shí)取

極小值1

?；當(dāng)且僅當(dāng)在兩個(gè)固定高速路口往返行駛時(shí)，取極大值1

2。

如果結(jié)合七巧板，可以得到相同結(jié)論。如下圖所示，無(wú)論如何切割正方形，最大面

積的子正方形邊長(zhǎng)都不會(huì)超過(guò)????2，而其余正方形的面積都不會(huì)超過(guò) ??。因此所有子

正方形之和不超過(guò)大正方形面積的一般，即?({?}) ≤ 1/2，如圖 4。

圖 4：對(duì)大正方切割的子正方邊長(zhǎng)都不會(huì)超過(guò)????2（易證???必為偶數(shù)），子正方的

面積之和不會(huì)超過(guò)整體的一半。

更為嚴(yán)格的，當(dāng)? > 2時(shí)，從圖 5 中易知，當(dāng)面積最大的正方形邊長(zhǎng)依次為????2

和????2 ? (?-2)，剩余正方形取邊長(zhǎng)為 1 時(shí)，子正方形總面積之和最大，取值為

???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：如果停駐地點(diǎn)個(gè)數(shù)大于等于 3 時(shí)，將面積按照從大到小排序，面積最大正方形位

于上方，依次類推。當(dāng)?shù)谝粋€(gè)子正方形邊長(zhǎng)為????2，第二個(gè)邊長(zhǎng)為????2 ?

(?-2)，剩余邊長(zhǎng)為 1 時(shí)，面積求和最大。

1 2 3 … SUM/2 … … … … SUM

1

2

3

…

SUM/2

…

…

…

… …

SUM Length

=1

Length=SUM/2

Length=

SUM/2-(m-2)