星期一, 3月 26, 2007

資料結構與演算法(下)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做的,來找找做個介紹

張貼留言