有哪些「上帝演算法」？

12-27

無意中發現能以O（1）的時間複雜度實現最短路徑演算法，具體是這樣的，N個節點，他們之間有若干條帶權值無向邊連接，求任意兩點之間的最短路徑。我假設節點是一個球，球之間用線連接，線的長度作為權值，拉著任意兩個球繃緊成一條（或多條）直線，那麼就是這兩點之間的最短路徑。我想不通計算機不能以這樣的時間複雜度還原這個計算過程，我暫時稱它為「上帝最短路徑演算法」。好奇有沒有其他「上帝演算法」？補充一下，很多人的關注點都在「扯繩子」這個字眼上，我現在換一種說法，迷宮中可走的路徑是導體，我把入口與出口通電，電子移動的路徑就是迷宮的解法。上帝的廣度優先搜索是與節點數無關的，這麼就說的通了吧？

先上結論：上帝演算法完全是扯淡。

如果10年前的我和19世紀的人交談，讓他來做最短路徑的演算法，他知道Dj演算法的話，會用筆紙把一步一步畫出來，然後算了半天出來說，哦，這是 $V^2+E$ 複雜度或者聰明點說是 $VlgV+E$ 複雜度。
但是10年前的我，把數據輸入到計算機裡面，用Dj"演算法，算一下秒出。19世紀的人要說，啊，看起來啟動一下計算機一下下子就出來了是 $O(1)$ 複雜度，這是上帝演算法。But，這個人看到計算的本質了嗎？
但是20年後的我，拿著幾千個內核的cpu，幾萬台分散式機器，把Dj演算法，改造成樓主的所謂「上帝式的拉直」演算法，然後跑一下，上百萬節點的圖結果也是秒出，樓主是不是也要說，啊，看起來啟動一下牛逼的集群一下下子就出來了是 $O(1)$ 複雜度，這是上帝演算法。But，這個人看到計算的本質了嗎？

---------------------------------------------割一下----------------------------------------------------------------

首先，這個「上帝式的拉直演算法」，是典型的Dj的並行演算法改造，現在各種大數據圖計算框架，入門例子就是Dj的分散式演算法。圖的每個點用一個計算單元表示，每一個點根據周圍點的情況計算和起始點的關係，一直到達點滿足最短路徑的退出條件。
然後，這個演算法並不是 $O(1)$ 複雜度，最壞的情形是所有的點都在一條直線上，所以是 $O(V)$ 複雜度。樓主仔細分解一下拉直的過程，會發現所有的節點都是在做計算，判斷和周圍點的距離，然後移動自己。但是最後達到拉直的最終也不是「你拉的這一步 $O(1)$ 」，而是微觀計算過程的，最壞的 $O(V)$ 步。你拉的這一步，意思是只需要一步啟動計算，不是實際計算只有一步。
再然後，樓主的「拉直的演算法」這是用實際的定律來模擬本質上的計算過程，為什麼這種演算法看起來很牛逼，很有效。這就像專用晶元來做專用的計算一樣，在特定的問題上無比效率，但是計算的本質是一樣的。
而且，正如專用計算和模擬計算在更大範圍內能力就弱的無比，儘管很多專用計算模型本質上也是滿足圖靈計算條件，都能算出結果。這個「上帝演算法」並不牛逼。如果一百萬個點，節點和節點之間的距離都是光年級別的距離，現在揉在小小的一個房間裡面。上帝啊，給我來展示一下 $O(1)$ 的「拉直演算法」吧，這個計算的啟動過程也是麻煩吧，現在的計算機，恐怕也是隨便秒出結果。
這讓我不經意聯想到，現在量子計算機。啟動計算環境無比複雜，然後天然的並行狀態遵循量子定律開始演化，迅速破解大數分解。

光學方法做傅立葉變換

如圖，左側是字元3的鏤空平板，將其放透鏡前面，用平行光照明，透鏡焦平面上將顯示其二維傅立葉變換。

來源：http://www.amazon.com/Introduction-Fourier-Optics-Joseph-Goodman/dp/0974707724

「電子移動的路徑就是最短路徑」……
你們高考不考這個的么……
並聯電路

