over 2 years ago

0 緣起──最短路徑問題

一般來說,我們在解決所有點對的最短路徑問題的時候,我們會想要對所有點對 計算在圖上他們之間的最短距離 。考慮一個鄰接矩陣 ,如果我們想要得到任兩點之間走不超過兩步的最短距離,可以某種形式計算這個矩陣的「平方」。即,對於任意點對 ,我們想計算的是枚舉任意中繼點 使得

試想一下,如果我們把這裡的「加法」對應到一般矩陣的乘法,這裡的「取 Min」對應到一般矩陣的加法,那我們就可以寫成:

我們回憶一下,一般矩陣相乘有個有趣的分而治之法:Strassen 演算法,大致上是將兩個矩陣各自切成四份,然後利用加法、減法與乘法完成運算。我們有沒有辦法把 Strassen 演算法應用在我們的最短路徑問題上面呢?其實是沒辦法直接套用的。我們仔細檢視計算 Strassen 演算法的步驟,就會發現原因出在減法上面。如果只有加法與乘法,那麼可以直接分別換成「取 Min」和「加法」是可以保持遞移關係的。可惜現在必須要進行減法,式子上沒辦法把一個求最小值的式子直接地拆成兩個式子加減(有些方法可以在數字範圍不大的時候套用 Strassen 演算法,比方說把所有數字變成指數大小,然後倒數硬乘起來再取 log,如此一來這個數字就會是 min 了。)

對於與輸入數值無關演算法裡頭,目前的 (min, +) 矩陣相乘問題也還沒有發現任何多項式指數嚴格少於 3 的 的演算法。那我們今天要聊什麼呢?我們來講一個比直接按照定義相乘還快一點點的 演算法吧!更正確來說,它的複雜度會是

1 拆成條狀

矩陣相乘傳統上除了拆成四個方陣或大致切成正方形的 Strassen 系列演算法以外,我們還可以考慮以下的拆解方式:

把左邊的矩陣拆成很多條 的長條矩陣 ,然後右邊拆成很多 的長條矩陣 。那麼原本的矩陣相乘就可以表示成:

對應到我們的 (min, +) 矩陣相乘就可以表示成:

於是,我們把一個 (min, +) 矩陣相乘問題拆解成了 個長條矩陣相乘的問題。如果我們仍然按照原本的方式進行計算,每兩個 長條矩陣相乘所花費的時間是 。因此傻傻地做顯然不會有任何好處,複雜度仍是紮紮實實地 。接下來,我們就要好好地針對 (min, +) 的性質探究一番啦!

2 (min, +) 性質

我們現在把注意力集中在一個 的長條矩陣 和另一個 長條矩陣 的乘積。令 是一個 的方陣。讓我們把矩陣的乘積寫開來:

決定性的觀察!

我們注意到,如果某個 是滿足 的最小的 ,那麼,對於所有的 兩邊的總和就會比較大:

移項之後我們可以發現這個不等號的兩邊可以只跟 有關係。

假設我們現在固定這個 。如果對於 我們預處理所有的 ,並且整理成向量的形式:

我們可以發現,若 是讓 的最小 ,那麼 就應該會是一個 維度的支配點對!這也解釋了為什麼這篇的標題是(四之二)而不是(五)了,嘿嘿。

分析

因此!可能會有一點點加速的空間,讓我們來分析一下!首先,我們枚舉所有可能的 值:這包含了 總共 種可能。每一次產生所有的 需要花費 的時間。然後花 的時間找出所有在 是「正確的最小值對應的註標」情形下的支配點對。由於最後乘出來的 總共有 個值,所有輸出的支配點對恰好加起來就是 個(演算法快就快在這裡)。

我們再把最外層拆成條狀矩陣的部份考慮進來,算得時間複雜度為:

該如何選擇 的值讓上面這個 upper bound 變小呢?我們可以發現當選取

的時候,會有

兩邊代入指數函數之後可以得到 ,因此選擇這樣的 值以後可以得到時間複雜度被右邊那項決定:

我們就得到一個 的 (min, +) 矩陣相乘演算法了!

3 所有點對最短路徑問題(APSP)

前面我們描述的是所有點對「走兩步以內最短路徑問題」,那如果我們想要計算所有點對真正的最短路徑,豈不是要計算 。注意到超過一定的次方以後,。我們可以利用倍增法,依次計算這些鄰接矩陣的「平方、平方、再平方」(這裡的平方觀念仍是 (min, +) 矩陣相乘)。

但是,如此一來,我們辛辛苦苦得到的解不就必須要多一個 倍,變成了 。這比大家比較熟悉的 Floyd-Warshall 演算法還要來得悲慘呀!

不過,好消息是,Aho, Hopcroft 與 Ullman 三位大師合作的一本書《The Design And Analysis Of Computer Algorithms》裡頭就有寫道(第 204 頁):利用自動機概念加上分而治之再加上類似 Strassen 流派的拆矩陣方法,只要能夠計算兩個矩陣的 (min, +) 相乘,整個 APSP 的時間複雜度與計算一次矩陣相乘的時間應該是一樣的!

礙於篇幅,只能請大家期待(四之三)了(呵呵…你以為說有就會有嗎)!想法不難,但是能想得到這個角度才真的厲害。

於是,總結我們今天的結論:我們可以在 時間計算兩個 (min, +) 矩陣相乘,並且在相同複雜度下找出任意實數值無負圈之一般圖所有點對最短路徑長度。耶。

4 參考資料

目前世界上最快的演算法是 [Chan '07]

下面這份投影片有一些更有趣的結果跟想法(包含隨機演算法)可以參考:

https://resources.mpi-inf.mpg.de/departments/d1/teaching/ss12/AdvancedGraphAlgorithms/Slides14.pdf

感謝 DJWS 提供的參考資源:

http://theory.stanford.edu/~virgi/cs367/lecture3-56.pdf

5 練習題

請求大家協助補充各大 OJ 的相關題目!

← 分而治之法(四):D維支配點對問題 分而治之法(五):L形鋪磚問題 →
 
comments powered by Disqus