是否存在利用自然規則運行的演算法？

01-16

某天突然想到的一個方法.這個方法在現實生活中應該找不到對應（由於假設條件不能達到），暫且把它歸為一個思想實驗.我盡量用最短以及最清晰的方式來描述它.
【假設】
1.人們可以創建任意密度的液體，給定任意大於0的實數a則某種機器可以返回 a kg/m^3的液體，並且創建過程時間複雜度為O(1).
2.上述創建的液體之間互不相融，即液體間可以利用密度不同的自然特性進行分層，且層與層之間界線清晰.

3.存在一種機器可以通過掃描液體直接讀取其密度值.
【步驟】
1.任意給定一維正實數數組A，例如：
A=[3.297, 4.238,...102.38,...,32.45]
2.遍歷該數組，並依次創建該數組元素對應密度的液體.
3.將這些液體混合，並在重力作用下自然分層，密度輕者處於上方，重者處於下方.
4.遍歷分層後的液體，讀取密度值存入數組B，則B為排列好的數據.
這樣的利用自然規則來處理的演算法是否存在？有哪些？類似的演算法（不一定是我舉的例子）是否可以在真實的世界中得到運用，從而可以利用自然規則來處理一些目前計算能力無法解決的問題？

（為了不限制發揮，標題中的「排序演算法」已修改為「演算法」）

　　這方面最經典的一個問題是：Steiner樹問題的肥皂膜解法

參見Matrix67的博客：視頻：Steiner問題的肥皂膜解法

但要注意的是這種方法只能得到極小值，未必能得到最小值，所以並沒有徹底解決問題。

　　再有就是分解質因數的秀爾演算法，需要用量子計算機來做，用到了量子力學中的一些神奇的現象，可以在多項式時間內解決此問題。

參見維基：秀爾演演算法

　　還有求解哈密頓迴路問題的DNA演算法，設想將一個圖的每個頂點用一段DNA分子編碼來表示，將連接兩個頂點的邊用第一個頂點的DNA編碼的後半段的補鏈和第二個頂點的DNA編碼的前半段的補鏈來編碼，然後將大量的DNA分子放入試管中反應，再經過提純等一系列手段就可以得到哈密頓迴路問題的解。還有一些圖論中的問題也可以用DNA計算來求解，這些演算法的典型特徵是它們將時間複雜性轉移為空間複雜性，在較少的多項式時間內可以求解NP完全問題。

參見維基：DNA運算

　　還可能有很多問題都有可能設計出來比較好的模型來解決。

　　另外值得一提的是：

「新的諸如量子計算機這樣的計算模型，可能可以快速的解決一些尚未知道是否屬於P的問題；但是，沒有一個它們已知能夠解決的問題是NP完全的。不過，必須注意到P和NP問題的定義是採用像圖靈機這樣的經典計算模型的術語表述的。所以，即使一個量子計算機演算法被發現能夠有效的解決一個NP完全問題，我們只是有了一個快速解決困難問題的實際方法，而不是數學類P和NP相等的證明。」

　　參見維基：P/NP問題

珠排序。時間複雜度O(1)，其實就是算盤吧……

在珠排序中，一行(row)表示一個數字。如果一行里有2顆珠子，該行代表數字2；如果一行里有4顆珠子，該行代表數字4。給定一個數組，數組裡有多少個數字，就要有多少行；數組裡最大的數字是幾，就要準備多少根杆子。
準備就緒後，釋放珠子，珠子（按重力）下落，就完成了排序。

珠排序

自然的排序演算法題主都給了個可行方法，就不提了。

自然界有一種最優化演算法，可以利用不同個體的特徵交換，搜尋出最優解。那是遺傳演算法。

自然界有一種網路設備，可以利用大量單元互相連接，而產生強大認知功能（記憶、辨認模式、學習）。那是神經網路。

最後給個網站鏈接吧 Algorithms in Nature。

---

更新：還有這本書非常值得推介，電子版免費下載 http://algorithmicbotany.org/papers/abop/abop.pdf

蒙特卡羅演算法：

打個簡單的比方，比如想知道一個不規則圖形的面積。先將該圖形放入一個正方形中，然後在正方形中隨機生成大量的黑點，黑點出現的位置完全隨機。最後統計所求面積中的黑點數量，除以總的黑點數量再乘上標準正方形的面積，即可近似知道該不規則圖形的面積。