友善度不要了：
這個問題基本上就是民科入侵計算機科學領域大薈萃。
補一句解釋：
脫離計算模型談複雜度都是耍流氓。
建議閱讀圖靈機的概念和解釋。

梁邊妖說：一切問題都可以用跳脫的想像力解決；
我覺得：一切類似的「民科」問題皆可通過往死里摳定義解決。

比如這道題，什麼叫演算法複雜度？什麼叫基本操作？什麼叫圖靈機？去維基看看這些定義，這問題還能提出來才怪。

再舉個例子：著名的 $pi=4$ 悖論。
1.什麼是圓周率 $pi$ ？
我們直接採用圓的周長和直徑的比值來定義。

2.什麼是圓？
我們這裡用「到平面上一定點是定長的點的集合」。

3.什麼是長度？
這個可就麻煩了，我們得分三步來定義。
3.1 線段的長度
最簡單，用端點的歐幾里得距離定義就行，不會產生什麼問題。
3.2 折線段的長度
這個也不難，定義為所有線段的長度和。
3.3 曲線的長度
維基告訴我們了：曲線內接折線段長度的上確界和曲線外接折線段長度的下確界如果相等，這個值叫做曲線的長度。

4.什麼是上確界：一個數 a。對於集合里的每個數 x ,都有 $xleq a$ ；而對於任意的 $c，集合里都存在一個數 b 使得<img src=$ .這個 a 就叫做上確界。
下確界類似。

好了，現在你能證明你給出的那個折線段的長度是所有外切折線段長度的上確界嗎？不能。所以整個證明無效。

如果每個這樣的「悖論」提出者都能在提出之前去維基把所有牽扯的定義查一查，我覺得99%的問題都會解決。

哦，對了，維基被封了……好吧那當我沒說。

因為上帝計算你的腦子更慢，所以你的腦子就覺得物理世界的計算好快。人類的計算機都是在從上帝的計算機里偷資源。目前偷得還不夠有效率。

==新增最後一條==
按照題主的描述，
一個電子不需要花任何時間計算就能在原子核附近做精確的球諧函數展開；
一根繩子不需要花任何時間計算就能解任意邊界條件下一維波動方程；
一盆水不需要花任何時間計算就能解出二維駐波；
一個球不需要花任何時間計算總是找到勢能函數的最低點；
兩個冷熱不同的物體不需要花任何時間計算就能知道熱平衡後兩者的溫度；
一群光子不需要花任何時間計算Maxwell方程組就能知道自己該如何衍射;
三個物體在一起運動不需要花任何時間計算就能得到三體運動的一個解=

你拉繩子，可是幾摩爾的原子，在用1/普朗克時間 Hz的頻率進行計算的。演算法複雜度根本就不是O（1），只是用了碾壓演算法複雜度的計算資源做到的好不好？
幾摩爾原子可是在用繩命為你算繩長啊~

類似的混淆概念的例子：
1. 一個M*N的圖片，人看一眼用O(1)的時間複雜度，計算機看一眼，至少也是個O(MN)吧？所以圖像識別演算法都是O(1)的時間複雜度嗎？
2. 用自然語言可以構造比圖靈機更強大的計算模型：」一個比圖靈機更強大的計算模型「。

時間複雜度是用來描述「數學操作」計算量的，」拉繩子「的操作不能用O(1)的時間複雜度的數學操作模擬，所以你這裡定義的」O(1)「並不是我們一般意義的時間複雜度。

平面幾何填空題求∠A的時候，畫出來用量角器量。

你說有可能畫歪量歪？對啊，你綁球那繩子長度也不準啊。誤差無處不在，因為你乾的這個事不叫計算，叫實驗。

這個是o1嗎？把所有點連一起這道工序就已經不是o1了吧……

Steiner問題的肥皂膜解法。

給定 n 個村莊的位置，要想把他們全部連通，最少需要修建多長的公路？這個問題被稱為 Steiner 問題，是由數學家 Jakob Steiner 提出來的。注意，和最小生成樹不同的是，公路是可以在中間匯合、分岔的。目前已經知道，Steiner 問題是 NP-hard 的，在規模很大的情況下，不能有效地得出最優解來。
然而，大自然卻是無敵的，它可以迅速秒殺這樣的難題。由於肥皂膜總會試圖讓自己的表面積最小，利用肥皂膜實驗，我們可以輕易獲得 Steiner 問題的解。

