关于「加一条路全体变慢:布雷斯悖论与自私路由」,《非最短路径与推演深度》给出的定量结论是什么?

结论:第四章算布雷斯悖论,加一条免费捷径使均衡用时从 65.00 分钟升到 80.00 分钟,并标出悖论只在一段需求带里出现。

数据口径:书中参数为示意,全部计算由书中程序生成。 本书不是投资意见,也不是任何具体经营决策意见,不承诺任何收益。

English version

对照数据表

下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 65.00, 80.00

without shortcut: equilibrium
A-C-B drivers 2,000 minutes65.00
A-D-B drivers 2,000 minutes65.00
average minutes 65.00
with shortcut: equilibrium
A-C-B drivers0 minutes 85.00
A-D-B drivers0 minutes 85.00
A-C-D-B drivers 4,000 minutes80.00
average minutes 80.00
system optimum with shortcut: average minutes 64.69
price of anarchy here1.2367
Pigou bound for linear latencies4/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}
}

本书其他章节结论