軟件測試悖論之Braess悖論

關于 Braess 悖論的原始工作是 Dietrich Braess 的“ über ein Paradox der Verkerhsplannung ”（ 1968 ）。而我的例子，是基于我發現的幾個例子，這幾個例子對 Mark Wainwright 的工作作出了貢獻。當時我不能親自參加到 Wainwright 的原始工作中。

　　Braess 悖論相當復雜，所以這里我給一個簡化的、離散近似。假設象圖 5 中顯示的一樣有四個城鎮——城鎮 A ，城鎮 B ，城鎮 C 和城鎮 D 。

　　連接任意兩個城鎮之間的每一條路都有一個關聯成本，由圖中與路相鄰的方程給出。成本是陸上汽車數的函數。你能想象成本代表了在這條路上行駛所需要的時間，或者所需要的汽油，或者你們想要最小化的某些因素?，F在假設某一個早晨，有 6 輛車從城鎮 A 離開，每次一輛，目的都是城鎮 D 。汽車 1 離開的時候，路上完全是空的。該車可以從兩條路徑中選擇： A-B-D 和 A-C-D 。 A-B-D 的成本是 [4(1) + 1] + [1 + 16] = 22 。由于該圖的對稱性，路徑 A-C-D 的成本也是 22 。假設汽車 1 選擇了路徑 A-B-D 。

 　

　　圖5 公路網絡： Braess 悖論

　　現在汽車 2 準備離開了。他看到汽車 1 在路徑 A-B-D 上，因此知道了現在 A-B-D 上的成本是 [4(2) + 1] + [2 + 16] = 27 ，所以他選擇了成本只有 22 的路徑 A-C-D 。汽車 3 看到每條路徑上都有一輛車，所以選擇了成本是 27 的路徑 A-B-D 。汽車 4 選擇了成本是 27 的路徑 A-C-D 。汽車 5 看到四輛車是均勻分布的，他選擇了路徑 A-B-C ，成本是 [4(3) + 1] + [3 + 16] = 32 。最后，汽車 6 選擇了成本是 32 的路徑 A-C-D ?，F在所有六輛車都在從城鎮 A 到城鎮 D 的某一條路徑上。因為每一條路徑上有三輛車，而兩條路徑是對稱的，每輛車的成本是 32 。

　　這是 Braess 悖論出現的地方。如果在城鎮 B 和城鎮 C 之間增加一條新的、有效的路徑，你認為會出現怎樣的結果？常識是，增加道路容量會降低司機們的成本。但是既然這種現象被叫做“ Braess 悖論”而不是“ Braess 常識”，你應該猜到實際發生的并不是如此。

　　假設修改圖 5 中的地圖，在城鎮 B 和城鎮 C 之間增加了一條高效快捷路徑，它的成本函數是一個常數 1 。在加入了快捷路徑的第一個早晨，汽車 1 準備離開城鎮 A 。他有四種可能路徑選擇，各條路經的關連成本如下：

A-B-D cost = [4(1) + 1] + [1 + 16] = 22   A-C-D cost = [1 + 16] + [4(1) + 1] = 22   A-B-C-D cost = [4(1) + 1] + 1 + [4(1) + 1] = 11   A-C-B-D cost = [1 + 16] + 1 + [1 + 16] = 35

　　這是很有希望的。汽車 1 選擇了路徑 A-B-C-D ，通過快捷路徑來顯著降低他的交通成本——至少暫時如此。汽車 2 準備離開了。他看到汽車 1 選擇了路徑 A-B-C-D ，于是分析他的可能成本：

A-B-D cost = [4(2) + 1] + [1 + 16] = 26   A-C-D cost = [1 + 16] + [4(2) + 1] = 26   A-B-C-D cost = [4(2) + 1] + 1 + [4(2) + 1] = 19   A-C-B-D cost = [1 + 16] + 1 + [1 + 16] = 35

　　經過快速數學計算之后，汽車２頁選擇了路徑 A-B-C-D 。盡管汽車 1 已經在這條路徑上了，快捷路徑的有效性仍然使得它是汽車 2 的最好選擇。

原文轉自：http://www.anti-gravitydesign.com