將物理與計算機結合可以做些什麼？

01-05

我來講一個狹義相對論和計算機演算法的故事。這裡要討論的是

物理問題和計算機演算法的聯繫
物理思想在計算機演算法設計中的作用

1. 狹義相對論體系下的因果關係

先來看看狹義相對論下的因果關係。

在相對論體系下，每一個事件都存在於時空之中，有一個唯一的坐標(x, y, z, t)，其中x, y, 和z是事件在三維空間中的位置，而t是事件發生的時間。我們知道在三維空間中兩個點的距離可以用勾股定理計算，同樣，在四維時空中的兩個事件的距離也可以用類似的方法計算，不過，這裡算出來的是時空間隔。

兩個事件的時空間隔是確定的，但是它們的的時間間隔和空間距離都是相對的，從不同的慣性系觀察會得到不同的結果。比如圖中這個例子，貓和老鼠站在行駛的車上向對方開槍，然後雙方都中彈了。在這個場景中有4個事件：「貓開槍」，「老鼠開槍」，「貓中彈", "老鼠中彈」。我們來看看這4個事件的因果關係。

兩個事件可以建立因果關係的前提是：兩個事件之間可以用等於或小於光速的速度傳遞信息。

如果不能傳遞信息，我們就可以認為這兩個事件沒有因果關係，誰先誰後沒有意義，不同的觀察者會得出不同的結論。對於「貓開槍」，「老鼠開槍」這兩個事件，站在車上觀察的狗會發現它們是同時向對方開槍的，而站在地上的熊卻會得出不一樣的結論，它認為是貓先開槍的。

」貓開槍「和」老鼠中彈「兩個事件之間卻可以用小於光速的速度（子彈的速度）傳遞信息，所以」貓開槍「事件必然發生於「老鼠中彈「事件之前。同樣「老鼠開槍」也發生在「貓中彈」之前。我們把這些事件畫在」貓開槍「事件的光錐中，可以看出它們的關係。

從上圖可以看出，」貓中彈「和」老鼠中彈「都在」貓開槍「事件的未來光錐中，它們都發生在」貓開槍「事件之後。而」老鼠開槍「事件不在」貓開槍「事件的未來光錐之中，那麼這兩個事件是無法確定前後關係的。

這裡的所謂因果關係實際上是一種時序關係，即時間上的前後，而不是邏輯上的原因和結果。

2. 分散式計算機環境中的時序關係

現在來看在分散式計算機環境中的一個類似問題。設想一下這個場景：多個計算機通過網路連接，它們之間的通信方式是通過網路介質傳遞數據。每個計算機會把發生在本地用戶的動作廣播到其他計算機，所以一個計算機會收到來自不同計算機的多個事件通知，它需要獨立判斷出這些事件的時間順序。

用一個簡單的遊戲作為例子。

這是一個多用戶的遊戲。每個用戶從自己的計算機控制自己的角色。一個角色可以做出兩種動作：開槍和移動。為了例子簡單，我們假設如果對方沒有移動，開槍肯定可以命中。如果對方移動，則不會命中。被擊中後，角色的生命值相應減少。當用戶控制角色做出動作後，包含動作信息的數據向其他所有計算機廣播。

現在，貓和老鼠分別做出了開槍和移動的動作。兩條消息，「貓開槍」和「老鼠移動」，向其他計算機廣播。每各計算機需要獨立判斷貓有沒有擊中老鼠。

這裡需要區別事件和消息這兩個概念。

事件是指由於用戶的操作，導致本地計算機狀態發生變化，比如，用戶操縱貓開槍，或者操縱老鼠移動。
消息是指本地計算機發生事件以後，向其他計算機以廣播的方式送出的信息，如」貓開槍「消息和」老鼠移動「消息。

最簡單的思路是，讓每一個消息都帶上一個時戳(time stamp)，表示事件發生的時間。需要確定事件時序的時候，只需要比較消息的時戳就行了。但是，這個方法在分散式環境下行不通，因為沒有一個足夠精確的辦法讓所有計算機的時鐘都調到同一時間。就算調好了，由於硬體的輕微區別，各個計算機的時鐘也會漸漸出現偏離，並且越來越大。

所以，我們的選擇是採取與狹義相對論體系類似的方式來定義事件的時序，定義如下。

兩個事件可以建立因果（時序）關係的前提是：兩個事件之間是否發生過信息傳遞。

和上面的相對論中的因果關係定義比較，可以看出以下區別：