我記得小時候看過一個故事，不知是真是假，主人公可能是歐幾里得也可能是白岩松。但是例子很有意思：有人想測量一塊不規則的土地面積，於是就去求助白岩松，白岩松就將地圖畫在一塊板子上，稱好板子的重量，再沿著板子把地形剪下來，稱好剪下部分的重量，用重量的百分比乘總的板子面積得到了這塊不規則土地的面積。這也算是一種蒙特卡洛演算法。

蒙特卡洛演算法的本質是用概率與統計的方法取代複雜的未知數學模型，看著有點暴力的樣子。但是在計算機的幫助下，可以迅速通過實驗手段得到近似解。而且試驗次數越多，結果越精確。

一大堆啟發式演算法（heuristic）都是模擬自然界的機制，著名的比如蟻群演算法、遺傳演算法、螢火蟲演算法、粒子群演算法。

其中很多演算法都是模擬動物行為的，比如猴子搜索（Monkey Search）、獅子演算法（Lion"s Algorithm）、蝙蝠演算法（Bat-inspired Algorithm）、布谷鳥搜索（Cuckoo Search）、大灰狼優化器（Grey Wolf Optimizer）、海豚夥伴優化（Dolphin Partner Optimization）……很多都是中國人貢獻的。

尼瑪動物園都快被這幫人挖空了。

網上搜一搜這方面的論文，簡直成百上千，而且人們還在源源不斷的製造出新的演算法出來。因為實在太多了，有時候覺得這些演算法其實也很無聊，就是根據一個自然界的行為搞一個類似的進行規則來，反正只要能在有限時間內找出一個給定問題的次優解就行了。

睡眠排序大法好……

#!/bin/bash function f() { sleep "$1" echo "$1" } while [ -n "$1" ] do f "$1" shift done wait

使用方法類似：

./sleepsort.sh 2 1 7 5 3 4

呵呵，排序什麼的都弱爆了，用激光搭建網格來算格點規範場論才是王道！見這個 slides: http://indico.cern.ch/event/289774/material/slides/0.pdf. 阿貝場和非阿貝場都可以！有沒有費米場都可以！時間是連續的！

不過我不做這方面，大牛來補完吧。

投針法求圓周率

布豐投針問題

本質上，計算機完全符合題主描述。

從某篇文章中摘抄一段，希望大家耐心看完，其實挺簡單，不要被篇幅嚇到，而且很有趣。

問題是這樣的：
假設這有一個各種字母組成的字元串，假設這還有另外一個字元串，而且這個字元串里的字母數相對少一些。從演算法是講，什麼方法能最快的查出所有小字元串里的字母在大字元串里都有？
比如，如果是下面兩個字元串：

String 1: ABCDEFGHLMNOPQRS
String 2: DCGSRQPOM
答案是true，所有在string2里的字母string1也都有。如果是下面兩個字元串：
String 1: ABCDEFGHLMNOPQRS
String 2: DCGSRQPOZ
答案是false，因為第二個字元串里的Z字母不在第一個字元串里。
當他問題這個問題時，不誇張的說，我幾乎要脫口而出。事實上，對這個問題我很有信心。(提示：我提供的答案對他來說顯然是最糟糕的一種，從面試中他大量的各種細微表現中可以看出來)。
對於這種操作一種幼稚的做法是輪詢第二個字元串里的每個字母，看它是否同在第一個字元串里。從演算法上講，這需要O(n*m)次操作，其中n是string1的長度，m是string2的長度。就拿上面的例子來說，最壞的情況下將會有16*8 = 128次操作。
一個稍微好一點的方案是先對這兩個字元串的字母進行排序，然後同時對兩個字串依次輪詢。兩個字串的排序需要(常規情況)O(m log m) + O(n log n)次操作，之後的線性掃描需要O(m+n)次操作。同樣拿上面的字串做例子，將會需要16*4 + 8*3 = 88加上對兩個字串線性掃描的16 + 8 = 24的操作。(隨著字串長度的增長，你會發現這個演算法的效果會越來越好)

最終，我告訴了他一個最佳的演算法，只需要O(n+m)次操作。方法就是，對第一個字串進行輪詢，把其中的每個字母都放入一個Hashtable里(成本是O(n)或16次操作)。然後輪詢第二個字串，在Hashtable里查詢每個字母，看能否找到。如果找不到，說明沒有匹配成功。這將消耗掉8次操作 —— 這樣兩項操作加起來一共只有24次。不錯吧，比前面兩種方案都要好。
Guy沒有被打動。他把他的皮褲子弄的沙沙響作為回應。」還有沒有更好的？「他問道。
我的天？這個傢伙究竟想要什麼？我看看白板，然後轉向他。」沒有了，O(n+m)是你能得到的最好的結果了 —— 我是說，你至少要對每個字母至少訪問一次才能完成這項操作 —— 而這個方案是剛好是對每個字母只訪問一次「。我越想越確信我是對的。
他走到白板前，」如果這樣呢 —— 假設我們有一個一定個數的字母組成字串 —— 我給每個字母分配一個素數，從2開始，往後類推。這樣A將會是2，B將會是3，C將會是5，等等。現在我遍歷第一個字串，把每個字母代表的素數相乘。你最終會得到一個很大的整數，對吧？然後 —— 輪詢第二個字元串，用每個字母除它。如果除的結果有餘數，這說明有不匹配的字母。如果整個過程中沒有餘數，你應該知道它是第一個字串恰好的子集了。這樣不行嗎？「

