• 软件测试技术
  • 软件测试博客
  • 软件测试视频
  • 开源软件测试技术
  • 软件测试论坛
  • 软件测试沙龙
  • 软件测试资料下载
  • 软件测试杂志
  • 软件测试人才招聘
    暂时没有公告

字号: | 推荐给好友 上一篇 | 下一篇

软件测试悖论之Braess悖论

发布: 2009-7-02 11:18 | 作者: 不详 | 来源: 领测软件测试网采编 | 查看: 19次 | 进入软件测试论坛讨论

领测软件测试网 关于 Braess 悖论的原始工作是 Dietrich Braess 的“ über ein Paradox der Verkerhsplannung ”( 1968 )。而我的例子,是基于我发现的几个例子,这几个例子对 Mark Wainwright 的工作作出了贡献。当时我不能亲自参加到 Wainwright 的原始工作中。

  Braess 悖论相当复杂,所以这里我给一个简化的、离散近似。假设象图 5 中显示的一样有四个城镇——城镇 A ,城镇 B ,城镇 C 和城镇 D 。

  连接任意两个城镇之间的每一条路都有一个关联成本,由图中与路相邻的方程给出。成本是陆上汽车数的函数。你能想象成本代表了在这条路上行驶所需要的时间,或者所需要的汽油,或者你们想要最小化的某些因素。现在假设某一个早晨,有 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 。现在所有六辆车都在从城镇 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

  经过快速数学计算之后,汽车2页选择了路径 A-B-C-D 。尽管汽车 1 已经在这条路径上了,快捷路径的有效性仍然使得它是汽车 2 的最好选择。



延伸阅读

文章来源于领测软件测试网 https://www.ltesting.net/

TAG: 软件测试 Braess


关于领测软件测试网 | 领测软件测试网合作伙伴 | 广告服务 | 投稿指南 | 联系我们 | 网站地图 | 友情链接
版权所有(C) 2003-2010 TestAge(领测软件测试网)|领测国际科技(北京)有限公司|软件测试工程师培训网 All Rights Reserved
北京市海淀区中关村南大街9号北京理工科技大厦1402室 京ICP备2023014753号-2
技术支持和业务联系:info@testage.com.cn 电话:010-51297073

软件测试 | 领测国际ISTQBISTQB官网TMMiTMMi认证国际软件测试工程师认证领测软件测试网