好想成為人類啊：計算機算法的發展歷程

9654

筆者是失敗的OIer，已經afo兩年，如有錯誤，還請指出。

人和計算機的區別在哪裡？
人是有腦子的，有主觀能動性的，會自己提出「思路」的；計算機是沒有腦子的，只能聽命於代碼的，是按著程序打工的社畜。
人是算力低下的，人腦的運行內存可能頂多就一個小小的數組；計算機的算力自然是不消說的，最小的測評機也有32MB的運行內存，現在連移動端設備都會有動輒5GB以上的運行內存了。
於是我們可以歸納出一個特點：人是靈巧的fvv，計算機是坦克，毫無靈活性可言但超級暴力。

巨型計算器——前計算機科學時代
由於計算機實在是太「笨」，在初代計算機ENIAC橫空出世時，大家拿它幹什麼呢？當巨型計算器使。當時的計算機無法執行複雜的指令，只能讓人類替代它思考，進行的計算還全都是人類的思路，是傳統意義上的數學。你會用計算機強大的算力幫你求導、取對數，但你不會想著讓它幹點別的。
在計算機出現前的年代，曾經有一群被稱為「computer」的女性。她們負責複雜而重複的計算工作。這之後，這個詞被用於命名這種巨大的機器，這也許能說明計算機最早的用途。

優雅的暴力——經典的計算機算法
等到計算機的性能略有提升時，一個想法出現了：既然我可以讓計算機替我執行超長的計算，那能不能讓這個過程更加長，讓它更加普適，在過程中加入分支、循環，最終變成一個設計出的半自動過程？既然計算機沒法自己思考，人類的腦子又無法想像整個過程，那能否通過一個小的切入點，構建一個計算機可以使用的，依賴算力的模型，從而讓這個坦克知道怎麼走，替我幹活呢？「計算機科學」在這樣的背景下應運而生。這個年代出現了很多如今在信息競賽赫赫有名的算法，它們的特點是注重時間和空間的優化、在算法上部分脫離人類思維的侷限。在計算機的性能尚不發達的年代，處理冗余的消耗對於一個算法是至關重要的。同時，算力已經有了一定程度的發展，是時候讓計算機進行一些「暴力」的操作了。
這個年代代表性的算法有SPFA、動態規劃。關於這兩個算法的詳細原理我不在這裡展開，感興趣的可以在CSDN上搜索。SPFA大致的思路如下：（因為我不知道我寫得是否足夠親民，這一段可以跳過，不影響閱讀）
作為老古板暴力枚舉算法Bellman-Ford的優化，Shortest Path Finding Algorithm最大的特點就是「實在」。在鬆弛一條邊時，只有當前路徑長度小於該節點儲存的路徑長度且終點節點不在隊列內時，才會將終點節點入隊。對比B-F的「我全都要」——關我p事，我全都入隊，SPFA在高度隨機的稀疏圖中效率極高。
（雖然現在一直有人因為SPFA的不穩定性黑SPFA，但是SPFA是真的快，能做負權環，改良一下就可以增強穩定性，只能說別尬黑了。）
SPFA的思路是以一個特定的方式從單點開始搜索整張圖，不像人類搜圖需要把每個路徑全部窮舉，搜索還不一定有序，可能會有一些對於特定情況適用的奇技淫巧，對於SPFA，除非「有可能使路徑更短」，否則它都不會鳥這條路，搜索方式高度保守，很老實地枚了一圈。SPFA是一種「優雅的暴力」，是高度優化的窮舉。

