軟件測試悖論之Braess悖論

         軟件測試悖論之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 的最好選擇。

　　現在汽車 3 準備離開了，他的選擇是：

  A-B-D cost = [4(3) + 1] + [1 + 16] = 30
  A-C-D cost = [1 + 16] + [4(3) + 1] = 30
  A-B-C-D cost = [4(3) + 1] + 1 + [4(3) + 1] = 27
  A-C-B-D cost = [1 + 16] + 1 + [1 + 16] = 35

 

　　再次，這個快捷路徑 A-B-C-D 是最好的選擇。汽車 4 準備離開城鎮 A ，觀察了錢三個司機的決定，算出了他自己的成本：

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

 

　　快捷路徑上目前的交通使得 A-B-C-D 比路徑 A-B-D 和 A-C-D 的成本要高。假設汽車 4 選擇了路徑 A-B-C （如果汽車 4 選擇了 A-C-D ，細節會有一點不同，但是總的結果是一樣的）。

　　汽車 5 現在準備離開了，他分析了他的選擇：

  A-B-D cost = [4(5) + 1] + [2 + 16] = 39
  A-C-D cost = [1 + 16] + [4(4) + 1] = 34
  A-B-C-D cost = [4(5) + 1] + 1 + [4(4) + 1] = 39
  A-C-B-D cost = [1 + 16] + 1 + [2 + 16] = 36

 

　　因此汽車 5 決定選擇路徑 A-C-D 。最后一輛車，汽車 6 ，現在準備離開了，他觀察了前面 5 個司機的決定，做出了他自己的分析：

  A-B-D cost = [4(5) + 1] + [2 + 16] = 39
  A-C-D cost = [2 + 16] + [4(5) + 1] = 39
  A-B-C-D cost = [4(5) + 1] + 1 + [4(5) + 1] = 43
  A-C-B-D cost = [2 + 16] + 1 + [2 + 16] = 37

 

　　汽車 6 選擇了路徑 A-C-B-D ，因為這是成本最低的?，F在 6 輛車都在路上了，你可以算出每輛車的成本。

  Car 1 route A-B-C-D, cost = [4(4) + 1] + 1 + [4(4) + 1] = 35
  Car 2 route A-B-C-D, cost = [4(4) + 1] + 1 + [4(4) + 1] = 35
  Car 3 route A-B-C-D, cost = [4(4) + 1] + 1 + [4(4) + 1] = 35
  Car 4 route A-B-D, cost = [4(4) + 1] + [1 + 16] = 34
  Car 5 route A-C-D, cost = [2 + 16] + [4(4) + 1] = 35
  Car 6 route A-C-B-D, cost = [2 + 16] + 1 + [1 + 16] = 36

 

　　回憶一下，如果沒有這條快速路，每輛車的成本是 32 ?，F在增加了額外公路容量，我們卻增加每個司機的成本！

　　這個例子提供了一個對 Braess 悖論的實際接觸。因為這和網絡系統上所傳輸的數據包有明顯的關系， Braess 悖論受到了研究人員的深入研究。你能非正式的總結這個悖論：有時候增加節點之間的路徑數反而會增加網絡擁塞。從軟件測試角度來說， Braess 悖論會在進行網絡性能測試的時候出現。老實說，你碰到 Braess 悖論的機會很少。但是這個現象確實存在。啟示是，你不應該假設增加網絡容量就會提高性能。如果你增加了容量但是沒有看到你所期望的性能提高， Braess 悖論就是應該去調查的。

原文轉自：http://www.kjueaiud.com