奇怪的Rate

老實說我也不知道這是根據什麼來排的，只是覺得這個分析的圖很有趣就放上來了XD

願望

有時候，最微小的願望，反而很難以達成

---
這就是生活

最近

生活平順的跟鬼一樣，或許就是那麼平順，才覺得這是一個很好的生活吧，每天自由的念書，自由聊天，自由睡覺，自由翹課(這是不好的行為XD)

念書是越來越順了，在此感謝兩位女性朋友，一位為了我在班上的評語而生氣，一位跟我說，你人真的很好，不要理他們說的這些話，老實說，當我自己看到的時候我是置之一笑的，但是我為了這些人而感謝，不過有時候會陷入一種想法，什麼意見是自我該接受的，而什麼是該置之一笑的，如果全盤不接受只聽好話，這就很像綠色只看自由時報是一樣的有趣。

不過目前的我只想做好一件事，把我該學的學好...相信知道我的人都是那個字，有人說blog的Computer 味變的非常重...呃，可能最近無意在blog上搞笑吧，就盡量啦，連寫個孫燕姿都會寫成評論文...回憶成評論啊，我是不是對生活太過於認真了些?或許吧XD

在此提醒Josh，快去買張懸吧，呵，難得他會有肯聽的中文歌手(Josh如此要求，我看中文他肯聽的真的很少XD)，雖然他稱張懸是"基本教義派"的歌手(這聽起來像某激進教派，還好張懸唱歌不怎麼激進XD) 這算是一件令人高興的事，有時候也會想起常常傳歌給他的情形XD

---
雜記XD

隱藏

好耶~只是偶爾會無意間跳出來...Orz

ex：寫個信就被人查到了

---
盡量不要留真名在網路上XD

TeX4PPT

TeX4PPT 是一個讓Microsoft PowerPoint 可以順利show出數學方程式的一個轉換軟體，只要寫出TeX code就可以在文字方塊中按右鍵的"TeXify"即可順利轉換，是一個相當方便的工具，但是需裝LaTeX的complier為前置轉換，官方說明中，MikTeX為佳

前置軟體(只要是LaTeX即可)
MikTex 2.5 (2.6 beta試過，不能用)

TeX4PPT
官方網站

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

非正題：這一次是有史以來上課最緊張的一天(雖然課程內容不怎麼緊張)，Josh 身體不適，嗯，有點緊張，但上課越來越進入狀況，只是對沒學過圖論的我還是一個很大的問題，早上六點起來騎車也是一個不錯的經驗，只是一直下雨XD

---

2007/04/02 資料結構與演算法(下) 06 呂學一 投影片

