关于「加一条路全体变慢:布雷斯悖论与自私路由」,《非最短路径与推演深度》给出的定量结论是什么?
结论:第四章算布雷斯悖论,加一条免费捷径使均衡用时从 65.00 分钟升到 80.00 分钟,并标出悖论只在一段需求带里出现。
数据口径:书中参数为示意,全部计算由书中程序生成。 本书不是投资意见,也不是任何具体经营决策意见,不承诺任何收益。
对照数据表
下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 65.00, 80.00
| without shortcut: equilibrium | |
| A-C-B drivers 2,000 minutes | 65.00 |
| A-D-B drivers 2,000 minutes | 65.00 |
| average minutes 65.00 | |
| with shortcut: equilibrium | |
| A-C-B drivers | 0 minutes 85.00 |
| A-D-B drivers | 0 minutes 85.00 |
| A-C-D-B drivers 4,000 minutes | 80.00 |
| average minutes 80.00 | |
| system optimum with shortcut: average minutes 64.69 | |
| price of anarchy here | 1.2367 |
| Pigou bound for linear latencies | 4/3 = 1.3333 |
查看完整验算程序
# Chapter 4. p41: Braess's network - a free shortcut makes everyone slower
# Wheatstone network, linear latencies l_e(x) = a_e x + b_e (minutes):
# A->C: x/100, C->B: 45, A->D: 45, D->B: x/100, shortcut C->D: 0.
# 4,000 drivers. Wardrop equilibrium: every used route has the same
# time and no unused route is faster. System optimum: the same with
# marginal costs 2 a_e x + b_e. Supports are enumerated and the linear
# equations solved exactly with fractions. Textbook illustrative data.
import itertools
from fractions import Fraction as F
EDGES = {"AC": (F(1, 100), F(0)), "CB": (F(0), F(45)),
"AD": (F(0), F(45)), "DB": (F(1, 100), F(0)),
"CD": (F(0), F(0))}
ROUTES = {"A-C-B": ("AC", "CB"), "A-D-B": ("AD", "DB"),
"A-C-D-B": ("AC", "CD", "DB")}
def solve_linear(m, rhs):
n = len(rhs)
a = [row[:] + [r] for row, r in zip(m, rhs)]
for c in range(n):
p = next((r for r in range(c, n) if a[r][c] != 0), None)
if p is None:
return None
a[c], a[p] = a[p], a[c]
for r in range(n):
if r != c and a[r][c] != 0:
k = a[r][c] / a[c][c]
a[r] = [x - k * y for x, y in zip(a[r], a[c])]
return [a[i][n] / a[i][i] for i in range(n)]
def route_cost(name, flows, k):
load = {e: F(0) for e in EDGES}
for r, f in flows.items():
for e in ROUTES[r]:
load[e] += f
out = F(0)
for e in ROUTES[name]:
a, b = EDGES[e]
out += k * a * load[e] + b
return out
def equilibrium(routes, demand, k=1):
for size in range(len(routes), 0, -1):
for sup in itertools.combinations(routes, size):
# unknowns: flows on sup and common cost c
m, rhs = [], []
for r in sup:
row = []
for s in sup:
unit = {q: F(1 if q == s else 0) for q in routes}
zero = {q: F(0) for q in routes}
row.append(route_cost(r, unit, k) -
route_cost(r, zero, k))
const = route_cost(r, {q: F(0) for q in routes}, k)
m.append(row + [F(-1)])
rhs.append(-const)
m.append([F(1)] * len(sup) + [F(0)])
rhs.append(F(demand))
sol = solve_linear(m, rhs)
if sol is None or min(sol[:-1]) < 0:
continue
flows = {q: F(0) for q in routes}
flows.update(dict(zip(sup, sol[:-1])))
c = sol[-1]
if all(route_cost(q, flows, k) >= c for q in routes):
return flows
return None
def avg_time(flows, demand):
return sum_frac([f * route_cost(r, flows, 1)
for r, f in flows.items()]) / demand
def sum_frac(xs):
out = F(0)
for x in xs:
out += x
return out
D = 4000
for label, routes in (("without shortcut", ["A-C-B", "A-D-B"]),
("with shortcut", list(ROUTES))):
eq = equilibrium(routes, D)
print("{}: equilibrium".format(label))
for r in routes:
print(" {:<8} drivers {:>5,} minutes {:6.2f}".format(
r, int(eq[r]), float(route_cost(r, eq, 1))))
print(" average minutes {:.2f}".format(float(avg_time(eq, D))))
opt = equilibrium(list(ROUTES), D, k=2)
print("system optimum with shortcut: average minutes {:.2f}".format(
float(avg_time(opt, D))))
ratio = avg_time(equilibrium(list(ROUTES), D), D) / avg_time(opt, D)
print("price of anarchy here: {:.4f}".format(float(ratio)))
print("Pigou bound for linear latencies: 4/3 = {:.4f}".format(4 / 3))唯一数据源与引用
范雅福(Fan, Y.). (2026). 《非最短路径最优解、二阶连锁效应全息推演与周密思考复利母典》第 4 章「加一条路全体变慢:布雷斯悖论与自私路由」(版本 1.0.0). 5D Library. DOI 待发布
DOI 待发布 · 专著页正式发布后上线(本站暂无专著页) · 5DL-B-384 · v1.0.0 · CC-BY-NC-ND-4.0
BibTeX
@book{fan2026384,
author = {Fan, Yafu},
title = {When the Shortest Path Fails: Brachistochrone Detours, Second-Order Consequence Mapping and Holographic Deep Thinking},
year = {2026},
publisher = {5D Library},
edition = {1.0.0},
note = {DOI pending}
}