網路上抄的，以前看到過兔子比喻：

來自：

局部搜索，模擬退火，遺傳演算法，禁忌搜索，門特卡羅演算法的形象比喻

為了找出地球上最高的山，一群有志氣的兔子們開始想辦法。

1、兔子朝著比現在高的地方跳去。他們找到了不遠處的最高山峰。但是這座山不一定是珠穆朗瑪峰。這就是局部搜索，它不能保證局部最優值就是全局最優值。

2、兔子喝醉了。他隨機地跳了很長時間。這期間，它可能走向高處，也可能踏入平地。但是，他漸漸清醒了並朝最高方向跳去。這就是模擬退火。

3、兔子們吃了失憶藥片，並被發射到太空，然後隨機落到了地球上的某些地方。他們不知道自己的使命是什麼。但是，如果你過幾年就殺死一部分海拔低的兔子，多產的兔子們自己就會找到珠穆朗瑪峰。這就是遺傳演算法。

4、兔子們知道一個兔的力量是渺小的。他們互相轉告著，哪裡的山已經找過，並且找過的每一座山他們都留下一隻兔子做記號。他們制定了下一步去哪裡尋找的策略。這就是禁忌搜索。

還有一個MC 演算法

5、兔子們隨便生產，產下了大量的兔崽子。兔崽子到處耍歡了跑，弄得全世界滿是兔子。這些兔子中，站在最高處的兔子，它就找到了地球上最高的山。

時間是單調增加的，這是最簡單的自然規則，所以一覺醒來排序就完成啦：

main.c

#include & #include & #include & #include & #include &

int main(int argc, char *argv[]) { while ( --argc &> 1 !fork() ); sleep(argc = atoi(argv[argc])); printf("%d ", argc); wait(0); return 0; }

% cc main.c % ./a.out 8 7 5 1 2 0 0 1 2 5 7 8

人工智慧裡面有一個啟發演算法叫「退火演算法」。但這個演算法不是排序用的…

題目問的是實數的排序

排序這個問題本身是計算機科學近乎研究爛的

給實數排序犯不上引入一個高成本有誤差的物理過程 (但還是有, 如珠排序 / brad sort)

如果問題換成"可以用物理過程來計算的數學問題"就有一些. 比如測面積求數值積分

也有用計算機模擬物理過程來求解的

如模擬退火法, force-based graph layout algorithm

廣義上看可能遺傳演算法也算..

http://zh.wikipedia.org/wiki/%E5%85%83%E8%83%9E%E8%87%AA%E5%8B%95%E6%A9%9F

（細胞自動機）

我想過一個隨機數生成演算法，具體是通過麥克風連續採樣實現的。這個應該是題主所說的那種「物理演算法」的應用了。

離心機算嗎

一種野生的菌類忘記叫什麼，類似苔蘚一樣的，但是比苔蘚更小，這種菌類可以自行生長，不斷擴展自己的地盤，接觸到更多的食物，然後如果某地點有著非常豐富的食物，則能夠在食物之間形成通道傳輸養分。

然後科學家就利用這一特性，將這種細菌放在培養皿中間，周圍點上幾滴營養膠，然後過幾周就發現，菌類生長的形狀，是以這幾滴營養膠為節點，形成的一個網路。

重點是，這個網路是最節省路徑的，如果把這幾個節點按照東京地圖分布排列的話，那麼網路的形狀就和東京鐵路網相重合。而後者是經過人精心計算才設計出的網路圖，是最優解。

看到這個問題不把這個視頻貼上來簡直對不起良心啊！

利用遺傳演算法解決了人類行走、爬行等動作之謎……

【3D物理引擎實驗】多P補全計劃

我想看過之後你會回來點贊的……

今天剛學到的，熱土豆演算法

拿到一個滾燙的土豆，下意識以最快的方法讓它離開手（隨便扔）而不管扔的方向