這裡我們去掉了關於速度的部分。這是因為，在網路環境中速度是不確定的，它可能受到很多因素的影響，比如路徑選擇，路由器負荷，軟硬體異常等。
另外我們也去掉了」可以"這個條件，因為它在網路環境中也是沒有意義的。由於速度的不確定性，如果沒有真正傳遞過信息，沒有辦法確定在限定時間內是否可以完成信息傳遞。

基於這個定義，我們就可以對上面的例子做出一個符合邏輯的判斷。如果「老鼠移動」發生在「貓開槍」之後，那麼老鼠被擊中。這意味著要求有一條消息在這兩個事件之間傳遞，而這條消息就是從貓計算機發出的」貓開槍「消息。如果老鼠在收到這條消息之前移動，那麼時序關係不成立，沒有命中。如果老鼠在收到消息之後移動，則時序關係成立，命中。

我們仍然可以把事件畫在」貓開槍「事件的光錐圖上。

值得注意的是圖中的距離不再是物理距離，而是以網路連接的計算機之間的一種邏輯上的距離。兩台放在同一間屋的計算機如果是通過廣域網相連的，它們的邏輯距離也可以很遠。這裡也沒有光和光速，但是我們仍然沿用光錐的這個概念。這個光錐代表在一定時間內，這個事件對應的消息能夠到達的計算機。

在老鼠計算機上發生了」老鼠移動」這一事件。如果它發生在收到「貓開槍」消息之後，那麼」老鼠移動「就在「貓開槍」的光錐中（圖中的B），意味著「老鼠移動」發生在「貓開槍」之後，也就是說，老鼠被擊中。反之，如果「老鼠移動」事件在「貓開槍」的光錐之外（圖中的A），那麼兩個事件沒有時序關係，也就是說，老鼠沒有被擊中。

這個判斷對於老鼠計算機來說比較簡單：如果移動發生在收到「貓射擊」消息之前，則沒有命中。如果移動在收到「貓射擊」消息之後，則沒有命中。這個順序在老鼠計算機上是清楚地，所以老鼠可以簡單的做出判斷。

對於貓計算機就不容易了。它在發出「貓射擊」消息之後，收到了「老鼠移動」的消息。它沒有辦法知道老鼠移動發生在收到「貓射擊」消息之前還是之後，所以無法判斷。同樣，狗計算機接收到了兩條消息，」貓射擊「和」老鼠移動「。它也無法對兩個事件的順序做出判斷。

對於這個特定的例子，讓老鼠計算機發出」我中彈了「的廣播通知可以解決這個問題。但是這裡我們不採取這個方案，因為

這是一個用以說明演算法的簡化例子。在廣義的分散式時序判斷場景下，這個方法不能用。我們面臨的情況往往是收到大量來自各個計算機的消息，需要判斷出它們的時序。
等候」中彈「消息導致系統判斷的延遲。其他計算機在收到這條消息以前無法給用戶反饋，從而降低用戶體驗。

所以，我們要求每台計算機在接收到消息後能夠自行判斷消息之間的時序。

至此，我們討論了分散式環境下事件的時序問題和它與相對論下的因果關係的相似性，但是還沒有看到這個問題的解決方法。這畢竟並不是物理世界，洛倫茲變化和閔可夫斯基時空圖都幫不上忙。

下面是演算法描述。如果你還有興趣，請繼續往下看。

3. 向量邏輯時鐘

1978年，Leslie Lamport 描述了分散式環境下的事件時序問題，並提出了基於邏輯時鐘的演算法（Time, clocks, and the ordering of events in a distributed system）。基於這一模型的向量時鐘（Vector clock）和狀態向量（State Vector - Concurrency control in groupware systems）等演算法為解決分散式時序問題提供了有力的工具。有趣的是，從這些文章中可以看出，相對論對演算法設計的影響十分明顯。

下面我們用向量時鐘來解決這個遊戲中的問題。

我們平時使用的物理時鐘只需要1個數字表示時間，比如從計時開始到現在的秒數。而邏輯時間是一個向量，其中的每一個元素代表一個計算機上發生過的事件總數。比如，在上面的遊戲例子中，我們有3個計算機，向量時間就可以定義為（貓事件數，老鼠事件數，狗事件數)。我們採用以下方法維護邏輯時間。

每一個計算機都對系統的向量時間有一個自己的拷貝。
計算機本地發生事件時，向量時間中對應的元素加1。
每次發出消息時，帶上自己的向量時間作為時戳。
收到消息後，根據消息中的向量時間更新自己的邏輯時間。