曾經在一篇博客里看到過這篇文章，十分有意思，分享到這裡。
NP-hard問題的特點就是，問題規模越大，解決問題的時間複雜度越高（指數級增長），而利用肥皂膜就能輕而易舉地解決一個NP-hard問題，很有趣。
視頻封面 Steiner問題的物理解法視頻

當然，視頻中最後也說了，這種方法求出的實際上是極小值(local minimum)而不是最小值(minimun)。但已經足夠讓人覺得自然的奇妙了。

reference：
Steiner問題的肥皂膜解法

update（20150323）：感謝 @Deep Reader的指正，Dij演算法不是指數級的複雜度，是二次冪多項式級的。這個地方是我記混淆了。對不起各位看官了～以及 @Deep Reader真是人如其名！

不請自來。
答題資格：gis相關開發人員。
我想目前的答案對題主的批評其實是缺少思考的結果，其實題主的上帝演算法確實很上帝的，這個演算法的時間複雜度確實是常數級的，問題在於目前的計算機沒有辦法實現這個演算法。
請聽我細細道來。
五年前跳入GIS這個坑，如今準備出坑了，這五年多的時間裡二維空間的一切都讓我感到奇妙，總是不時地去思考為什麼一涉及到二維的演算法，複雜度就恐怖得一比。dijkstra這種指數級複雜度（錯誤，此處應為O（n^2）感謝 @Deep Reader 指正！）的演算法，還得靠A*去減少複雜度，勉強得到近似解。當初看到A*的時候，簡直驚為天人，並在自己的代碼里模仿A*解決了一個大問題，如今想起來也是頗有感慨。說遠了，咱么扯回來哈，我也一直在想為什麼空間關係計算機處理起來這麼複雜呢？剛開始我得出的答案是：計算機的原生數據結構是一維的，所有高維數據都是通過一維的模擬來實現的。這當然是一個解釋，但我覺得還不夠，卻又想不通到底哪裡還不夠。直到最近又一次翻開《java設計模式》，當我看到調停者模式的時候，突然恍然大悟！原因就是——計算機的原生數據結構不支持關係的表達！
具體的內容就不複述了，可以參加《Java設計模式》的調停者模式一節相關內容。
在這個題目中，之所以人來扯一扯就可以達到O（1），而計算機直奔指數級揚長而去，就是因為原生數據結構不支持關係。

詳細說說。

一個二維的無向權值圖，一般我們會主要關注它的拓撲關係，在數據結構中，這種拓撲關係可以簡單地用一個對象引用+權值來表示。在題主的演算法中，還引入了歐拉幾何的二維空間關係，此演算法利用空間關係改變時，拓撲關係不變的特性來達到找出最優路徑的目的。

然而，在計算機處理時，空間關係怎麼表達的？（x，y）數值對，注意，在這種表達中，空間關係來源於計算，而非原生的數據機構。換句話說，當兩個對象的空間關係發生改變時，我們必須要通過一次「計算」來獲得二者當前的空間關係，而現實中，並不需要，因為關係是直接存在於物理世界的原生屬性中。
因此，「扯不動」這個關係，對於計算機而言，是非原生的，也就說，計算機原生的數據結構無法表達「扯不動」這個關係，因此，你必須在扯的過程中，不斷計算，並加入代碼來人工判斷是否還能扯得動。然後，你還得計算到底哪一條路徑是「綳直」了的，因為「綳直」其實本質上也是一種關係的體現。
我們做個特殊處理，把待求的兩個點a，b放在水平軸x上，橫向扯動，設a在b的左邊。於是，a的x值減小，而同時b的x值開始增大。問題在於，實際中，當a，b開始移動時，由於物理世界原生的關係，你無需去控制其他球和線，它們會「自動」地開始變化，最終達到綳直時的狀態。但計算機不行，這個變化的「關係」必須通過你的計算去達到，而計算的次數顯然與一共有多少個球相關，最終也會變成指數級（錯誤，O（n^2））的時間複雜度。

