久久久国产一区二区_国产精品av电影_日韩精品中文字幕一区二区三区_精品一区二区三区免费毛片爱

機(jī)械社區(qū)

標(biāo)題: 用高等數(shù)學(xué)清掃馬路 [打印本頁(yè)]
作者: 曉昀    時(shí)間: 2020-9-6 17:41
標(biāo)題: 用高等數(shù)學(xué)清掃馬路
! Z* v1 u9 \7 t- A/ Z" v

; {; Y2 r  K- }1 W" x* y
(, 下載次數(shù): 66)
" R" [: M3 `6 e' a
$ Y" Z" y6 t9 z
      有人會(huì)說(shuō)，這還不簡(jiǎn)單，哪兒沒(méi)有跑過(guò)就去跑一遍不就行了嘛。

- g- n5 `# E6 Q% F, X0 Y. F
      這種方法的確能保證所有的道路都被打掃了，但是車子可能會(huì)在某幾段馬路上重復(fù)開，損失燃油和時(shí)間。
/ M! ~* t: f5 `+ [7 @3 B  c
     北美的一個(gè)大城市多倫多在好好用數(shù)學(xué)規(guī)劃之前，每年就白白多花了3百萬(wàn)美金的冤枉錢。/ D* \3 O4 ?, h. i

( r. g1 i! ^( y8 B; q
(, 下載次數(shù): 79)

& {/ G3 x2 ]3 N* l! a8 \
      是這樣的，掃馬路、灑水車、鏟雪車這類問(wèn)題在數(shù)學(xué)上屬于中國(guó)郵差問(wèn)題，中國(guó)郵差問(wèn)題本身早在20世紀(jì)70年代就有了靠譜的解法。

( V; C. d( s# T2 S
     事情還要從1962年說(shuō)起。當(dāng)時(shí)，毛主席鼓勵(lì)科學(xué)家們用科學(xué)解決人民日常生活中遇到的問(wèn)題。

' V& P$ B+ _: s1 |4 e: n; ~' c% c
     我國(guó)數(shù)學(xué)家管梅谷就想到了這樣一個(gè)問(wèn)題：一個(gè)郵差走遍每條街道去送信，最短路徑應(yīng)該是什么樣的？

7 `) t' G% p) r& G4 ~4 u0 }6 U
     后來(lái)，美國(guó)國(guó)家標(biāo)準(zhǔn)技術(shù)研究所的數(shù)學(xué)家 Alan J. Goldman 把這個(gè)問(wèn)題命名為“中國(guó)郵差問(wèn)題”。

