Monday, March 18, 2013

网络相关的几个悖论


Braess's paradox
这个悖论是说在网络中添加新的路径,反而有可能造成更大的拥塞;反之,删除掉某些边,可能会让拥塞缓解。
乍一看,似乎比较难理解,但是回过头来考虑到在网络中传输的个体(比如交通网络中的车辆)实际上选择的都是局部最优的贪婪算法,即大家都去抢目前看来似乎比较快的路径,结果反而造成路径的通过时间变长。这是典型的局部优化导致全局不优化的一个例证。
一个很直观的简单例子在http://en.wikipedia.org/wiki/Braess's_paradox中可以看到。
这也实际上给治理交通拥堵的城市规划部门提了个醒,不能简单拍拍脑袋说拓宽某条容易堵车路,或者修条新路,有时候反而是起到相反的作用。反之,特定时间适当地限制从某些特定路通过,有时候反而能缓解。
实际上,城市里的交通规划比较理想的解决思路应该是上物联网+大规模智能计算。所有的路口安装足够多的sensor(比如监视器拍摄到画面),回传数据给类似waston一样的智能计算中心,进行实时的分析(视频、图像的分析是个迫切需要解决的问题)和计算、推理,然后统一进行调度,控制红绿(黄)灯的信号和时间。这样才有可能尽量合理的发掘道路的潜力,并能定位到真正的bottleneck所在,给市政规划、建设提出正确的建议和方向。
基于这个悖论的一些猜测也很有趣,比如是否存在如下可能?
在团体赛事中(足球、篮球),并不是队员越多越好,有时候少上一些队员反而更能赢得比赛?
管理机构中,人员也并非分工越细越好,合理的消除一些岗位或许反而使得整体办公效率提高。