總結起來，其實題主這個演算法，對於計算機而言，確實是「上帝演算法」了，原因很簡單：你做了對於計算機而言，是它的上帝才能做的事情——你的世界裡「關係」是原生的。

如果，我是說如果，有一天，計算機內的數據結構原生地支持了關係···我擦，我再跳GIS坑來得及嗎？

以上答案是個人思考的結果，不可避免會有不嚴謹甚至錯誤的地方。望各位大牛斧正，因為我對空間關係的好奇是無盡的。

最後，考慮到工作關係，雖然可能是廢話，但還是說一句：
本答案未經作者允許，禁止轉載。

有哪些令人拍案叫絕的演算法？ - 冒泡的回答 - 知乎
跟我這個例子一樣哈，不過需要說的是，如果你真用物理做法來解決這個問題，則複雜度絕不是O(1)，甚至深究起來，複雜度是比計算機的計算要大的，因為哪怕不考慮你構造這個網子的時間，要把它整個拉伸，也至少需要拉伸O(∑Li)長度，其中Li是最短路徑中第i條邊的長度，由於你的速度不會超過光速，所以時間複雜度至少也是這麼大的，這還不考慮拉伸過程中其他鬆弛的邊對你造成的能量和速度損耗
ok，重點來了，如果在物理世界做這個結果，我們至少需要結果數字這麼大的時間，而在計算機中得到這個結果，則我們至少要做的工作量是將這些邊的長度加起來，而加法的時間複雜度是O(lgLi)，即便我們需要Ω(E)次邊的加法（E是邊個數），但是和lg∑Li和∑Li的巨大差異也足夠讓演算法在時間上勝出了，簡單說，就是在二以上的進位下，做加法比做實際的count更快，後者其實是沒有進位的數字表示法，就像古埃及的原始人用的那種做法一樣
這個加法的時間在一般情況下認為是O(1)，則是因為很多題目限定了可以在32或64bit整數範圍內得到結果，如果從複雜度本身來說，是需要計算的，參考我之前的blog：
偽多項式複雜度 - xtlisk的專欄 - 博客頻道 - CSDN.NET

O(1)是因為每顆球及每條繩子本身都起到了"處理器"的作用, 而"演算法"就是物理本身. 並行計算當然快啦.

圖靈的停機問題(The Halting Problem)
不存在這樣一個程序（演算法），它能夠計算任何程序（演算法）在給定輸入上是否會結束（停機）。

弱弱地吐槽一句什麼電子走迷宮那個不過是無數個電子同時搜索可能的路徑而已，對於圖靈機演算法來說就是做了無數次蒙特卡羅試驗……你要是給我阿伏加德羅常數那麼多數量級的核我也能秒出結果。根本不是與節點數無關，只是通常情況下阿伏加德羅常數遠遠大於節點數而已。

上面很多人已經指出了繩子的比喻的不嚴謹之處了。想補充一下電子的那個比喻有兩個問題。

電子其實走的不是最短路徑，而是遵循歐姆定律（或者更深刻的說，基爾霍夫定律）根據電阻不同分配不同電流而已。
就算我們不考慮第一點，電子之所以可以在常數時間內找到最短路徑是因為有很多很多電子在同時（隨機）做廣度優先搜索。計算機要有和電子數量一個量級（阿伏伽德羅常數級）的核數，宏觀上表現的確也是常數級複雜度。但你要把核數降到目前常見的比如4核，或者說你只有4個電子，這個常數級的基於廣搜的演算法得不到正確的結果，而只能隨機挑四個路徑，取最小值。

http://en.m.wikipedia.org/wiki/Spaghetti_sort
一個O(n)的排序演算法

你們都在說自然計算比計算機模擬快的例子。我來個自然計算比較慢的反例（逃

Stable marriage problem

計算機算stable marriage problem有O(N^2)的演算法。自然計算：把n男n女關到一棟設施里，過幾十年打開大門，然後你可以假設這幾十年總能達成一個equilibrium吧。。好，得解。