& K% x3 h: d  T7 m8 |( i" o
(, 下載次數(shù): 78)
2 w# r* _: H- N) w( W
      到了1973年，加拿大滑鐵盧大學(xué)的數(shù)學(xué)家 Jack Edmonds 和 IBM 研究院的計(jì)算機(jī)科學(xué)家 Ellis L. Johnson 提出了一個(gè)至今無(wú)人超越的有效算法。他們的算法要 cue 到三百年前的一個(gè)人，那就是歐拉。

0 {3 D: d: W! f
      其實(shí)，歐拉在1735年就研究過(guò)一個(gè)和管梅谷類似的問(wèn)題——七橋問(wèn)題，并得到了一些重要的結(jié)論。

! ^* a8 m3 r( v
(, 下載次數(shù): 81)
七橋問(wèn)題 圖片來(lái)源：wikipedia
: H% o) s$ q5 E& A
       七橋問(wèn)題和我們小時(shí)候玩的一筆畫的益智問(wèn)題類似：在普魯士的柯尼斯堡有兩個(gè)小島，兩個(gè)小島和附近一共有7座橋連通。現(xiàn)在問(wèn)題來(lái)了，怎樣規(guī)劃路線才能恰好經(jīng)過(guò)每一座橋一次？
4 q6 `7 N% s) t# i
       第二年，歐拉發(fā)了一篇論文，證明七橋問(wèn)題不可解，原因是他給出了能解的一般條件，那就是每塊地都必須有偶數(shù)座橋，而七橋問(wèn)題不符合這種情況。
; j9 `0 P; m: r2 ]0 P0 y; G9 B. @
! p+ a8 F0 @( {- @3 V' T9 h- @
      后來(lái)，這類問(wèn)題在數(shù)學(xué)上發(fā)展成了圖論和拓?fù)鋵W(xué)。而因?yàn)闅W拉的開創(chuàng)性貢獻(xiàn)，能夠一筆畫的圖被叫做歐拉圖，一筆畫的路徑被叫做歐拉路徑。
: c" e- f& X" M6 L+ d5 S8 _
(, 下載次數(shù): 80)
七橋問(wèn)題等價(jià)于右邊這個(gè)圖形。歐拉證明，只有當(dāng)奇頂點(diǎn)的數(shù)量等于0或2時(shí)，才存在一筆畫。七橋問(wèn)題的奇頂點(diǎn)（藍(lán)點(diǎn)）的數(shù)量等于4，因此無(wú)法一筆畫。

$ z5 z  ^6 b8 c- @* E5 \
       歐拉還證明了一張圖能一筆畫的一般情況：奇頂點(diǎn)（也就是邊的數(shù)量是奇數(shù)的頂點(diǎn)）的數(shù)量等于0或2。

7 K4 {/ D  D1 _8 n/ |
       所以按照歐拉證明的定理，中文的“串”就可以一筆寫成，因?yàn)樗钠骓旤c(diǎn)只有最上面和最下面一共兩個(gè)。

4 R% O, a* j1 M. T
(, 下載次數(shù): 80)
串的奇頂點(diǎn)有2個(gè)（最上和最下），因此可以一筆畫。
% k# l1 {6 l' x# T' p2 Q: k: l
       下面這個(gè)德國(guó)兒童的傳統(tǒng)娛樂(lè)項(xiàng)目——Haus vom Nikolaus puzzle （圣尼古拉房屋）也可以一筆畫——
, H* V. H9 g/ o% k7 u; r
(, 下載次數(shù): 68)

2 I- b4 t5 ^& v" Q( w+ r
       順便說(shuō)一下，圣尼古拉房屋有44種解法。
9 n! c6 ]- f% e
(, 下載次數(shù): 69)
1 b* h# `2 h  u* {9 ~: Y
       把歐拉證明的結(jié)論推廣到中國(guó)郵差問(wèn)題的情況，最難搞定的是奇數(shù)分叉的道路，遇到三岔路口、五岔路口，走回頭路幾乎是必然。

3 F( M" f. @. F! d: B
(, 下載次數(shù): 68)

3 Z. Z) F& ?0 A
      所以 Edmonds 他們的算法是，把奇數(shù)路口拎出來(lái)單獨(dú)算，找到這些路口間的最短路徑；而偶數(shù)岔路之間必然存在只走一次的方法，最后把兩部分拼起來(lái)就可以了。

2 {  \$ k7 a1 Y- T, |4 A) j
(, 下載次數(shù): 77)
5 B: Z. k7 C4 [+ M& ^
       但是呢，實(shí)際生活中掃馬路、灑水和鏟雪要比這復(fù)雜得多。
# w) n1 M# y/ v5 Z6 a' N
       比如，高速公路的整潔對(duì)司機(jī)的生命財(cái)產(chǎn)安全更重要，所以要早點(diǎn)清掃完畢；一些路段是單行線，或者對(duì)大型車輛限行。此外，“郵差”也不只一個(gè)人，而且不能無(wú)限“肝”活，清潔車之間的交接班也要考慮在內(nèi)。
) T* f0 I. M6 E* L1 B
       因此在現(xiàn)實(shí)生活中，中國(guó)郵差問(wèn)題很難找到最優(yōu)策略，這也是為什么一開始 Edmonds 的算法沒(méi)有得到廣泛應(yīng)用。
