星期五, 4月 06, 2007

資料結構與演算法(下)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

張貼留言