當遊戲啟動時，每台計算機上的邏輯時間都是（0,0,0）。當貓開槍事件發生時，貓計算機時鐘的貓事件數加1，所以邏輯時間變成（1,0,0）。從貓計算機送出去的」貓開槍「消息就帶著這個邏輯時間。當老鼠計算機收到這條消息是，它發現時戳中的貓時間元素比自己時鐘大1，於是它把自己時鐘的對應元素變成和消息時戳相同的值。於是，老鼠計算機的邏輯時間也變成(1,0,0)。狗計算機也做相同的處理。然後，老鼠移動，這使得老鼠計算機向量時間中老鼠元素加1，變成(1,1,0)。同時送出的「老鼠移動」消息帶著這個時戳。在貓計算機收到這條消息時，發現時戳中的老鼠元素比自己的時鐘大1，於是它也相應的更新自己的時鐘，變成(1,1,0)。現在重點來了，貓計算機也需要判斷"老鼠移動「和」貓開槍「事件的時序關係。這裡的方法是比較兩條消息中的時戳。

」貓開槍"時戳 - (0, 1, 0)
"老鼠移動「時戳 - (1, 1, 0)

比較的結果是，「老鼠移動」消息中的每一個元素都大於或等於」貓開槍「消息的相應元素。這說明，」老鼠移動「事件發生在」貓開槍「事件之後。結論：老鼠中彈了。

狗計算機也用相同的方法比較兩條消息，得出相同的結論。

在這個時空圖中，我們仍然可以看到光錐的影子。在「貓開槍」消息到達其他計算機後時空範圍，就是」貓開槍「事件的未來光錐。在這個範圍內發生的事件，我們都可以確定是在」貓開槍「事件之後。

下面來看另一個例子。

這一次，老鼠在收到」貓開槍「消息以前移動，所以，」老鼠移動「消息的時戳是(1,0,0)。在收到"老鼠移動」消息後，貓計算機同樣比較「老鼠移動」消息和「貓開槍」消息的時戳。

」貓開槍"時戳 - (0, 1, 0)
"老鼠移動「時戳 - (1, 0, 0)

現在，「老鼠移動」時戳中的元素有的大於「貓開槍「消息，有的小於「貓開槍「消息。這說明，兩條消息之間不存在時序關係，它們是並發的(Concurrent)。

從光錐圖同樣可以看出，「老鼠移動」事件在「貓開槍」時間的未來光錐之外，所以它們之間不存在時序關係。以上是使用狀態向量演算法解決分散式環境下的時序問題的一個簡單描述。在一個真正的系統中進行時序判斷需要考慮更多複雜的情況，而時序判斷的結果只是進一步處理的基礎。本文的重點是討論物理問題和計算機演算法的聯繫以及物理思想在計算機演算法設計中的作用。更深入的演算法分析就不在本文的範圍以內了。

計算物理學。然後就是各種苦逼的

計算流體力學（CFD）

計算電磁學

分子動力學（MD）

計算天體力學（包含計算相對論（Numerical Relativity））

格點色動力學（Lattice QCD）

。。。。。。。。。。

可以說很多學物理的（還有化學，生物），最終乾的都是苦逼的碼農的活，各種數據分析，模擬的搬磚。。。

這個問題範圍有點兒廣。我挑一點說吧。

我很喜歡的一本書是《遊戲開發物理學》。

念書的時候一直疑惑，射擊遊戲怎麼這麼真實，模擬飛行怎麼做到模擬，遊戲中物體下落的感覺為什麼這麼自然，計算機怎麼編的程序。

然後我就發現了這本跨界書，關鍵。。。這本書對數學要求不是很高，太體貼了。

量子計算機啊，前沿

量子化學的計算

原理是利用量子論，通過計算機的強大計算性能來計算物質的各種性質。

題主可以查一下以下幾個軟體

Gaussian，Vasp

贊多的話再仔細答

沒有物理哪來的計算機

集成電路。

可以做出一個叫havok的有趣引擎，幫助各種遊戲準確的模擬真實世界的物理效果

知乎這麼多計算機圖形學大V可以關注。計算結合物理的例子遍地都是：

基於物理的渲染：Physically-Based Rendering

動力學視覺模擬：GameWorks VisualFX Overview

當然，很多計算機程序可以描述的事物不是基於物理的，例如，在網路遊戲里你的速度超越光速，斯通見慣，無需遵循任何物理規則，這個角度，程序是基於邏輯的數字遊戲。

對於物理而言，物理更關注真實世界的運作規律，計算機當然是一個絕佳的科研設備和應用工具。