6 M2 ~) a" K; Z  C8 X7 Y5 A
(, 下載次數(shù): 82)
       到了20世紀(jì)90年代，隨著計(jì)算機(jī)技術(shù)的進(jìn)步，一些數(shù)學(xué)家開始嘗試把中國(guó)郵差問(wèn)題應(yīng)用到日常生活中。比如，明尼蘇達(dá)大學(xué)的數(shù)學(xué)教授 Peh Ng 就曾用圖論的思想幫明州莫里斯市政府規(guī)劃冬季的鏟雪線路。
( y' ~  B& O0 t; R
       而從2001年開始，北美的一些大城市就開始用比較成熟的軟件（如 ArcGIS）來(lái)規(guī)劃鏟雪車的行車路徑。這些軟件一般會(huì)把一大塊城市交通網(wǎng)分割成一小塊一小塊的，然后分別再進(jìn)行計(jì)算。

/ _* p( Q( v. e( @2 }6 v5 ~
(, 下載次數(shù): 82)
6 [, H5 }1 X8 \/ L
        比如，多倫多在用圖論原理對(duì)鏟雪線路進(jìn)行規(guī)劃后，鏟雪費(fèi)用比之前減少了三分之一，每年節(jié)省了大約3百萬(wàn)美金（約合2千萬(wàn)人民幣）。
4 K; m, l+ o$ Z6 O9 f
       多倫多的市政道路交通的運(yùn)營(yíng)經(jīng)理 Hector Moreno 表示，在用ArcGIS之前，行車路線主要靠經(jīng)驗(yàn)和人工計(jì)算，現(xiàn)在就不需要這么麻煩了。
9 k$ s9 Q/ n3 `; A1 B
(, 下載次數(shù): 68)
波士頓市政府的應(yīng)用數(shù)學(xué)團(tuán)隊(duì) 圖片來(lái)源：boston.gov

. q. Q' s1 `+ I5 _
       2010年，波士頓市政府也組建了自己的數(shù)學(xué)團(tuán)隊(duì)——Mayor's Office of New Urban Mechanics，用數(shù)學(xué)和計(jì)算機(jī)來(lái)規(guī)劃鏟雪路線。

. J5 Y% {  ?! O$ V7 o+ F1 H
       像波士頓這樣的大城市用數(shù)學(xué)進(jìn)行規(guī)劃真的太有必要了。2015年，為了鏟雪，波士頓的鏟雪車一共開了47萬(wàn)千米，差不多可以繞地球12圈了。鏟雪的花費(fèi)也是驚人的，那年的暴雪讓波士頓一共掏出了3500萬(wàn)美金（約合2.3億人民幣）。

$ O  W  k0 Y! T1 }3 U
(, 下載次數(shù): 74)
2015年，波士頓的暴雪創(chuàng)下了記錄。圖片來(lái)源：newyorktimes
" x9 F. C& t* D7 y7 h, l7 l
       除了道路養(yǎng)護(hù)，中國(guó)郵差問(wèn)題的算法在很多領(lǐng)域還有應(yīng)用。比如在交互設(shè)計(jì)時(shí)，中國(guó)郵差問(wèn)題就被用于終端產(chǎn)品的可用性檢測(cè)。

5 n$ X7 B# P( L9 B& ~' U' [
舉個(gè)例子，一個(gè)手機(jī)被制造出來(lái)以后，手機(jī)制造商想要看看每個(gè)功能是不是和名稱相符。比如按下主鍵，點(diǎn)開“設(shè)置”，再點(diǎn)開“網(wǎng)絡(luò)”，是不是真的會(huì)出現(xiàn)網(wǎng)絡(luò)設(shè)定功能。

, E! d  w) |  T; ~) }5 N
(, 下載次數(shù): 81)

& T8 T( D: C. @# ?# s
       因?yàn)槭謾C(jī)的功能很復(fù)雜，不同功能之間形成的網(wǎng)絡(luò)要怎么樣才能有效地走個(gè)遍，這個(gè)問(wèn)題有時(shí)連制造商也搞不太明白。1996年諾基亞出的2110的菜單有88個(gè)項(xiàng)目，一共有273種操作。如果隨便按，可能一些菜單永遠(yuǎn)也不會(huì)得到檢測(cè)。