模仿與超越——啟發式算法的出現
在計算機的算力高度發達，已經不再需要為了內存和時間精打細算的年代，就像孩子長大了家長把孩子放出去闖世界一樣，人們想讓計算機「自己行動」。所謂「自己行動」並不是現在的人工智能，它遠沒有AI智能，但它與傳統算法最大的不同就是：由於空間和時間的寬裕，讓計算機「犯錯」後自己學習成為了可能，即「啟發式算法」。在計算機手頭發緊的年代，任何一個錯誤可能都會產生不必要的消耗，但現在不一樣了。
如果說之前的算法是科學家們絞盡腦汁設計一個完美的藍圖讓計算機自己閉眼開坦克，那麼這時候的算法就是科學家放著計算機自己開坦克，反正撞壞了也沒關係，坦克變結實了。撞牆了的話，這個坦克會自己掉頭，直到它成功為止。
這個時代代表性的算法是啟發式搜索IDA*，模擬退火SA。模擬退火的大致原理就是模擬金屬的退火過程：高溫時高度無序，計算機隨機亂跑，但隨著溫度的降低，計算機的每一步操作越來越精細，最終收斂至最優解的點。
啟發式算法的特點是效率可能不如傳統算法，但因為允許試錯，將局部最優解當作全局最優解的情況大幅減少。在適用範圍上，啟發式算法的邏輯往往不如傳統算法死板，開放性的結構使啟發式算法能適應更加複雜、更加混亂的數據，充分發揮了計算機坦克的優勢。

成為人類——深度學習與算力爆發
隨著電子技術的發展，如今算力的限制已經不在話下。以往單計算機算力的限制被徹底打破，算力不夠就整多點服務器好了。這自然給了人們很大的發揮空間：如果讓啟發式算法自身不斷遞歸，讓這個學習過程不斷持續下去，是不是有一天，計算機就不再需要人類發號施令了？既然它都能在我的指導下學習了，那麼我能不能讓它明白怎麼學習，從而讓它自己學習，最後自己幹活呢？
恭喜你發現了機器學習與人工智能。
從「編程解決問題」到「由數據學習規律」的範式轉移，此刻，實現了。
這樣的事情在二十年前還是難以想像的。我認識二十年前從事相關工作的人，那時因為算力的限制，他們的項目最終失敗了。他們沒能想到的是，在那個年代絞盡腦汁都無法通過優化解決的問題，在現在只需要加多幾台服務器就能解決。
不知道各位有沒有了解過：
#pragma GCC optimize(3,"Ofast","inline")
沒錯，就是著名的O3優化。O3通常能帶來10～30%的提升，極端情況下能到數倍，加上Ofast之後能優化更多（代價是隨手開優化精度去他媽）。O3已經是常見單程序層面優化的天花板（因為沒有包括更高層面的LTO之類），但比起堆算力依舊是路邊一條。
算力帶給了人們無窮的可能，而對於計算機，它開始「成為人類」。
坦克開始變得越來越靈活，懂得自己跑圖，同時坦克的攻擊力一點不減，說人話就是，坦克成精了。

從人類開坦克到坦克自己跑圖，計算機算法的發展正是不斷學習人類思考的結果，而背後的動力便是算力的進步。這與生物的進化不謀而合：在生物體變得越來越高級時，大腦便變得越來越聰明。同時這也讓我們不禁感嘆人類大腦的精妙：雖然算力不怎麼樣，但這種思考的能力，計算機迭代了這麼久，經過了這麼多年，也還沒完全學會。
在某一天，你腦中從無到有的靈光一閃，可是計算機拼盡全力也無法模仿的奇蹟呢。

窾坎镗鞳

我一直在想，人类是怎样从使用石头开始到使用想计算机这样的精密工具的；从泥塑木雕到光刻机，这样的精密度提升真的很让人感到人类集体的伟大。

blast

科学一直在不断给人带来惊喜呢……
关于AI智慧爆炸的担忧越来越多了，到那时人类又会拿出什么样的奇迹呢？

星阁少女

不好的回忆全都回来了（指写不出来的代码
（IDA*楼主学懂了吗 能给我讲一下吗）
在我看来计算机的神奇之处在于高速执行大量指令 但如何做到“高速”，执行何种指令，以及最重要的，这一切的结果会被用来干什么，才是人类智慧真正闪耀的地方啊