回憶

很多很多天以前，我就想寫一篇有關孫燕姿的文章，但是苦無時間...

對我而言，聽音樂是一個具有很特殊的回憶之事，孫燕姿對我而言就是一個很特殊的高中回憶。我高一的時候，她的第六張專輯"未完成 To be continued"出來了，我聽一聽之後，不知道有什麼動力，我餓了一兩個月，把她前面五張專輯買齊，現在想想，仍屬一件神奇之事。

照慣例，要說話之前，我們先來看看，她出專輯的記錄(破例記錄到月)

• 同名專輯 - 2000.06
• 我要的幸福 - 2000.12
• 風箏 - 2001.07
• Start自選輯 - 2002.01
• Leave - 2002.05
• 未完成 - 2003.01
• The Moment - 2003.08
• Stefanie - 2004.10
• 完美的一天 - 2005.10
• 逆光 - 2007.03

就發片速度來看，早期的速度可謂是迅雷不及掩耳，到後來越來越慢(一方面是合約問題，一方面是她真的唱的很累)。

對她歌的感想是什麼呢？Josh Ko對我說了如下的話

剛出道時耳目一新，但是久了就與一般歌手一樣

對我而言

剛出道時耳目一新，但久了就陷入了複製自己的迴圈

何謂陷入複製自已的迴圈？周杰倫是個很好的例子(我直到現在還是只聽同名專輯和范特西，雖然咬字還是模糊，但是創作原味仍在)一般歌手為什麼不敢跳脫既定印象呢？因為怕失去原有的老聽眾群，更害怕無法開發新的聽眾群，如果仍然走一脈的唱風，孫燕姿的確出的每一張專輯都有固定的支持群眾，但是卻很難再吸引新的群眾了。

"逆光"出來時，我一首都沒有聽過，即以掏錢預購之，聽完不出預料的失望，這張專輯的歌曲鑑別度不高(鑑別度高的？我要的幸福)，聽了十首歌很像聽了同一首，硬是要聽的話...我頂多只能分出其中三首。事實上孫燕姿後面所出來的專輯都有歌曲鑑別度不高的問題，帶來的就是人氣下滑(The moment的"遇見"或許是例外，與電影"向左走，向右走"結合，事實上很多歌都與電視電影行銷)，更別提那奇怪的銷售量數字(或許會有專業的姿迷提出精確的數字反駁，但是我不得不說，歌迷流失是一個事實)，其他有關孫燕姿的想法，我想，與大部分人相同。

我是不是姿迷，或許是，早期我與"18度C的孫燕姿"站長、yahoo家族"愛姿病末期病房"的家長 有過接觸(家長都叫我小藍XD)，那是我一段很快樂的網路生活(少不更事時，曾經過著每天灌水18度的日子XD)，或許是姿迷，我會以較嚴格的標準來看待。

但是就今年而言，"逆光"是不是一張好專輯，是，因為台灣整體的流行音樂界品質也降了不少，不然我不會轉聽外文歌曲和非主流樂團。張惠妹的姊妹不也賣了上百萬張嗎:)

---
看來最近都走懷舊風

發現

真的要寫一份說明document的話，用字要嚴謹，這好像不是現在的我所能辦到的，不過願盡力一試，當然，排版要有一定的乾淨程度，這是一必然要求，SIC已經完成，SIC/ XE，我想我會照我自己的意思來寫

才能?

才能能當飯吃之外還能做什麼？

當水喝XD

---
為什麼我早起就要那麼冷Orz

資料結構與演算法(下)05 by 隨機客

非正題：今天上課算是比較輕鬆的一次(是進入狀況還是課比較好懂呢?我也不知道XD)，上課還被隨機客詢問(當然，我答不出來XD)，興起了換位子的念頭XD

---

2007/03/26 資料結構與演算法(下) 呂學一 投影片
今天上課的主題是Shortest-Path Tree Algorithm, 主要分有Bellman-Ford, Dijkstra Algorithm

在進入Algorithm前，先行討論此問題的背景

• The setting
  
  • The graph G = (V, E) is directed with edge length w. (此圖必需是個有權重的有向圖)
  • The length of each edge could be negative. (允許圖上的edge 為 negative)
  
  


• The problem
  
  • Input: A directed Graph G=(V, E) with weight edge w.
    A node r of G
  • Output: A tree T rooted at r such that the path of T from r to each node u of T is a shortest path from r to u in G.(yen3註：一個root 為r 的shortest path tree.)
  
  


• We may assume that each node in the graph is reachable from r.(yen3註：假設r 可以到達每個node)
  那麼在Graph中，有unreachable node，則一開始則remove掉，而不失一般性(Without loss of generality)，為什麼呢？
  尋找對r所有的unreachable node只需要花linear time，用DFS(depth First Search)從r開始，把所經過的點編號，而沒有被編號到的node就是unreachable node，而執行DFS只需要linear time，故此假設不失一般性