今天的主題為算出all-pairs shorest paths tree(yen3註：相當於把Graph上所有的node都建shortest path tree)，而今日的主題有三，Naïve algorithms和改善其效率的dynamic programming和Reweighting(yen3註：若能把edge weight 都變正，則可用Dijkstra's Algorithm)。在進入正題之前，先討論。

• The setting
  對於問題的setting仍與上禮拜相同，有一Graph G=(V, E)，而每個edge有weight，而edge weight允許為negative
  


• The Problem
  
  • Input: Edge weight matrix w, where w(i, j) stands for the length of edge (i, j).
  • Output:The distance matrix d, where d(i, j) stands for the length of a shortest path from node i to node j.
  
  今天的問題仍然在討論shortest path trees和distance是否等價
  • 從all-pair shortest path tree求得distance table
    這相當的直覺，有n個node，而每一次皆跑n-1個node，總次數為n*(n-1)，所以為O(N^2)
  • 從distance table 算出 all-pair shotest path trees
    這看起來不怎麼直覺，但是就上禮拜的從distance找回shortest path tree的方法，是一樣的

    若是shortest distance呢？從r到v的點，我們從v點找起，把指向v點的edge weight掃描一次，若剛好等於，則是shortest path 的一個解，若小於此weight，則扣掉該重量，進行recursion，由於只有m個邊，我們可以保證在linear time 找到

    而每個row至多把所有edge走完為m次，而有n個node，所以為O(nm)(yen3註：懶的寫XD)
  
  所以今天重點仍舊是在shortest distance上
  

• Naïve algorithm - all-pairs distance
  根據上禮拜所教的演算法(Bellman-Ford, Lawler, Dijkstra)，Naïve algorithm - general edge weight上(可以有negative edge, negative cycle)，方法如下。
  
  • 先Run Bellman-Ford 確定G中有沒有negative cycle，如果有negative cycle則停止，可在O(mn)時間內完成(yen3註：怪怪的，因為只跑一次真的能保證能找到negative cycle?)
  • for each node in Graph G Run Bellman-Ford Algorithm，每一個點都是O(mn)，所以Time complexity 為 O(mn^2)，最多是任意兩點都有edge，則為C(n,2)*O(mn^2) 則worest case 為O(mn^4)
  
  若確定為each edge weight is nonegative edge weight則可使用Dijkstra Algorithm，for each node in Graph G run Dijkstra Algorithm，由於是nonegative edge weight，所以不用擔心negative cycle，每一個node為O(m+n^2)，所以為O(mn+n^3)，而使用Fibonacci heap的話，Time complexity 為O(mn+ n^2 log n)

那麼今天真正的主題就是，要把Naïve algorithm speeding up(yen3註：上禮拜是一個怪好笑的舌頭，這禮拜為一個戰鬥機代表speeding up XD)


• Dynamic Programming
  (JK註：以下的DP皆建立在Graph無negative cycle 上)(一種聰明的填表法，想辦法讓走過的都留下痕跡，recursive definition很重要)，首先，建立一個matrix w(i,j)，而w_k(i,j)指的是所有i to j 的path中，所使用的edges <= k中，挑選min edge weight sum為其value，定義如下
  
  • w_1(i, j) = w(i,j)
  • w_{n-1}(i, j) = d(i, j)
  
  而Recurrence Relation為
  • w_1 = w(i,j)
  • w_{2k}(i, j)= \min_{1<=t<=n}(w_k(i,t)+w_k(t,j))
  
  算出一個的(i,j)為O(n^2)*O(n)，而我們可用O(log n) 求完所有的點，所以總花費時間為O(n^3 log n)



• Dynamic Programming - Floyd-Warshall algorithm
  定義一個matrix, 而d_k(i,j)的定義為，把每個node編號，而從i到j的中繼點編號不能超過k，所以對於每個d_k(i,j)我們都有如下定義
  • d_0(i,j) = w(i,j) (it's clear)
  • d_n(i,j) = d(i,j) (d_n 是所有的點都可以經過或不經過，所以path distance就是shortest path)
  
  而它的 Recurrence Relation如下
  • d_0(i,j) = w(i,j)
  • d_{k+1}(i,j) = min{d_k(i,j), d_k(i,k+1) + d_k(k+1, j)} (把整個路徑分成i to k, k+1 to j而分別求)(yen3註：寫到這邊有一點後繼無力的感覺XD)


• Reweighting
  用意是把有negative weight edge 變成正的，如此一來可使用Dijkstra's Algorithm 做一個speeding up的動作。但是方法不是直接對每一個edge weight 加上一個constant value，這樣子會造成shortest path 改變(例如說，本來繞了很多圈在經過negative weight edge，可能因為加了一個constant value而造成不經過。)，在此，Johnson提出了一個方法
  • Assign a weight h(i) to each node i in G.(給每個node一個weight)
  • for any path P from node i to node j, we have
    \hat{w}(P) = w(P) + h(i) - h(j)
    (New edge weight = old edge weight + 起點的 node weight – 終點的 node weight)(前一個edge 的 end node weight會和下一start node weight做抵消動作，故不影響shortest path，而知道shortest path 之後，利用原圖G，即可在O(n^2)求出原圖的distance)
    
  • 此方法成立嗎？假設戴帽子的P為最短的，而沒有戴帽子P卻不是最短的，那麼，我們必然能找到一個Q比沒有戴帽子的P還要短，然後根據reweighting的方法，我們得到帶帽子的Q竟然比帶帽子的P還要來的短，矛盾，故沒有帶帽子的P一定是shortest path
  
  問題又來了，這樣子做reweighting的動作，並不保證edge weight為nonegative，所以Johnson提出的方法如下
  • 多設立一個為0的node，使其node連接到每一個node上，而edge weight 為 0
  • 如果G沒有negative cycle，則戴帽子的G也不會有negatvie cycle
  • 對於每個node的h(i)設為0 至每一個node 的weight sum
    可利用s.29的圖來說明，用三角不等式即可得證，d(0,j) <= d(0,i) + d(i, j)，d(0, j) 為shortest path，則d(0,i) + d(i, j) 至多有可能為d(0,j) 的其中一個解。
  
  使用了Johnson's Reweighting的方法之後由於edge weight為nonegative，所以可使用Dijkstra's algorithm，running time可達到O(mn+n^2 log n)

---

---
下次寫作時間不要拖那麼長了..Orz

How Would It Be

聽起來讓人心情不錯的歌，最近一直在聽這首

How Would It Be(Lene Marlin, Lost In A Moment, 2005)

What have I done?
What if it's too late now?
Did I do all I could, did I?
Did I make it good, did I?

Somehow it doesn't feel right
Is it really all over?
Did I think it through, did I?
What if all I want is you?

And now
I won't see you again
The moment was there but we lost it
Time changed it all
And we let it
We let it happen

And now
I wonder how it would be
If things stayed the same and we liked it
The end of a search 'cos we found it
How would it be?
How would it be?
How would it be?
How would it be?

What have we done?
What if it's too late now?
Was it always like this, was it?
Was it something we missed, was it?

Somehow it doesn't feel right
Is it really all over?
Was it all it could be, was it?
Did I give you the best of me?

And now
I won't see you again
The moment was there but we lost it
Time changed it all
And we let it
We let it happen

And now
I wonder how it would be
If things stayed the same and we liked it
The end of a search 'cos we found it
How would it be?
How would it be?
How would it be?
How would it be?

And now
I won't see you again
The moment was there but we lost it
Time changed it all
And we let it
We let it happen

And now
I wonder how it would be
If things stayed the same and we liked it
The end of a search 'cos we found it

How would it be?
How would it be?
How would it be?
How would it be?

普通物理學

期中考超乎想像的順利，大概因為早睡早起每天複習漸漸發揮功效了，考前也不停的狂念，如無誤差，此學期應可高分過關，原因，我不想再重修了。

當然，期中考題目很簡單也是真的XD

睡覺

昨日與朋友聊的非常高興，半夜三點才睡....早上醒來已經十二點....連翹四堂課，資料結構與演算法無妨，我一直靠著線上課程和隨機客在學習，現代小說，有點對不起老師。

室友相當的神奇，用手機設了五個鬧鐘，皆在我還沒有聽到時就按掉了，所以今天睡到十二點不是偶然XD

下雨

去旁聽隨機客的課，共去了5次，4次下雨，難得的高紀錄，我在上禮拜說，該不會下禮拜會下雨吧，果真成真了，獲得一個"雨男"的稱號，Josh 身體不適，我偷偷錄了音，具有單聲道立體環繞的效果，下次不會再做了，因為隨機客不是一個能接受學生上課的錄音，但是為了Josh著想，就偷偷錄一次吧XD

感想

三天看完海賊王50集，我的感想是什麼？

在現實生活中，我的朋友都好厲害(厲害用日文發音)

---
看海賊王是很熱血的一件事XD