斜楼板式汽车库:什么是Breass悖论？

“悖论”也可叫“逆论”，或“反论”，这个词的意义比较丰富，它包括一切与人的直觉和日常经验相矛盾的数学结论，那些结论会使我们惊异无比。 悖论是自相矛盾的命题。即如果承认这个命题成立，就可推出它的否定命题成立；反之，如果承认这个命题的否定命题成立，又可推出这个命题成立。

例如比较有名的理发师悖论：某乡村有一位理发师，一天他宣布：只给不自己刮胡子的人刮胡子。这里就产生了问题：理发师给不给自己刮胡子？如果他给自己刮胡子，他就是自己刮胡子的人，按照他的原则，他不能给自己刮胡子；如果他不给自己刮胡子，他就是不自己刮胡子的人，按照他的原则，他就应该给自己刮胡子。这就产生了矛盾。

1900年前后,在数学的集合论中出现了三个著名悖论，理发师悖论就是罗素悖论的一种通俗表达方式。此外还有康托尔悖论、布拉利—福尔蒂悖论。这些悖论特别是罗素悖论，在当时的数学界与逻辑界内引起了极大震动。触发了数学的第三次危机。

悖论有三种主要形式。

1．一种论断看起来好像肯定错了，但实际上却是对的（佯谬）。

2．一种论断看起来好像肯定是对的，但实际上却错了（似是而非的理论）。

3．一系列推理看起来好像无懈可击，可是却导致逻辑上自相矛盾。

悖论有以下几类：

逻辑悖论、概率悖论、几何悖论、统计悖论和时间悖论等。

　　节选自“http://www.vckbase.com/document/viewdoc/?id=1593#Braess_悖论”引号内为网址
　　Braess 悖论

　　现在来看看 Braess 悖论。我的例子使用了一个传统场景——汽车交通，但是我描述了这个悖论是怎样扩展到软件测试和其他情况的。关于 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 的最好选择。

　　现在汽车 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 ，因为这是成本最低的。现在 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 。现在增加了额外公路容量，我们却增加每个司机的成本！

　　这个例子提供了一个对 Braess 悖论的实际接触。因为这和网络系统上所传输的数据包有明显的关系， Braess 悖论受到了研究人员的深入研究。你能非正式的总结这个悖论：有时候增加节点之间的路径数反而会增加网络拥塞。从软件测试角度来说， Braess 悖论会在进行网络性能测试的时候出现。老实说，你碰到 Braess 悖论的机会很少。但是这个现象确实存在。启示是，你不应该假设增加网络容量就会提高性能。如果你增加了容量但是没有看到你所期望的性能提高， Braess 悖论就是应该去调查的。

　　Braess悖论是由数学家 Dietrich Braess在1968 年的一篇文章中提出的，是一佯谬。Braess悖论是指在个人独立选择路径的情况下，为某路网增加额外的通行能力（如增加路段等），反而会导致了整个路网的整体运行水平降低的情况。
　　有时在一个交通网络上增加一条路段，或者提高某个路段的局部通行能力，反而使所有出行者的出行时间都增加了，这种为了改善通行能力的投入不但没有减少交通延误，反而降低了整个交通网络的服务水平。
　　人们对这个问题做过许多研究，在城市建设当中也尽量避免这种现象的发生。但在复杂的城市道路当中，Braess 悖论仍然不时出现，造成实际交通效率的显著下降。若某道路系统的纳什均衡并非最优状态，就可能会产生Braess悖论现象。