看板 Gossiping作者 DavidGuo (大衛郭)標題 Re: [新聞] 超狂數學教授活用演算法 高鐵分段買票竟時間 Tue Aug 15 18:38:00 2017
大家好,
我是這篇文章的作者,今天我的Line跟FB都費這則新聞洗板了…
身為鄉民這麼久,第一次在八卦版發言,
Unimath是陳宏賓教授發起的網路期刊,旨在刊登一些科普文章,
告訴大眾數學、科學在生活中處處都是,
而且學校學的數學,常常都能應用到生活上。
期刊中有不少教授寫了很多不錯的文章,有興趣的人可以看看。
回到主題,高鐵拆票是去年寫的文章,蘋果記者應該是最近看到,所以想寫篇專欄吧!
我目前在歐洲,昨天才跟蘋果的記者通電話,沒想到今天就刊出來了。
拆票有可能變便宜,我想很多人很早就知道了,
如鄉民講的,只要利用加法,還有比較大小,就可以知道了,
沒錯,會這樣想的話,表示已經可以把數學用到生活中了。
但更進一步想,
1.有時拆票又會變貴,到底為什麼?是不是高鐵的Bug?
2.又怎麼拆會最便宜?
不管答不答的出來,會這樣想的人,就是有著數學思維,Unimath的目的就達到了。
那本篇文章重點就是幫大家回答這兩個問題:
原文:
https://goo.gl/yQi9GE
1. 因為「誤差是會累加的」,高鐵票的計算方式是四捨五入到十元,有誤差,所以分越多段的誤差就會越大。
2. 但怎麼拆才會「最佳」,這就要靠電腦的幫忙了。(演算法用在哪?後面會講)
而記者把重點放錯了,都著重在省20元,去售票機買不會影響別人,之類的。
而且下的標題還很聳動!
(這當然不能怪記者,因為不聳動的標題,沒人要點進去看!但至少重點要放對啊…)
大致上是這樣!其實還蠻高興大家對這個主題有興趣的,
若有什麼好的科普主題或文章,歡迎投稿Unimath,跟大家一起分享。
- 師大數學系 郭君逸
下面是一些比較boring的部份,順便回答一些鄉民的問題,沒興趣的話可以直接跳過!
1. 演算法用在哪?不是只要加法就可以了嗎?
會這樣問的人,應該是沒碰過程式。
知道怎麼拆票的話,當然是直接把每一段票價加起來即可。只用到加法。
但問題就是不知道怎麼拆,有時拆了還會變貴。
一個簡單的想法就是,A到F中間有B,C,D,E站的話,每個站要分不分,總共2^4種切法都去試,
這樣就是一種演算法,但這樣的爆力法,效率很差(指數時間),
當中間的站點一多(例如算台鐵的分票),電腦也算不完。
那要怎麼省時間呢?我觀察到了中間有很多重複計算的部份,例如:
計算A到F站的話,在試切C點時,也會把AC與CF的最佳解都算過了,後來就不用再重複算。
所以我就採取空間換取時間的方法(Dynamic Programming)把算過的存起來,就不用再重算,
這樣的演算法就會快很多,即時算台鐵的所有站的分票,也是按個Enter馬上就算完了。
整個演算法雖然是我自己想的,後來還是查了一下書,
發現在演算法書中,最短路徑一章就有很多類似的東西,
然後我的演算法跟Dijkstra無迴圈的版本很像。
(其實還是有點不同,只是原理相同,
有興趣的同學可以自己寫程式列出所有站點之間的分票方式,比較能體會其奧妙。程式其實很短。)
2. 誤差疊加,很重要,求學時老師每次講,台下的我聽了都沒感覺,
明明多項式計算就代進去就好,為什麼還要改成巢狀計算;
矩陣就直接乘就好,為什麼還要對角化、Jordan Form……
然後就會在台下說,學這個到底要幹嘛,多此一舉,
後來等到自己遇到麻煩了,才知道自己當時的無知。
3. 時間成本很重要,誰會省這20元。
這當然是這樣,現在比較忙,時間都不夠用,我自己每次坐高鐵都坐直達的,誰想每站在那裡換位置!
省錢只是文章的手段,讓讀者願意點進來看,但重點不在此,不要再被記者拉著走了。
4. 數學教授整天算一些沒用的東西。
其實有沒有用每個人都不同,
否則籃球員為什麼要一直把球丟到籃框裡?
畫家為何要畫畫?不就照起來,再用一些濾鏡就好了?
這都是他們的工作、成果、興趣。
自然會有欣賞的人,自然也都有它的價值在。
5. 只要會加減乘除就可以活的好好的,為什麼要學這麼多?
這老生常談了。這就讓大家幫忙回答吧!
連加減都不會,也是可以活的好好的。
上了幾次新聞後,發現,其實水果算是新聞媒體裡還不錯的,他們會主動去採訪、訪問、找新聞,
然後很多媒體都是看到水果發布的新聞後,自己再改寫後再發布。
之前辦魔術方塊比賽,也沒發布新聞稿,水果記者前一天就會來訪問,比賽當天新聞就會出來,
其他家的記者看到新聞才來採訪,比賽都快比完了…
至於新聞內容有時會斷章取意,或是技術方面有寫錯,這是人人皆知的,
因為大家都是站在自己熟悉的專業在看新聞,但記者卻是要寫所有領域的東西,
錯誤是難免。(當然有些離普的,都被網友整理出來。)
不過,在大家關注的主題上,
有瑕疵的新聞,反而點擊率會更高,這是無庸置疑的。
--
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 83.216.94.104
※ 文章代碼(AID): #1PaiyBlZ (Gossiping)
※ 文章網址: https://www.ptt.cc/bbs/Gossiping/M.1502793483.A.BE3.html
※ 同主題文章:
Re: [新聞] 超狂數學教授活用演算法 高鐵分段買票竟
08-15 18:38 DavidGuo.
推 ulosy: 可惜你現在po只會被洗掉4F 08/15 18:39
噓 kenro: 無聊5F 08/15 18:39
推 klyee: 專業 可是沒空6F 08/15 18:39
推 Namukab: 我頭好痛 停電你在算數學 = =8F 08/15 18:39
推 ipad9: 幫你推推 但你po錯時間了10F 08/15 18:40
推 o11i: 沒空11F 08/15 18:40
推 aaazzza: 怎樣從台北到高雄最省錢?16F 08/15 18:44
推 hioer: 推老師!魔術方塊台灣第一人!17F 08/15 18:44
推 CWNS: 幫推一下18F 08/15 18:44
推 faloca: 難得好文..19F 08/15 18:44
推 m9o2o: 推25F 08/15 18:46
推 eWriter: 這時候發認真文不會覺得很幹嗎?28F 08/15 18:47
推 icps: 推 噓記者39F 08/15 18:51
推 imvh: ㄜ,這位教授好像是當年讀大學的助教41F 08/15 18:53
推 papac: 推!43F 08/15 18:55
推 miao145: 推你的想法 心胸好寬大47F 08/15 18:57
推 CSMUck: 洪seafood 嘗試切他c路58F 08/15 19:09
推 fqstory: 可以幫算一下台電會賠償多少錢嗎59F 08/15 19:11
推 a41503: 數學系給推61F 08/15 19:14
推 sleep123: 郭大發錯時間惹,台灣大停電63F 08/15 19:15
推 JameC: 難得在八卦版看到熟悉的東西,推67F 08/15 19:19
推 h73o1012: 喔喔下次講講如何用你那方法避免停電吧68F 08/15 19:23
推 PPK33: 幫推,有幾個錯字欸72F 08/15 19:25
推 l75cm: 會想到用數學解決生活問題就很屌73F 08/15 19:27
推 jainyoyo: 停電很熱...演算法沒心情看74F 08/15 19:30
推 Seabook: 推! 演算法的日常生活應用!92F 08/15 19:50
推 WK7er: 了解!推~~~99F 08/15 20:09
→ stock0907 …
噓 stock0907: 你知道你在創造華(ㄠˋ)客嗎 @@!?103F 08/15 20:14
推 oidkk: 推107F 08/15 20:23
推 AAPL: 推110F 08/15 20:24
推 toyeee: 推 但是會被洗掉111F 08/15 20:27
→ WWIII: 里組才是台灣社會的棟樑啊116F 08/15 20:40
推 adifdtd: 推 ftp,魔術方塊,數學都受到教授無私的分享 ^^117F 08/15 20:42
推 coolda: 數學能實用120F 08/15 20:50
推 syaman: 謝謝你帶我進入魔術方塊的世界121F 08/15 20:54
推 akata: 推124F 08/15 21:05
推 lv256: 發錯時間啦125F 08/15 21:05
推 SHIU0315: 推推
可惜發的時間不對 再推個129F 08/15 21:14
→ gosee: 快出來見神阿 學長好!!!!132F 08/15 21:21
推 mn228426: 基本的optimization problem133F 08/15 21:22
推 rax1010: 一個不同的思考方式,推140F 08/15 21:48
推 Bijala: 五樓在噓三小?145F 08/15 21:53
--