44 thoughts on “

  1. 這問題有點大,我分兩段講,這篇講Dijkstra演算法。

    Dijkstra的原始論文:只有大略做法,沒有實作細節,也就沒有明確的時間複雜度。

    O(V^2)版本:Aho, Ullman, Hopcroft的演算法著作,自行弄出了一個演算法,巧妙使用表格,時間複雜度是O(V^2),並且把它叫做Dijkstra演算法(多半是想紀念先人,科學領域常有這種事)。然後,眾所皆知的CLRS抄了這本書。因此,眾所皆知的Dijkstra演算法是O(V^2)版本。

    O(ElogE) = O(ElogV)版本:使用了binary heap。我不知道這是誰發明的。

    O(E + VlogV)版本:使用了Fibonacci heap。發明人是Fredman , Tarjan,叫做Fredman -Tarjan演算法。注意到此演算法的原理跟上面那個完全不同。

    順帶一提Fibonacci heap的發明人也是Fredman 。Fibonacci heap是一個病態的算法(請參考前一篇),沒有任何實用價值。因為CLRS介紹了它,所以就走紅了。也因此至今仍有不明就裡的老師用Fibonacci heap來荼毒學生。

    priority queue是泛稱,是指可以自動自發排序的queue,它可以是binary search tree、binary heap、binomial heap、Fibonacci heap。heap也是泛稱,是指可以隨時得到極值的資料結構,尤其是長得像樹的。priority queue和heap概念很像,儘管有點不一樣,但是我們並不會分得那麼清楚──這種事情不太重要。

  2. 這問題有點大,我分兩段講,這篇講複雜度。

    單論Dijkstra演算法,這是確定性演算法,不是隨機化演算法,時間複雜度上限和下限都是一樣的,都是O(V^2)。這沒有什麼好討論的。

    討論「所有可能的」單源最短路徑演算法,這就不簡單了。一個trivial、沒有討論價值的下限是Ω(V+E)──因為每個點每條邊至少都得讀一次呀。那麼有略大於Ω(V+E)、更逼真、更準確一點的下限嗎?沒有!地球人至今仍然不知道更好的下限。

    (順帶一提,課本上介紹這個概念,通常是以矩陣乘法為例,而不是以最短路徑問題為例。)

    因為搞不定下限,只好搞上限。很多人拼命發明新的演算法,嘗試降低上限。然而演算法往往過於繁雜,無法投入實用,已經發展到了病態的地步。演算法的頂尖會議經常出現這種病態算法。比方說,今年的SODA某篇論文就給了集合分割問題一個精彩的新上限:

    正常人看了都會崩潰。

  3. 另外補充一下。

    即便int改成char,CPU每次還是讀32位元,計算時間不會下降。

    但是int array改成char array,CPU每次得以載入更多變數,cache miss會減少,計算時間會明顯下降。

    填表格時是循序讀取陣列,cache miss理論上會減少為1/4。回溯時不是循序讀取,cache miss理論上會減少但不會到1/4。

  4. 修正好了,謝謝!

    for迴圈索引值打錯了。為了增加可讀性,一維固定用i,二維用j。

    prev原先是虛擬碼,現在改成程式碼了。變數型態正常下是用int。省空間是用char。更省空間是併入array,以位元運算添加於array最高位元,int array改成unsigned int array。更更省空間是用Hirschberg’s Algorithm,array和prev從二維降一維,不需要走旁門左道。為了保持可讀性,我還是用int。

  5. 系統自動分類成垃圾留言了。我手動還原了。

    你說的對。其實我不知道怎麼做。當時我看到Unit Capacity Network,我沒細想就把它們湊一起了。現在已經刪去了。真是抱歉。

  6. 不知道剛才發出來了沒有…自己沒看到就重新發一遍吧(如果看到了就無視這一條好了)
    Capacity Scaling Algorithm 中,每次增加的容量的確是 Unit Capacity Network,但是本來的容量仍然在,乘以二之後加上增加的容量,得到的新圖不一定是 Unit Capacity Network ,那麼如何使用 Unit Capacity Network 的算法進行優化呢?

  7. 請問下Flow中的Capacity Scaling Algorithm里的衍生閲讀中說到,“增加的容量是Unit Capacity Network”,但是原圖中的容量要乘以二再加上“增加的容量”,最後得到的圖並不是Unit Capacity NetWork?那如何處理呢?

  8. 不是遺失,是還沒畫。拖了好幾年了。

    拖稿原因很多。我列出其中幾個:一、我想製做立體圖片,能用滑鼠旋轉觀看,但是目前尚無合適的JavaScript套件。即便要自己動手做,我的程式功力還沒厲害到可以輕輕鬆鬆完成這件事,一想到就覺得麻煩,也就遲遲沒有動手做。二、三維凸包概念簡單不難學習,計算幾何書籍已經做了詳細介紹。我沒有什麼能補充的,也就不急著完成。三、三維凸包用途極少,無論是工程上還是理論上。國內外學校課程幾乎不談三維凸包算法,因此我也沒必要積極推廣。製作三維凸包圖片,性價比偏低,不如先搞其他主題。

  9. 匿名 說道:

    您好,3D Convex Hull那邊有些圖片遺失了,希望能夠修正,謝謝!

  10. 你的網頁裡面有一句話是:「時間複雜度來說的話,用當時論文提出的實作方式,修改邊權的部分為O(|E|)。」所以我才會想說你可能有讀過原始論文。

    正是因為很多paper引用,但是卻找不到原始版本,所以我才形容為都市傳奇。

    1965年朱劉宣稱完成論文,投稿國內期刊《中國科學》。《中國科學》的官方網站沒有提供1965年的論文,無論是中文版還是英文版。我在網路上也搜尋不到,可能沒有電子檔、只有紙本吧。
    https://zh.wikipedia.org/wiki/%E4%B8%AD%E5%9B%BD%E7%A7%91%E5%AD%A6_(%E6%9C%9F%E5%88%8A)

    1967年美國數學年鑑記錄了論文名稱的英文翻譯。不過我不清楚這是1967年出版的,或者是之後出版、之後收錄的。
    https://books.google.com.tw/books?id=6Zw8AAAAMAAJ&q=On+the+Shortest+Arborescence+of+a+Directed+Graph

    根據下面網頁的說法,朱劉投稿後,中國隨即對外失聯。直至1974年英國數學家才發現朱劉算法(是哪位?),看的是英文版(在哪裡?)。
    http://www.qzu5.com/zhuyongjin.htm
    http://www.qzu5.com/lz.htm

    1977年Tarjan的finding optimum branchings,這是我看過最早的引用,翻譯名稱跟年鑑一致。
    https://cw.fel.cvut.cz/wiki/_media/courses/a4m33pal/cviceni/tarjan-finding-optimum-branchings.pdf

    在看到原文之前,我還是傾向認為這是都市傳奇。這就好比課本寫著國父革命11次建立中華民國,但是事實卻是俄國買通孫文建立叛軍、日俄夾攻推翻中華民國。

  11. 楊子平 說道:

    你好
    我在看Label Correcting Algorithm
    在程式碼中
    我認為
    if (inqueue[parent[a]]) continue;
    inqueue[a] = false;
    這兩行應該要調換位置
    否則下面那行會沒跑到

  12. 你的情報網實在太強大了,我明明只有聯繫hansonyu123,可是他應該不是你同學吧?雖然我有在個板暫時備忘這件事,不過聯繫完就刪掉了,難道是因為這樣就被看到了嗎?

    關於匈牙利算法,感謝你特地跑來說明,既然我的code沒問題,那就沒事啦。另外我再順便補充一下,我的經驗是O(N^4)版本比O(N^3)版本還要快,因此我猜測匈牙利算法的平均時間複雜度應該還要更低,所以才有「簡單粗暴反而速度快」的現象。不過我印象中沒看過有人做過平均複雜度分析,也懶得深入研究。如果你身懷強大小宇宙、想要深入研究的話,你們系上有一位畢業系友蘇信豪(http://people.csail.mit.edu/hsinhao/),他有做過匹配的複雜度,前陣子也在SODA發論文,也許可以請教他。

    既然你來了那我再順便請教你一下,你那邊有朱劉算法的原始論文嗎?我找了很久都找不到原文。我有點懷疑朱劉算法是不是天朝創造出來的都市傳奇。

  13. ㄠㄨ
    我是日月卦長
    我同學轉給我看你問你的匈牙利演算法是不是O(N^3)的問題後
    我認為你的code是O(N^3)的
    也經過有卡O(N^4)的題目測過了
    http://uoj.ac/problem/80
    我說的「因此網路上大多數O(N^3)的code其實是錯的」是我那時候在寫文章時查了一大堆資料
    都說O(N^4)的方法是O(N^3)(很多都大陸的網站),所以才這樣說

  14. 對啊,所以之後用的是另外一種對偶(原點O投影到直線之後的座標),不是計算幾何常常見到的那個斜率/截距對偶。

    Hough transform整個過程是三步驟:對偶、轉成極座標、投票。其實就算沒有轉成極座標,一樣可以得到正確結果。使用極座標的理由,你給的文章裡面沒有提到。我猜理由是公式漂亮、變化速度均勻、提高精確度、限制數值範圍在[0,2pi]以提升窮舉速度諸如此類的。應該已經有人研究過這些東西,不過我懶得考古就是了。

  15. Yu-Han 說道:

    其實 Hough transform 原本是沒有用極座標的,而是直接用 point-line duality,是後來為了解決 infinity 的 case ,之後才有人提出使用極座標的方法,http://www.ai.sri.com/pubs/files/tn036-duda71.pdf

  16. Hough transform是窮舉像素(x,y)、窮舉穿過(x,y)的所有直線,每一條直線都要對偶成一個點。

    Hough transform不是點線對偶(直線的斜率和截距 => 點的XY座標),而是另一種對偶(直線 => 原點在直線上的投影點的XY座標,再換成極座標)。

    這個對偶沒有特別取名,也許可以叫做點圓對偶、點線對偶二次方版本、切線對偶,那之類的。

  17. 已經拿掉了,感謝。

    我也是用建表(histogram)AC的。我當初選錄這題應該是用來做為對照的。以前網站內容少,選題較廣較雜;既然現在有疑慮,還是拿掉比較好。

Leave Message

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s