續前回,從兩年前的暑假(2006/07)開始,我的研究方向轉為交通相關的 data mining / data management。想想,我覺得解決塞車問題似乎最有趣也最實用,老師也對這很有興趣,之前有專題生做過簡化版問題,於是就朝此方向前進。
CS 領域內,解決塞車的 paper 到沒很多,不過在 Operation Research 和一些不清楚分類的領域裡,有不少相關作品。塞車相關的研究滿有趣的,像有一篇討論塞車有多糟,或從另一角度來看,我們能解決塞車到什麼程度。印象中這篇 paper 估計,最糟的情況下,無管制的行車時間會是有管制的兩倍慢。另外也有看到其它領域如何解決塞車,像倫敦用塞車稅(congestion road tax)的作法很有意思。我個人是認為經濟學(?)的作法比較實際,以價治量是合理且有效的作法。不過反正問題還沒徹底解決,也可以想想自己的做法。
理想的作法是大家都聽政府或某有公信力的單位指示開車,假設 server (central or distributed) 算得夠快,理論上塞車量會降到最低。於是我將問題切成如下三個部份,準備各個擊破:
1. 若我們有部份車子的車速和位置,如何將這些資料轉為表示即時車速的 graph?
2. 若有表示即時車速的 graph,當我們告知駕駛人如何前進時,如何即時更新 graph,以避免大家走同一條,造成一段時間後的新塞車點?
3. 若有表示即時車速的 graph,也知道如何依駕駛人選的路徑來更新它,要如何在極短時間內算出大量不同需求的最短路徑?
當一切規劃差不多後,我發現這問題很難,三個月顯然作不完,但這題目還沒有趣到讓我想和它奮鬥兩年,於是又找老師商量,可不可以換題目啊...。幸好開明的老師又讓我換方向,但要求我帶新的專題生接手做下去,這是個有趣的插曲,待日後分享心得。
隨著我再度更改研究方向,第一個暑假也差不多結束了,即將邁入正式的碩一。這個暑假到沒做太多研究,被一些「外務」耗掉時間,例如:
- 花了整整一週寫 Wow! Dice War!!
- 看完十季的 Friends。一開始還有一邊切換無字幕、英文字幕、中 + 英字幕,後來乾脆都用中文字幕了。
- 摸索 Web 2.0 相關東西,像 Blog、Wiki、Online Bookmark 等,這大概是和研究唯一有關的外務,後來我轉往這方向找研究點子。
另外還有協助將 lab 學長的論文投出去。我滿喜歡這篇的,完整版的內容比較多,可說是讓有的點都做到了,學長想出兩個新方法,一個可快速找到近似解,另一個可找到最佳解,且效率大勝暴力法。實驗結果說明前者的效率大勝後者,且和後者最佳解的誤差極小。後來論文投上了 DASFAA 2007,老師原本希望我去報告,可藉機認識學術研討會,也許可激發我做研究的熱情。不過我覺得自己不是第一作者,熱情不足,若研討會上有人提出討論,我大概也會興致缺缺,這樣似乎不太好。結果最後老師自己衝去,兩三天內來回的樣子,辛苦老師啦。