• Can a shortest path between node u and v contain a cycle? (是否會有cycle在shortest path tree上呢?)
  答案是否，我們把cycle weight sum分成三種狀況
  • cycle weight sum is positive: 此狀況不可能發生，因為這一定不是shortest path，因為一定不會通過，因為把此cycle 拿掉則path會更短
  • cycle weight sum is negative: u到v根本沒有shortest path，繞了n圈為最短，則繞了n+1圈會更短，則繞不完，所以有negative cycle weight的Graph, 則shortest path 不存在(這是一個if and only if)
  • cycle weight sum is 0: 則不會通過，就沒有cycle，這樣子可把cycle做一個remove的動作，使其cycle不在shortest path上


• Single-source shortest-path problem
  在此問題上為single path，但是與一般的path定義不同，一般的path定義為該node通過後則不能再通過，但是在此，我們比較確切關心edge weight sum


• Such a shortest-path tree always exists? 不一定，原因如上
  若r至任何一點u，都是reachable，就找所有可以走到的方法，事實上有可能是無限條，但是限制在G has no negative edge 和remove unreachable node 和 only think about single path ，則shortest path 則會變成有限條


• The shortest-path tree problem is equivalent to finding the distance from r to each node u in graph G. (尋找shortest distance和shortest path 是等價的問題)
  何謂等價的問題，若A和B是等價的問題，則找到A的答案之後，我們可以在linear time 找到B的答案，且找到B的答案之後，也可以在linear time 找到A的答案
  那麼為什麼shortest distance 和 shortest path是等價的問題？若已知shortest path，則把edge weight求其和即為distance，可在linear time 找到，若是shortest distance呢？從r到v的點，我們從v點找起，把指向v點的edge weight掃描一次，若剛好等於，則是shortest path 的一個解，若小於此weight，則扣掉該重量，進行recursion，由於只有m個邊，我們可以保證在linear time 找到


• 補充說明：在演算法上所定義的linear time並不是指O(n)，而是指執行效率相對於input size，若input size 為O(n^2)，而RunTime也是O(n^2)，則我們說該演算法是linear time

終於可以描述演算法嘍XD

• Bellman-Ford Algorithm
  此演算法的方式如下
  
  • 設一個array d[u]為從r 到u的距離
  • 對其array做初始化的動作
    • Let d[u] = infinty for each node u of G
    • let d[r]=0(自己到自己距離為0)
  • Repeat improve對於d[u] for d(u)的估算
  
  而Relaxing edge(u,v)為

      If d[v] > d[u]+w(u,v) then
          let d[v] = d[u] + w(u,v)

  那何謂A phase of improvement

      For each edge(u, v) of G do
          relax edge(u, v)

  問題又來了，試問phase of improvement 要跑幾次才能確保答案的正確呢？
  如果node為n個，則跑n-1次就可確保答案正確性，每當我們跑了phase of improvement，則會有一點被改善(yen3註：竟然不會證Orz)
  那麼效率呢，由於有n個node，m個edge，每個點皆跑m個edge，所以Time Complexity = O(mn)
  
  第二個問題是，若圖中有negative cycle，則我們要怎麼得知？
  問題也很簡單，已知演算跑n-1次已經得解，若跑了第n個phase 而仍然有d[u]被改變的情形，則知道與原先預想的不合，此圖有negative cycle
  為什麼？在s.31說明(yen3註：證明竟然忘了...真神Orz)
  
  若該Graph 為一個 Directed Acyclic Graph DAG呢? 方法如下
  

  • 先對該DAG做topological sort
  • 根據topological sort 的順序，由小到大(slight 上寫由for 1 to n)做relaxing動作

  其Running Time 是 O(m+n)


• Dijkstra Algorithm
  
  (題外話：Edsger W. Dijkstra 是提出“Goto is considered harmful.”的人)(yen3註：此話真的是powerful，對於現在學assembly language的我而言更是一個有趣的問題。)
  
  此演算法是一個極具powerful的演算法，此演算法求shortest path是建立在無non-negative weight edge, non-negative-cycle的DAG上，方法如下(此方法不用依靠topological sort做前置作業)
  

  • 做與Bellman-Ford Algorithm同樣的初始化動作(與對其array做初始化的動作相同)
  • 每一個iteration中，尋找unprocessed node中，尋找到目前為止smallest path做relaxing，直到每一點都做完為止(換句話說，在所有未處理的點找到該點花費最少的來做處理)

  
  此方法的正確性呢?由s.50得知。假設u是unprocessed minimal node，而在處理到u node時出錯了，而y node 與processed node 的範圍只用一條edge連結，所以我們確信d[y] = d(y)，但是我們又說u是unprocessed minimal node，而用y連過去則會讓d[u] > d(u) >=d(y) = d[y] 矛盾(yen3註：證的真爛Orz)
  
  則Running Time用 Naïve implementation: O(n2 + m).
  With Fibonacci heap: O(n log n + m).

---

---
聽Josh Ko說明才得知簡報上的數學式是用TeX4PPT做的，來找找做個介紹

塞車

騎摩拖車遇到塞車算是很大的難題之一，雖然演算法學的是圖論，但是關係不大XD 唯一的關係，你得避開車潮，今日六點半起床(上大學以來最早)，七點出發...還是躲不了塞車的惡夢，下禮拜決定六點起來好了

---
再塞我前天就睡台大(會不會有兩個人做惡夢XD)

XD

家樂福的XD
家福福的XD2

---
是男人就該逛家樂福