0 n5 U% U! w' ]( B
      但是利用中國(guó)郵差問(wèn)題的算法就能規(guī)劃測(cè)試路徑和計(jì)算步驟數(shù)量了：最少就只需要按594次鍵盤按鈕就可以把所有的菜單和功能都過(guò)一遍了。

% a5 G0 N. r- L+ P% ~6 W% W% R
(, 下載次數(shù): 76)
* Y5 {3 A& E- k2 N6 {) ?
      在檢查網(wǎng)頁(yè)鏈接有沒(méi)有“死角”的時(shí)候也可以用到中國(guó)郵差問(wèn)題的算法。

! l: r: v$ j8 `, G* _. W& m
      比如，富蘭克林故居的網(wǎng)站(benjaminfranklinhouse.org)有66個(gè)網(wǎng)頁(yè)，1191個(gè)超鏈接。如果網(wǎng)絡(luò)測(cè)試員沒(méi)有頭腦一頓亂點(diǎn)，不但要做無(wú)用功，有些網(wǎng)頁(yè)和鏈接可能還點(diǎn)不到。但是利用中國(guó)郵差問(wèn)題的算法，測(cè)試員知道只要點(diǎn)2248次就可以測(cè)試完所有的網(wǎng)頁(yè)和超鏈接了。

/ {  {' f- @2 R: N+ Q1 _
(, 下載次數(shù): 77)
位于英國(guó)倫敦的富蘭克林故居
# X# |1 W# x7 C: t+ |9 X; |+ J
       歐拉路徑判定挺好掌握的呢：口中串串，乃米田共。
* R! u/ Q7 R8 L0 [

  ^1 O  M3 ]$ z& z  G# R, j0 o% u
( M2 P$ {/ @5 D6 G( Q

& {' i# s  o$ C: R# G9 [2 i
作者: 大白小白    時(shí)間: 2020-9-6 18:00
口中串串，乃米田共？？
作者: okmeiyou    時(shí)間: 2020-9-6 18:05
學(xué)習(xí)了。
作者: 譬如朝露    時(shí)間: 2020-9-6 18:36
最后一句，是本文之主旨所在
作者: 曉昀    時(shí)間: 2020-9-6 20:40
譬如朝露 發(fā)表于 2020-9-6 18:361 N# ?, [% s8 W- g  E% |7 J+ I& U" ?
最后一句，是本文之主旨所在

- ?( g$ L/ q, E+ i超快速抓住重點(diǎn)。這是很有意思的一個(gè)問(wèn)題。
4 F6 K# b4 @5 ?% N# @
作者: kayex    時(shí)間: 2020-9-7 08:58
不能這樣的，一定要按領(lǐng)導(dǎo)規(guī)定的路線開才對(duì)，領(lǐng)導(dǎo)高興最重要！！！
作者: 魍者歸來(lái)    時(shí)間: 2020-9-7 13:46
七橋這個(gè)是奧數(shù)的典型問(wèn)題之一，噩夢(mèng)復(fù)現(xiàn)。
: X% O) q" P. o& ?% ^+ ?( s' x% x9 ?( P
說(shuō)個(gè)題外話，以前還經(jīng)常有公車私用，拉警笛闖紅燈的，現(xiàn)在不少城市都開始聯(lián)網(wǎng)了，不是出任務(wù)的情況拉警笛會(huì)被處罰，確實(shí)規(guī)范了不少。
作者: 遠(yuǎn)祥    時(shí)間: 2020-9-7 19:50
抓重點(diǎn)，提關(guān)鍵，也可以使用思維導(dǎo)圖。
作者: wlj0202    時(shí)間: 2020-9-21 14:05
學(xué)習(xí)一下啊了



歡迎光臨 機(jī)械社區(qū) (http://www.ytsybjq.com/) Powered by Discuz! X3.5